Hledani ve velkem souboru dat

Galloth lordgalloth na gmail.com
Čtvrtek Únor 12 14:44:14 CET 2015


Cuckoo hashing jsou v podstatě dvě hash tabulky.

http://en.wikipedia.org/wiki/Cuckoo_hashing

Hledáte jak v klasické hash tabulce bez kolizí. Tedy maximálně dvě
zahledání na klíč (jedno v každé tabulce).

Vkládání je trochu složitější. Funguje tak, že vložíte záznam do první
tabulky. Pokud již na daném místě nějaký záznam byl, tak jej vyhodíte
(proto cuckoo - kukačka) a vložíte jej do druhé tabulky. To opakujete tak
dlouho, dokud nenajdete volné místo (pointa je, že pokaždé vyhazujete). Ony
ty hash tabulky musí být o něco větší než je počet záznamů, aby se tam dalo
vkládat bez přeuspořádání celé tabulky.

Osobně bych ale zvážil, zda to stojí za takovou práci. Protože 0,6GB soubor
máte projitý grepem za 2s. (Možná více podle disku, PC atd...) Tedy za dvě
sekundy jste určitě schopen vybrat těch svých 500 hodnot do grafu. Takže je
otázka, jestli Vám případná úspora 2s na vykreslení něco přinese.

Honza
------------- další část ---------------
HTML příloha byla odstraněna...
URL: <http://list.hw.cz/pipermail/hw-list/attachments/20150212/3876e406/attachment.html>


Další informace o konferenci Hw-list