В смысле "алгоритмической сложности"
В случае 1 вариант 2 засчет того, что итераторы ветора RandomAcess
В случае 2 скорее вариант 1, поскольку лишнее копирование избегается
В реальной жизни на малых массивах не заметишь скорее всего, основной источник тормозов будет проверки и синхронизация (если стоит по дефолту).
Здравствуйте, denisko, Вы писали:
D>В смысле "алгоритмической сложности" D>В случае 1 вариант 2 засчет того, что итераторы ветора RandomAcess
Каким образом?
Вариант 1: lower_bound() выполняется за О(N) (последовательный просмотр).
Вариант 2: copy() выполняется за О(N) + lower_bound() за O(logN).
Итого оба варианта О(N). Только в первом варианте мы проходим в среднем по половине списка, что бы найти элемент, во-втором варианте мы проходим по всему списку + делаем копию + делаем бинарный поиск.
з.ы. это в предположении, что сравнение элементов занимает сравнимое время с чтениями/копированиями/итд.
Здравствуйте, shvonder, Вы писали:
S>Какой вариант быстрее?
lower_bound требует random access iterator, чего у листа нету, поэтому std::find_if будет в первом случае самым быстрым вариантом, а во втором, очевидно самым быстрым вариантом будет метод list'а — sort, хоть сортировка и stable, а вообще список это плохой выбор для хранения отсортированных данных, ибо факт сортировки недают никакого прироста производительности, стоит задумать о выборе вектора, дека или множества.
Здравствуйте, Sni4ok, Вы писали:
S>Здравствуйте, shvonder, Вы писали:
S>>Какой вариант быстрее?
S>lower_bound требует random access iterator, чего у листа нету, поэтому std::find_if будет в первом случае самым быстрым вариантом, а во втором, очевидно самым быстрым вариантом будет метод list'а — sort, хоть сортировка и stable, а вообще список это плохой выбор для хранения отсортированных данных, ибо факт сортировки недают никакого прироста производительности, стоит задумать о выборе вектора, дека или множества.
Мне нужно 1)удалять элементы из списка 2)быстро находить по ключу. Какой контейнер нужен, как вы считаете?
А почему факт сортировки не даёт ? lower_bound — это разве не бинарный поиск ?
Здравствуйте, shvonder, Вы писали:
S>Мне нужно 1)удалять элементы из списка 2)быстро находить по ключу. Какой контейнер нужен, как вы считаете? S>А почему факт сортировки не даёт ? lower_bound — это разве не бинарный поиск ?
бинарный, но требует random access iterator'а, раз нужно удалять элементы, на вашем месте я бы выбрал std::set, возможно даже с boost::fast_pool_allocator в качесте аллокатора(тут правда есть ньюансы, если контейнер очень большой с огромным колл. эллементов(миллионы), то
boost::pool неподходит в силу сложности освобождения памяти O(N)).
Здравствуйте, remark, Вы писали:
R>Вариант 1: lower_bound() выполняется за О(N) (последовательный просмотр)....мы проходим в среднем по половине списка, что бы найти элемент.
Вот VS-реаизация. На мой нескушённый взгяд, это — бинарный поиск, токо advance для list'a развернётся в цикл.Или я неправ ?
template<class _FwdIt,
class _Ty,
class _Diff> inline
_FwdIt _Lower_bound(_FwdIt _First, _FwdIt _Last, const _Ty& _Val, _Diff *)
{ // find first element not before _Val, using operator<
_DEBUG_ORDER_SINGLE(_First, _Last, true);
_Diff _Count = 0;
_Distance(_First, _Last, _Count);
for (; 0 < _Count; )
{ // divide and conquer, find half that contains answer
_Diff _Count2 = _Count / 2;
_FwdIt _Mid = _First;
std::advance(_Mid, _Count2);
_DEBUG_ORDER_SINGLE(_Mid, _Last, false);
if (_DEBUG_LT(*_Mid, _Val))
_First = ++_Mid, _Count -= _Count2 + 1;
else
_Count = _Count2;
}
return (_First);
}
Здравствуйте, remark, Вы писали:
R>Здравствуйте, denisko, Вы писали:
D>>В смысле "алгоритмической сложности" D>>В случае 1 вариант 2 засчет того, что итераторы ветора RandomAcess
R>Каким образом?
Я ступил копи не заметил.
В первом варианте — линейный поиск по списку. Во втором — линейное копирование, затем логарифмический поиск.
Даст выигрыш только в том случае, если операция сравнения существенно медленнее операции обмена.
Такое может быть в реальных условиях, например, если
struct MyStruct
{
const char* m_shared_text; // любой способ разделяемого владения - начиная от глобального словаря
};
bool operator < (MyStruct const& a, MyStruct const& b) { return *a.m_shared_text < *b.m_shared_text; }
естественно, при достаточно длинных строках.
S>Случай 2 S>
Сортировка списка — линейно-логарифмическая, без обменов.
Сортировка массива — тоже линейно-логарифмическая, но уже с обменами. Плюс оверхед на копирование туда-обратно.
Даст выигрыш, если
— MyStruct имеет небольшой размер, так, что обмен элементов совершается быстрее, чем обмен четырёх указателей при переносе узла списка
— вектор влезет в несколько линеек кэша, тогда как список окажется раскидан по памяти
Перекуём баги на фичи!
