Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
| | | | |
На работе стоит STLPort. Время поиска на ~40 меньше по... 30.01.08 05:01 Число просмотров: 2172
Автор: void <Grebnev Valery> Статус: Elderman
|
На работе стоит STLPort. Время поиска на ~40 меньше по has_set в сравнеии и MS.
Данные одни и те же, хеш функция та жа.
|
|
<programming>
|
[C++] хэш функция VC++ 2005 для строк с одинаковыми подстроками 14.01.08 00:49
Автор: 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” даёт лучшие результаты. Есть ли другие идеи?
Спасибо за помощь.
|
|
Есть вариант а-ля xor-shift, только немного лучше. 14.01.08 14:03
Автор: leo <Леонид Юрьев> Статус: Elderman
|
Попробуй rot13 с http://vak.ru/doku.php/proj/hash/efficiency.
Если сильно хочеться распределение близкое у идеальному, то:
unsigned super_hash (const _TCHAR *s)
{
unsigned __int64 h;
for (h = 0; *s; s++)
h = 6364136223846793005ui64 * (h + s[0]) + 5975218566490153283ui64;
return (unsigned) (h >> 32);
}
---
P.S.
64-битное умножение (по модулю 2^64) легко заменить на два 32-битных умножения и __emulu();
|
| |
Попробовал supper_hash. В принципе, поиск быстрее, но всё... 15.01.08 06:54
Автор: void <Grebnev Valery> Статус: Elderman
|
Попробовал 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
|
|
|
| | | |
Сегодня попробовал. Хорошая функция. 16.01.08 05:40
Автор: void <Grebnev Valery> Статус: 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
|
На работе стоит STLPort. Время поиска на ~40 меньше по has_set в сравнеии и MS.
Данные одни и те же, хеш функция та жа.
|
|
|
подробно о проекте
Анализ криптографических сетевых...
