Войти
ПрограммированиеФорумОбщее

Быстрая загрузка огромного словаря из файла (2 стр)

Страницы: 1 2
#15
17:00, 28 мар. 2016

ashujon
С хешем надо будет убеждаться, что нет коллизий. Неохота с этим возиться. Конечно можно взять хэш 64 бита и надеяться, что коллизий не будет, но это как-то нечестно.
Я сделал просто одну длинную строчку со всеми склеенными именами и массив структурок со всеми смещениями и размерами. Размер структурки 16 байт. Итого, где-то на каждый элемент приходится около 40 байт в файле для ускорения поиска. Даже для 10 000 000 элементов памяти хватит.
Но вообще, если перейти на хэши так, чтобы не было коллизий вообще, то будет профит - 16 байт на элемент, где 8 байт хэш и 8 байт смещение в файле. А можно наверное порезать хэш до 7 байт и смещение до 5 байт, чтобы уложиться в 12 байт. Только сравнивать хэши будет сложнее.
Но если вдруг понадобится имя, а не его хэш, то придётся читать его из исходного файла. В общем, допишу программу так, а потом будет видно, что и как оптимизировать, и стоит ли вообще это дальше делать.


#16
17:06, 28 мар. 2016

gammaker
нет смысла избавляться от коллизий в хешах, просто сравнивать имена со всеми элементами хеши которых совпадают, для 32битного хеша это будет не много
> Но вообще, если перейти на хэши так, чтобы не было коллизий вообще, то будет профит - 16 байт на элемент
переходя на хеши больше профит получается в скорости нежели в памяти, экономить память на битах хеша не советую

#17
17:15, 28 мар. 2016

ashujon
> нет смысла избавляться от коллизий в хешах, просто сравнивать имена со всеми
> элементами хеши которых совпадают, для 32битного хеша это будет не много
А, ну да, одинаковые хеши же будут идти подряд в сортированном файле...
Тогда вообще всё круто. Наверное даже не поленюсь и переделаю на такой вариант.
Спасибо за идею.

ashujon
> переходя на хеши больше профит получается в скорости нежели в памяти, экономить
> память на битах хеша не советую
Если у нас хеш 32 бита, то дальше экономить я бы и не стал. 12 байт на элемент в индексе - уже и так отлично. Можно даже ещё сэкономить, урезав смещение до 5-6 байт.

#18
17:35, 28 мар. 2016

gammaker

Сделай самую простую хеш-мапу, в которой берётся хеш по модулю и распихивается в бины массива.
Хеш чуть посложнее и O1 у тебя в кармане.

#19
18:41, 28 мар. 2016

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

#20
18:54, 28 мар. 2016

}:+()___ [Smile]
> Если словарь статичный, то можно использовать хэш-функцию со свободным
> параметром и на этапе подготовки выбрать его так, чтобы не было коллизий.
Да, только наверное надо перебрать дофига вариантов, чтобы при 10 000 000 элементов 32-битный хэш нигде не дал коллизий. Если вообще такой вариант попадётся.
А вот с 64-битным скорее всего сразу без коллизий будет.

#21
18:58, 28 мар. 2016

gammaker
Так вроде куча же алгоритмов perfect hashing для статического набора данных, некоторые шустрые.

#22
19:02, 28 мар. 2016

FordPerfect
> Так вроде куча же алгоритмов perfect hashing для статического набора данных,
> некоторые шустрые.
А что, есть что-то круче тупого перебора всех параметров и проверки отсутствия коллизий?

#23
19:10, 28 мар. 2016

Ну вот здесь, например, упоминается статья:
http://cmph.sourceforge.net/papers/chm92.pdf
Не разбирался.

http://cmph.sourceforge.net/


Это то, что сходу нагуглилось/вспомнилось.

#24
15:55, 31 мар. 2016

mmap (MapViewOfFile)
В начало/конец положи дерево или линейный хеш для поиска.

(ну или просто возьми какую-нибудь базу топорную, типа leveldb)

#25
16:23, 31 мар. 2016

Fla
> (ну или просто возьми какую-нибудь базу топорную, типа leveldb)
Предлагали ж уже. Взять sqlite и вбить таблицу адресов туда.

Страницы: 1 2
ПрограммированиеФорумОбщее

Тема в архиве.