Как насчет сохранения индексов массива на карте

Question

моя программа использует boost :: unordered_map много, а карта насчитывает около 40 миллионов записей. Эта программа не делает вставки или удаления очень часто. Он просто случайно получает доступ к записям с использованием ключей.

Мне интересно, улучшит ли производительность (с точки зрения скорости доступа к записям), если я сохраню свои значения ввода (около 1 КБ каждый) в плоском массиве (возможно, std :: vector), и я используйте boost :: unordered_map, чтобы сохранить сопоставление ключей с индексами в этот массив.

Спасибо, Цуй

Answer 1

Да, это может серьезно ускорить вещи. На самом деле, это то, что Повысьте flat_map для :)

Документов относятся: Non-standard containers

Используя упорядоченные векторы вместо дерева на основе ассоциативных контейнеров является хорошо известной технологией в мире C++. Классическая статья Мэтта Austern в Why You Shouldn't Use set, and What You Should Use Instead (C++ Report 12:4, April 2000, PDF) просвещал:

...

Это дает вам больше, чем вы просили, потому что вы даже не нуждаются в посторонней индекс. Это дает вам больше локализации ссылок и более низкий объем памяти. Самое главное, это дает вам более низкую сложность (-> меньше ошибок) и замену на std::[unordered_]map с точки зрения интерфейса.

Answer 2

Сохранение значений в смежной памяти, например std :: vector, приведет к увеличению местоположения кеша. Это может сильно повлиять на производительность, но это зависит от шаблона доступа.

Если ваша охотничья выгода, помните золотое правило: всегда измерять!