Хэш-карта оптимизирована для поиска

Я ищу карту с фиксированными ключами (исправленными во время инициализации) и обеспечивающую более быстрый поиск. Он может не поддерживать добавление/обновление элементов позже. Есть ли какой-то алгоритм, который просматривает список ключей и формулирует функцию, чтобы ее можно было быстрее найти позже. В моем случае ключи — это строки.

Обновлять:

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


c++ hash data-structures string-hashing
person balki    schedule 08.12.2011    source источник
comment
Посмотрите на gperf, он обеспечивает идеальное хеширование во время компиляции, когда все ключи для хеш-таблицы известны.   -  person Seth Carnegie    schedule 08.12.2011

Ответы (4)


arrow_upward
2
arrow_downward

CMPH может быть тем, что вы ищете. В основном это gperf без необходимости установки во время компиляции.

Хотя, конечно, std::unordered_map, как в C++11, тоже может подойти, хотя, возможно, с несколькими коллизиями.

Так как вы ищете строки, для строк, trie (любой из различных вариантов trie, crit-bit или любые другие причудливые имена, которые у них есть) также может быть полезно изучить, особенно если у вас их много . В свободном доступе есть много бесплатных реализаций trie.
Преимущество try в том, что они могут индексировать и сжимать строки, поэтому они используют меньше памяти, что повышает вероятность наличия данных в кеше. Кроме того, шаблон доступа менее случайный, что также способствует кэшированию. Хеш-таблица должна хранить значение плюс хэш и индексировать более или менее случайным образом (не случайно, а непредсказуемо) в памяти. Структура, подобная trie/trie, в идеале нуждается только в одном дополнительном бите, который отличает ключ от его общего префикса в каждом узле.

(Обратите внимание, кстати, что O(log(N)) вполне может быть быстрее, чем O(1) в таком случае, потому что big-O не учитывает такие вещи.)

person Damon    schedule 08.12.2011
comment
Trie намного медленнее, чем std::unordered_map для строк (он же std::string ака std::basic_string‹char›). Протестировано с разными флагами оптимизации. И в Интернете есть много сообщений об этом. - person cppist; 01.05.2013
comment
@cppist: это зависит от реализации и набора данных (как его размера, так и фактических данных). std::unordered_map — это хеш-карта. Это O(1) в отношении фактического поиска, но O(N) в отношении длины строки, и он должен выполнять дополнительное O(N) сравнение. Критически-битное дерево или тройка равны O(log(N)) как по длине ключа, так и по количеству ключей. Ему не нужно окончательное сравнение, ему не нужно касаться данных после первого другого байта, и он более удобен для кэширования, затрагивая меньшее количество страниц. Пока ответ не так уж прост, хэш может действительно не самый быстрый инструмент. - person Damon; 11.05.2013
comment
N - количество слов. C - количество столкновений. S - длина строки. Trie ищет строку для T=O1(S). Набор хэшей ищет строку для H=O2(S)+O3(C). Но O1(S) намного больше, чем O2(S). Набор хэшей использует простые арифметические операции с последующими данными. Но trie использует несколько разыменований и ветвей if. Даже если разыменование и ветвление будут выполняться быстрее, чем простая арифметика, обычные процессоры лучше работают с последовательными данными, а не с несущественными. Хорошо сделанная простая попытка действительно медленнее, чем unordered_map, также известная как хеш-набор. По крайней мере для строк (char). - person cppist; 12.05.2013

arrow_upward
1
arrow_downward

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

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

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

Это должно быть компенсировано стоимостью нескольких сравнений строк (которые не так уж и дороги, если вам не нужно сопоставлять).

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

person peterchen    schedule 08.12.2011
comment
+1 за рассмотрение вопроса о том, нужен ли вам вопрос о верхнем пределе, плюс ваш последний абзац. То, что вы описываете в последнем абзаце, в основном является хешированием с кукушкой. Как вы сказали, это медленнее для индивидуального поиска (и для вставок тоже), но у него есть гарантированная верхняя граница в худшем случае, что, если у кого-то есть это требование, очень круто. - person Damon; 08.12.2011

arrow_upward
0
arrow_downward

Попробуйте google-sparsehash: http://code.google.com/p/google-sparsehash/< /а>

An extremely memory-efficient hash_map implementation. 2 bits/entry overhead! 
The SparseHash library contains several hash-map implementations, including 
implementations that optimize for space or speed.
person Lei Mou    schedule 08.12.2011

arrow_upward
0
arrow_downward

В аналогичной теме ((количество) элементов, известных во время компиляции), я создал этот: Поиск известного набора целочисленных ключей. Низкие накладные расходы, нет необходимости в идеальном хэше. К счастью, это на C ;-)

person wildplasser    schedule 08.12.2011