Может кто встречался со схожей задачей (не очень хорошо распределённые строковые ключи) и может подсказать эффективную хеш функцию? Необходимо создать 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
Попробовал supper_hash. В принципе, поиск быстрее, но всё равно уступает XOR-SHIFT:
hash_map
Время создания (относительная величина, см. предыдущий постинг): T = 2.907
Время поиска T1 = 0.421
hash_set
T = 1.968
T1 = 0.419
Для той же последовательности ключей:
- время построения контейнера вущественно возрастает по сравнению с другими хеш, без существенного прироста скорости поиска. В моей задаче это не существенно, т.к. контейнер строится только один раз, при старте приложения.
- заметно уступают другим хеш-ам и min, и max выборочные время поиска. Стандартное отклонения T, T1 приблизительно такие же.
Спасибо, за инфу. Добавил в копилку ;)
Не понял, а rot13 пробовал или нет?15.01.08 16:08 Автор: leo <Леонид Юрьев> Статус: Elderman
Для hash_map - несколько уступает "Shift_and_XOR" по скорости поиска, но очень быстро "строит" map:
T= 1.788
T1 = 0.428
Для hash_set - самая быстрая и по скорости поиска, и по скороcти построения set-a (хотя разница в скорости поиска близка к погрешности эксперимента):
T= 1.213 (существенно быстрее предыдущих)
T1=0.399
Достойный кандидат, думаю, можно смело использовать.
Спасибо!
На работе стоит STLPort. Время поиска на ~40 меньше по...30.01.08 05:01 Автор: void <Grebnev Valery> Статус: Elderman
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
