информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
За кого нас держат?Все любят медГде водятся OGRы
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Крупный взлом GoDaddy 
 Просроченный сертификат ломает... 
 Phrack #70/0x46 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / programming
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
[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.
Данные одни и те же, хеш функция та жа.
1






Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2021 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach