Hledani ve velkem souboru dat

[Šerých Jakub]

A je třeba se dívat do 5ti sekundového intervalu například rok starých dat? Pokud by to byl případ řekněme detailní data za posledních 24h, menší detail za třeba týden, ještě menší detail za měsíc a celkový graf za řekněme rok, pak je to optimální úloha pro round robin databázi http://oss.oetiker.ch/rrdtool/

Jakub Šerých

> -----Original Message-----
> From: Hw-list [mailto:hw-list-bounces na list.hw.cz] On Behalf Of Martin
> Záruba
> Sent: Thursday, February 12, 2015 2:16 PM
> To: HW-news
> Subject: Re: Hledani ve velkem souboru dat
> 
> 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