Hledani ve velkem souboru dat

[Marek Sembol]

Ano, tak nejak.
Kdyby clovek sel "na krev", tak ma v pameti vsechny hodnoty indexu (9M x 8
byte == 72M a casem narusta). Pokud tam bude "kazda tisici" hodnota jak
pisete, tak nejdriv v pameti najdu interval a pak uz mam na prohledani na
disku jen 1000 hodnot, coz je (pulenim intervalu) jen 10 cteni. V praxi
jeste mene, protoze kazde cteni cte minimalne sektor tady minimalne 512
byte, coz je 9 zaznamu. Nektere disky pouzivaji tusim vetsi sektory.... S
temito faktory jde pocitat (ale program to komplikuje)
Ale proste nejvic ziskate tim indexem (a nejmensimi naklady prace)
Marek

2015-02-12 14:06 GMT+01:00 Martin Záruba <swz na volny.cz>:

> Ano, to by mohla být dobrá metoda. Vzorky jsou sice nepravidelné, ale zase
> to není tak hrozné. Index v paměti si představujete tak, že by to bylo
> pole, kde by byl např. každý tisící index, takže by sloužil "k hrubému
> najetí" na správnou pozici?
>
> Martin Záruba
>
> Dne 12.2.2015 v 13:46 Marek Sembol 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 <mailto:
>> 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 <http://www.HW.cz>
>>     Hw-list na list.hw.cz <mailto: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
>>
>
> _______________________________________________
> 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/9df1a9b0/attachment.html>