Hledani ve velkem souboru dat

[Galloth]

Určitě lze použít nějakou formu indexu, ale je otázkou, jestli Vám to stojí
za to. Možností může být například perfektní hashování, kdy si jednou za
čas předzpracujete data a uložíte si je do hashovací tabulky s perfektní
hash funkcí (libcmph) a metodou půlení intervalu budete prohledávat jen
přírustky.

Další možností je  např cuckoo hashing, který Vám garantuje, že najdete na
dvě zahledání (ale vložení může trvat déle).

Záleží hlavně na tom, jak často hledáte oproti tomu, tak často přidáváte
záznamy.
Honza

Dne 12. února 2015 13:46 Marek Sembol <hwm.land na gmail.com> napsal(a):

> Predpokladam, ze v klic ma "hlucha mista" (nektere hodnoty jsou
> vynechany), jinak by to bylo prilis jednoduche:)
> No mozna by se algoritmu dalo pomoct "inteligentnejsim" delenim intervalu,
> ale nebude to pak plne deterministicke (vyjimecne se muze hledani i
> zhorsit), zalezi jak "rovnomerne" jsou rozlozene klice.
> Uvedu postup na prikladu. Mam treba 1000 zaznamu, prvni je 0, posledni
> 10000. Hledam cislo 1000. Hledam cislo v 1/10 meho rozsahu hodnot. Pokud
> budu vychazet z toho, ze klice jsou cca rovnomerne rozdelene, tak zkusim
> pokracovat v hledani ne na zaznamu 500 (polovina intervalu), ale zkusim
> zaznam rekneme 200 (ja vim, v desetine intervalu je 100, ale cim bliz k te
> 100 pujdu, tim vetsi je riziko, ze mi ne nevyjde a hledana hodnota bude v
> "nadpolovicnim" zbytku).
>
> No a jeste vic by samozrejme pomohlo (pokud to jde) drzet si v pameti
> nejaky index (cim vice bodu, tim mensi interval prohledavam)
> Marek
>
> 2015-02-12 13:19 GMT+01:00 Martin Záruba <swz na volny.cz>:
>
>> Váhal jsem, zda mail označit OT:, ale jde o data z PLC, tak snad to sem
>> patří.
>> Mám soubor dat, který se stále doplňuje daty, přečtenými z PLC. V
>> současnosti má cca 9 000 000 vět. Každá věta má 8 byte klíč, podle kterého
>> je setříděn a 48 byte data, takže na disku cca 480MB . Pro nalezení
>> potřebné věty nyní používám půlení intervalu. Existuje nějaká jiná
>> efektivnější forma hledání? Nyní je na to třeba cca 24 skoků.
>>
>> --
>>
>> Martin Záruba
>>
>> _______________________________________________
>> HW-list mailing list  -  sponsored by www.HW.cz
>> Hw-list na list.hw.cz
>> http://list.hw.cz/mailman/listinfo/hw-list
>>
>
>
> _______________________________________________
> HW-list mailing list  -  sponsored by www.HW.cz
> Hw-list na list.hw.cz
> http://list.hw.cz/mailman/listinfo/hw-list
>
>
------------- další část ---------------
HTML příloha byla odstraněna...
URL: <http://list.hw.cz/pipermail/hw-list/attachments/20150212/f1c7c92e/attachment.html>