Насколько большой должна быть коллекция, чтобы std :: map <k, v> опередил отсортированный std :: vector <std :: pair <k, v>>?

Question

Насколько большой должна быть коллекция, чтобы std :: map опережал отсортированный std :: vector>?

У меня есть система, в которой мне нужно несколько тысяч ассоциативных контейнеров, и std::map, похоже, несет много накладных расходов с точки зрения кеш-памяти процессора. Я где-то слышал, что для небольших коллекций std :: vector может быть быстрее, но мне интересно, где эта строка ....

РЕДАКТИРОВАТЬ: я говорю о 5 или менее элементов одновременно в данной структуре. Меня больше всего беспокоит время выполнения, а не место для хранения. Я знаю, что подобные вопросы по своей сути зависят от платформы, но я ищу «практическое правило» для использования.

Billy3

Answer 1

Это не вопрос размера, а использования.

Сортированный вектор хорошо работает, когда используется схема чтения данных, а затем выполняется поиск в данных.

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

Причина этого довольно проста: у карты больше накладных расходов на отдельный поиск (благодаря использованию связанных узлов вместо монолитного блока хранения). Однако вставка или удаление, которые поддерживают порядок, имеют сложность только O (lg N). Вставка или удаление, которые поддерживают порядок в векторе, имеют сложность O (N).

Есть, конечно, различные гибридные структуры, которые также могут быть полезны для рассмотрения. Например, даже когда данные обновляются динамически, вы часто начинаете с большого количества данных и вносите в него сравнительно небольшое количество изменений за раз. В этом случае вы можете загрузить свои данные в память в отсортированный вектор и сохранить (небольшое количество) добавленных объектов в отдельном векторе. Так как этот второй вектор обычно довольно мал, вы просто не будете его сортировать. Когда / если он становится слишком большим, вы сортируете его и объединяете с основным набором данных.

Edit2: (в ответ на редактирование в вопросе). Если вы говорите о 5 предметах или меньше, вам лучше всего игнорировать все из вышеперечисленного. Просто оставьте данные не отсортированными и выполните линейный поиск. Для такой небольшой коллекции практически нет разницы между линейным поиском и бинарным поиском. Для линейного поиска вы ожидаете отсканировать в среднем половину элементов, что дает ~ 2,5 сравнения. Для бинарного поиска вы говорите о log ₂ N, который (если у меня математика работает в это время по утрам) работает до ~ 2.3 - слишком маленькая разница, чтобы о ней заботиться или замечать (в Фактически, бинарный поиск имеет достаточные накладные расходы, что может очень легко закончиться медленнее).

Answer 2

Основная проблема с std::map - это проблема кеша, как вы указали.

Сортированный вектор - это хорошо известный подход: Loki::AssocVector.

Для очень маленьких наборов данныхAssocVector должен разрушить карту, несмотря на то, что копия была задействована во время вставки просто из-за локальности кэша.AssocVector также превзойдет карту для использования только для чтения.Бинарный поиск там более эффективен (меньше указателей для отслеживания).

Для всех других применений вам потребуется профилировать ...

Однако существует гибридная альтернатива, которую вы, возможно, пожелаетерассмотрите возможность использования параметра карты Allocator для ограничения области памяти, в которой расположены элементы, что сводит к минимуму проблему с указанием локальности (отсутствует корень кэша).

Существует также сдвиг парадигмы, который выМожно подумать: нужны ли вам отсортированные элементы или быстрый поиск?

В C ++ единственные STL-совместимые контейнеры для быстрого поиска были реализованы в виде отсортированных ассоциативных контейнеров в течение многих лет.Однако в грядущем C ++ 0x появилась долгожданная unordered_map, которая могла бы выполнить все вышеперечисленные решения!

Answer 3

Если вы говорите «превзойти», то имеете в виду, что занимает больше места (то есть памяти), тогда весьма вероятно, что вектор всегда будет более эффективным (базовая реализация - это непрерывный массив памяти без данных, где map - это дерево таким образом, каждая информация подразумевает использование большего количества места). Однако это зависит от того, сколько вектор резервирует дополнительное пространство для будущих вставок.

Когда речь идет о времени (а не о пространстве), вектор также всегда будет более эффективным (делает дихотомический поиск). Но это будет экстремально плохо для добавления новых элементов (или их удаления).

Итак: нет простого ответа! Посмотрите на сложности, подумайте об использовании, которое вы собираетесь делать. http://www.cplusplus.com/reference/stl/

Answer 4

Должно быть в миллионных статьях. И даже там ...

Я больше думаю об использовании памяти и доступе к памяти. Под сотни тысяч, бери все, что хочешь, заметной разницы не будет. В наши дни процессоры работают очень быстро, и узким местом является задержка памяти.

Но даже с миллионами предметов, если ваша карта <> была построена путем вставки элементов в случайном порядке. Когда вы захотите пройти по своей карте (в отсортированном порядке), вы в конечном итоге будете случайным образом перепрыгивать в памяти, останавливая ЦП для доступной памяти, что приведет к снижению производительности.

С другой стороны, если ваши миллионы элементов находятся в векторе, обходить его очень быстро, используя предсказания доступа к памяти ЦП.

Как написали другие, это зависит от вашего использования.

Редактировать: Я бы больше подверг сомнению способ организации тысяч ассоциативных контейнеров, чем сами контейнеры, если они содержат только 5 элементов.

Answer 5

РЕДАКТИРОВАТЬ: Видя, что вы говорите о 5 предметах или меньше:

Сортировка включает в себя обмен объектами. При вставке в std :: map это будет включать только обмен указателями. Будет ли вектор или карта быстрее, зависит от того, насколько быстро будет поменяться местами два элемента.

---

Я предлагаю вам профилировать вашу заявку, чтобы понять это.

---

Если вы хотите простое и общее правило, то вам не повезло - вам нужно учитывать как минимум следующие факторы:

Время

• Как часто вы вставляете новые предметы по сравнению с тем, как часто вы ищете?
• Можете ли вы пакетно вставить новые элементы?
• Сколько стоит сортировка вашего вектора? Векторы элементов, которые дорого поменять местами, становятся очень дорогими для сортировки - векторы указателей занимают намного меньше.

Память

• Сколько накладных расходов на распределение имеет используемый вами распределитель? std :: map будет выполнять одно выделение для каждого элемента.
• Насколько велики ваши пары ключ / значение?
• Насколько велики ваши указатели? (32/64 бит)
• Как быстро растет реализация std :: vector? (Популярные факторы роста 1,5 и 2)

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