Hledani ve velkem souboru dat

Čtvrtek Únor 12 15:00:17 CET 2015

Tak vzhledem k novym informacim si dovolim nove poznamky:-)
1) u grafu casto plati, ze uzivatel se mnohem casteji diva na "cerstva"
data nez na "hodne prachem zapadana" - a dle toho jde taky pracovat s
"indexem v pameti". A proste starsi data budou o neco pomalejsi. Ale jak
rikam - neplati to vzdy
2) to tvrzeni 500x24 nepovazuji za spravne. Pri hledani prvni hodnoty to
mate 24 cteni - ale nikdo vas nenuti ty hodnoty zahodit! Proste pri hledani
hodnot si dynamicky tvorim index, ktery nasledne (kdyz mam hotovo 500
hodnot) kldine zahodim. Z prvniho cteni mam (minimalne) hodnotu v polovine
zaznamu. Takze druhou hodnotu nehledam v celem intervalu, ale (v tom horsim
pripade - lezi v jine polovine celeho rozsahu nez prvni hledana) v polovine
intervalu). A s kazdou dalsi hodnotou se bude situace zlepsovat...
Marek

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

> Vzorky se přidávají každých cca 5 vteřin, podle toho jak PLC stíhá nebo
> zda to nezdrží průchod paketu internetem (PLC je u zákazníka). Program pak
> z dat vytváří graf, přičemž je potřeba přečíst cca 500 vzorků, ale krok
> mezi nimi záleží na zvoleném roztažení vodorovné (časové) osy. Takže to
> klasické půlení opakované 500x je již znát.
>
> Můžete mi přiblížit, co je cuckoo hashing (jsem zcela neposkvrněn věděním
> v této oblasti). Při vkládání dat má PC hromadu času, další vzorek je cca
> za 5 vteřin.
>
> Martin Záruba
>
> Dne 12.2.2015 v 14:01 Galloth napsal(a):
>
>> 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 <mailto:
>> 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
>>     <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 <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/2fe65bfe/attachment.html>