Hledani ve velkem souboru dat

[Marek Sembol]

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
>
------------- další část ---------------
HTML příloha byla odstraněna...
URL: <http://list.hw.cz/pipermail/hw-list/attachments/20150212/e56467dd/attachment-0001.html>