Почему вектор быстрее, чем карта в одном тесте, а не в другом? - PullRequest
9 голосов
/ 18 февраля 2012

Мне всегда говорили, что векторы бывают быстрыми, и за годы работы в программировании я никогда не видел ничего, что могло бы с этим смириться.Я решил (преждевременно оптимизировать и) написать ассоциативный класс, который представлял собой тонкую оболочку для последовательного контейнера (а именно ::std::vector и предоставлял тот же интерфейс, что и ::std::map. Большая часть кода была действительно простой, и я заставил его работать снебольшая сложность.

Однако в моих тестах POD различных размеров (от 4 до 64 байт) и std::strings, с количеством от восьми до двух тысяч, ::std::map::find был быстрее, чем мой ::associative::find, обычно примерно на 15% быстрее, почти для всех тестов. Я сделал Short, Self Contained, Correct (Compilable), Example , который ясно показывает это в ideone Я проверил реализацию MSVC9::std::map::find и подтвердил, что он очень близко совпадает с моими кодами vecfind и ::std::lower_bound, и не может объяснить, почему ::std::map::find работает быстрее, за исключением обсуждения вопроса о переполнении стека, где люди предположили, что метод двоичного поиска не приносит пользывообще от местоположения вектора до последнего сравнения (что делает его не быстрее), и что требуется указатель arithпримечание, что ::std::map узлы не требуют, что делает его медленнее.

Сегодня кто-то спросил меня об этом и предоставил этот код на ideone , который, когда я тестировал, показал, что вектор более чем в два раза быстрее.

Хотят ли кодеры StackOverflow разъяснить мне это очевидное несоответствие?Я перебрал оба набора кода, и они кажутся мне эквивалентными, но, может быть, я слепой от того, чтобы так много играть с ними обоими.

(Сноска: это очень близко к одному из моих предыдущих вопросов , но в моем коде было несколько ошибок, которые были устранены. Из-за новой информации / кода я чувствовал, что это достаточно отличается, чтобы оправдать отдельный вопрос. Если нет, я буду работатьпри объединении их.)

Ответы [ 4 ]

2 голосов
/ 18 февраля 2012

Что заставляет вас думать, что mapfind() быстрее, чем vecfind()?

Выход идеона для вашего кода сообщает примерно на 50% больше тиков для mapfind(), чем для vecfind().При выполнении кода здесь (x86_64 linux, g ++ - 4.5.1), mapfind() занимает примерно вдвое больше времени, чем vecfind().

Если увеличить карту / вектор в 10 раз, разница увеличивается дооколо 3 ×.

Обратите внимание, однако, что сумма вторых компонентов отличается.Карта содержит только одну пару с любым данным первым компонентом (с моим локальным PRNG, который создает карту с двумя элементами), в то время как vector может содержать несколько таких пар.

2 голосов
/ 18 февраля 2012

Количество элементов, которые вы помещаете в тестовый контейнер, превышает количество возможных выходных данных из rand() в Microsoft, поэтому вы получаете повторяющиеся числа.Сортированный вектор будет содержать все из них, в то время как map выбрасывает дубликаты.Проверьте размеры после их заполнения - вектор будет иметь 100000 элементов, карта - 32768. Поскольку карта намного короче, конечно, она будет иметь лучшую производительность.

Попробуйте multimap для яблок досравнение яблок.

1 голос
/ 18 февраля 2012

Я вижу некоторые проблемы с кодом (http://ideone.com/41iKt), который вы разместили на ideone.com. (ideone на самом деле показывает vector как быстрее, но локальная сборка с Visual Studio 11 Developer Preview показывает map быстрее).

Сначала я переместил переменную карты и использовал ее для инициализации вектора, чтобы получить одинаковый порядок и уникальность элемента, а затем я дал lower_bound собственный компаратор, который сравнивает только first, поскольку именно так будет поступать карта. После этих изменений Visual Studio 11 показывает вектор как более быстрый для тех же 100 000 элементов (хотя идеальное время существенно не меняется). http://ideone.com/b3OnH

С уменьшением test_size до 8 карта все еще быстрее. Это неудивительно, потому что именно так работает сложность алгоритма, все константы в функции, которые действительно описывают время выполнения, имеют малое значение N. Я должен увеличить test_size до 2700, чтобы вектор выровнялся, а затем опередил карта в этой системе.

0 голосов
/ 18 февраля 2012

Сортированный std :: vector имеет два преимущества по сравнению с std :: map:

  • Лучшая локальность данных: вектор сохраняет все данные в памяти непрерывно
  • Меньший объем памяти: вектор делаетне нужно много бухгалтерских данных (например, нет объектов узлов дерева)

Зависит ли важность этих двух эффектов от сценария.Есть два фактора, которые могут оказать значительное влияние:

Тип данных

Преимущество для std :: vector, если элементы являются примитивными типами, такими какцелые числа.В этом случае локальность действительно помогает, потому что все данные, необходимые для поиска, находятся в смежном месте в памяти.

Если элементы являются, скажем, строками, то локальность не очень помогает.В непрерывной векторной памяти теперь хранятся только объекты-указатели, которые потенциально находятся во всей куче.

Размер данных

Если std :: vector соответствует определенному уровню кэша, ноstd :: map не имеет, std :: vector будет иметь преимущество.Это , особенно , если вы продолжаете повторять тест для одних и тех же данных.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...