Hledani ve velkem souboru dat
Martin Záruba
swz na volny.cz
Čtvrtek Únor 12 15:34:03 CET 2015
1) mě nenapadlo. 2) to tak dělám, ale jen tak, že prohledávám vždy od
předchozího vzorku do konce, protože graf se vytváří zleva doprava, tak
jako je setříděn soubor. Ale asi by šlo udělat, odhad pravděpodobného
výskytu vzorku a tím počet kroků (většinou) snížit.
Martin Záruba
Dne 12.2.2015 v 15:00 Marek Sembol napsal(a):
> 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
> <mailto: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> <mailto: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>
> <mailto: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> <http://www.HW.cz>
> Hw-list na list.hw.cz <mailto:Hw-list na list.hw.cz>
> <mailto: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> <http://www.HW.cz>
> Hw-list na list.hw.cz <mailto:Hw-list na list.hw.cz>
> <mailto: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 <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
Další informace o konferenci Hw-list