|
ru.perl
- RU.PERL ----------------------------------------------------------------------
From : yurik shestakov 2:5020/400 09 Jun 2004 12:11:40
To : Mikhail Polykovsky
Subject : Re: Хэш?
--------------------------------------------------------------------------------
On Wed, Jun 09, 2004 at 07:24:44AM +0000, Mikhail Polykovsky wrote:
MP>>> У меня есть ~8 млн. уникальных строк (20 символов). Hекоторые
MP>>> дублируются. Обработка идет посторочно. Мне нужно знать, обрабатывал я
MP>>> такую строку уже, или нет. Я пробовал BerkleyDB (tie( %str,
MP>>> "DB_File", $filename)), очень долго. MySQL с одним полем и индексом по
MP>>> нему быстрее, но тоже медленно (правда я делал не select, а пытался
MP>>> insert, если не получалось, складывал в таблицу дублирующих).
MP>>> Простой хеш не помещается в памяти. Что посоветуете?
AA>> http://www.perl.com/pub/a/2004/04/08/bloom_filters.html
MP> Это конечно здорово, но вероятность ошибки, хоть и маленькая, меня
MP> нисколько не радует.
Тогда придется решать задачу на C, используя или двоичное дерево
с балансировкой при вставке (это таки хорошее время на 8 млн. записей),
или хеш. Я в таких случах пользую hash.c/hash.h из исходников Squid.
Однако следует учитывать overhead по памяти в обоих случаях (что для
btree, что для hash): 20 *8 млн ~~ 160 mbytes, плюс:
a) структура _hash_link (8 байт на запись), итого +64 mbytes,
b) собственно структура _hash_table, в которой есть buckets, которых
столько, сколько задал hash_size при инициализации hash.
Если сказал, что buckets = 8 млн, то это еще +32 mbytes.
Итого выходим на 160+32+64 = 256 mbytes.
В принципе, это приемлимо, если на машинке 512 mbytes.
--
// yurik shestakov
--- ifmail v.2.15dev5.3
* Origin: Unknown (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
Re[2]: Хэш? |
Mikhail Polykovsky |
09 Jun 2004 11:24:44 |
 Re: Хэш? |
yurik shestakov |
09 Jun 2004 12:11:40 |
 Re[2]: Хэш? |
Bulat Ziganshin |
22 Jun 2004 14:46:54 |
|
|
