Комментарии 39
Результаты по праву заставляют задуматься, спасибо.
А почему испытывали с -O3, а не -O2? Интересно было бы сравнить с более стандартной оптимизацией.
А почему испытывали с -O3, а не -O2? Интересно было бы сравнить с более стандартной оптимизацией.
Вы бы написали, что совет 23 взят из книги C.Мейерса «Эффективное использование STL». А то так сразу и непонятно, что за совет 23 такой.
А так, статья полезная, спасибо!
А так, статья полезная, спасибо!
Рассмотрите сценарий, когда операции вставки идут вперемешку с поиском. Т.е. вы заранее не знаете, какая операция будет следующей — вставки или поиска. А может, удаления. Тогда после каждой операции вставки вектор надо приводить в сортированный вид.
Мне кажется, что в таком случае он проиграет.
Мне кажется, что в таком случае он проиграет.
А, да, рандомить тоже стоит не с фиксированным параметром. А то мало ли как там наоптимизируют во время компиляции:)
Я бы рассмотрел вариант с добавлением в вектор не через сортировку, а через push_heap (предварительно создав кучу с помощью make_heap).
В случае изменений данных vector проиграет, так как вставка, а тем более удаление в нем дорогие. Тут как раз ситуация, когда изменений данных мало, в этом случае вектор может выигрывать, причем значительно.
random() не принимает параметров, Вас наверно смутила цифра 3 — это я хотел сказать что это стандартная функция Си.
С кучей тоже нужно будет делать сортировку, иначе как в ней эффективно искать.
random() не принимает параметров, Вас наверно смутила цифра 3 — это я хотел сказать что это стандартная функция Си.
С кучей тоже нужно будет делать сортировку, иначе как в ней эффективно искать.
Вставка в середину вектора не так уж и дорога, как может показаться. Если даже у вас там 10000 элементов, которые являются 64-битными указателями на фактические объекты, то для вставки придётся передвинуть блок в 80 Кбайт. Шина позволяет порядка гигабайта в секунду пропускать, на этом фоне 80 Кбайт — не так много. Сдвиг блока хоть и линейная по времени операция в теории, она может быть дешевле, чем поиск нужной ветки в двоичном дереве с кучей сравнений.
В куче push_heap добавляет за логарифм, сохраняя свойство кучи.
Если сценарий использования таков, что данные сначала добавляются, а только потом осуществляется поиск — то да, тут красно-черные деревья будут излишними.
Если сценарий использования таков, что данные сначала добавляются, а только потом осуществляется поиск — то да, тут красно-черные деревья будут излишними.
А верктор в C++ это массив или связанный список?
Массив.
Странно, что map так медленно добавляет. Неужели перебалансировка красно-черного дерева (емнип гарантированно выполняющаяся за конечное время) дороже, чем сдвиг массива на полмиллиона эементов?
Сдвиг массива выполняется специальной операцией прямого копирования куска памяти. На современных процессорах и контроллерах памяти эта операция довольно быстра.
Впрочем, я наверное не прав. Внутри там обычный memcpy, который даже со всеми оптимизациями имеет линейное время работы.
А memcpy разве не инлайнится по жесткому – software.intel.com/en-us/articles/memcpy-performance/?
В vector сдвиги данных происходят, только когда выделенная память под vector заканчивается, так как мы добавляем все время в конец.
кстати, reserve памяти не пробовали сделать в векторе? это тоже неплохо поднимает производительность, как показывает практика
В данной задачи нет. А так пробовал — tchnts.wordpress.com/2010/04/01/%D1%80%D0%B0%D1%81%D1%88%D0%B8%D1%80%D0%B5%D0%BD%D0%B8%D0%B5-stl-vector/ Пришел к выводу, что если памяти не жалко то reserve(16) или reserve(32) делать для всех векторов очень помогает для производительности. А если знать размер данных, то еще быстрее — resize, а потом memcpy прямо в вектор.
Тут же сортировка при добавлении подразумевается, как в конец добавлять?
Всегда было интересно, почем не сделать аналог deque, где в каждом куске оставлялся определенный кусок свободного места для последующей вставки элементов. Надо будет попробовать реализовать на досуге.
Это называется B-дерево
А вы делали вставку в map с помощью insert(), или использовали [] нотацию? В случае вставки нового значения лучше использовать insert(), так как использование [] для вставки нового объекта (которого еще нет) приводит к тому, что сначала создается объект по-умолчанию для данного ключа, а потом объект по умолчанию заменяется на вставляемый объект. То есть имеет место быть примерно двукратный overhead.
Вызывал operator[], но разница не столь значима (я делал эксперименты с set, в который добавлял через insert — разница была в пределах 5-7%). Двукратного оверхеда нету, так как основная часть времени уходит на поиск элемента (если их много), а он и в insert и в operator[] делается единожды.
Абсолютно согласен. Тем более что это логичнее: operator[] — это поиск элемента, а insert() — вставка элемента.
Интересно, в современных процессорах до сих пор нет железячных оптимизаций для TreeMap/HashMap на строках и числах? По-моему, в современном программировании это было бы нелишне :-)
Чрезмерное усложнение схемотехники ведет к неоправданному повышению стоимости, Вы готовы пойти на это и платить за процессор на несколько порядков больше ради нескольких процентов профита?
Распространненые операции стоит выносить в железо, профит таки наблюдается. В Intel SSE4.2 появились операции CRC32 (используется в сетевых/дисковых драйверах), поиск подстроки.
byteworm.com/2010/10/13/crc32/
byteworm.com/2010/10/13/crc32/
Интересно было бы посмотреть накладные расходы на вызов функции random().
И, конечно, передавать объекты в функцию через указатель — это не C++-way; канонический способ — ссылки; впрочем, в конце концов, это дело вкуса.
И, конечно, передавать объекты в функцию через указатель — это не C++-way; канонический способ — ссылки; впрочем, в конце концов, это дело вкуса.
random() работает за O(1), если я не ошибаюсь то он состоит из произведения, суммы и деления, т.е. 3 операции на целочисленных типах, это очень быстро.
мне больше интересно зачем написали свои велосипеды типа vmin/vmax, когда есть подходящие под данные нужды max_element и min_element в stl
мне больше интересно зачем написали свои велосипеды типа vmin/vmax, когда есть подходящие под данные нужды max_element и min_element в stl
EuroElessar в общем прав — random в glibc в наиболее простом алгоритме (а такой и был выбран) реализован вот так:
val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
val = ((state[0] * 1103515245) + 12345) & 0x7fffffff;
И всё же map в первую очередь предназначен для реализации чего-то типа map<string, int> phone_book;.
И получается потом вот так.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Совет 23. Рассмотрите возможность замены ассоциативных контейнеров сортированными векторами