Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
[C++] хэш функция VC++ 2005 для строк с одинаковыми подстроками 14.01.08 00:49 Число просмотров: 3350
Автор: void <Grebnev Valery> Статус: Elderman
Отредактировано 14.01.08 00:52 Количество правок: 1
|
Может кто встречался со схожей задачей (не очень хорошо распределённые строковые ключи) и может подсказать эффективную хеш функцию? Необходимо создать hash_map(лучше hash_set) для строк “compound_key”, которые являются простой конкатенацией строк = “key_word1” + [“key_word2” + “key_word3”] +“key1” + “key2” + “key3”. Здесь,
key_word1 [key_word2, key_word3] – ключевые слова из набора в 10-25 слов
key1 – ключ из 4-х символов XXNN, где XX – символы алфавита (типа AA, AB, AC), NN – дополненные нулём слева числа последовательностей типа 01, 02, ..., 20). Например, AA01, AA02, ..., AB01, ... Всего существует 100 ключей “key1”
key2 – произвольная строка переменной длины (1-10 заглавных символов алфавита). Всего существует 1000 ключей “key2”.
key3 – 1-2 символа строкового представления чисел от -1 до 10.
Тесты hash_map/hash_set для таких последовательностей строк дают следующее результаты по скорости создания и поиска (поиск 100 000 псевдослучайных “compound_key”) в контейнере из 500 000 элементов (в относительных единицах):
*** MAP***
Стандартный std::map<const char*, SomeObject*, predicate>
- время создания map из 500 000 элементов, T = 1.0
- время поиска 100 000 элементов, T1 = 1.0
Стандартный VC2005 хеш для char* (стандартный хэш похож на “FNV”),
stdext::hash_map<const char*, SomeObject*, stdext::hash_compare<const char*, predicate>>
T = 2.752
T1 = 0.425
stdext::hash_map<const char*, SomeObject*, sz_stringhasher> с использованием “Bernstein” хэш функции
T = 2.073
T1 = 0.432
stdext::hash_map<const char*, SomeObject*, sz_stringhasher> с использованием “Shift-Add-XOR” хэш функции
T = 2.333
T1 = 0.380
*SET**
Стандартный std::set<const Object*, predicate>
T = 1.083
T1 = 0.929
stdext::hash_set<const Object*, sz_object_stringhasher> с использованием “Bernstein” хэш функции
T = 1.371
T1 = 0.434
stdext::hash_set<const Object*, sz_object_stringhasher> с использованием “Shift-Add-XOR” хэш функции
T = 1.546
T1 = 0.404
Похоже, что “Shift-Add-XOR” даёт лучшие результаты. Есть ли другие идеи?
Спасибо за помощь.
|
- [C++] хэш функция VC++ 2005 для строк с одинаковым... - void 14.01.08 00:49 [3350]
|
|
|
подробно о проекте
Анализ криптографических сетевых... 
