Hledani ve velkem souboru dat
Tomáš Hamouz
hamouz na divesoft.cz
Čtvrtek Únor 12 14:23:59 CET 2015
A nešlo by to optimalizovat tak, že v požadavku na zobrazení by bylo
měřítko? Pak stačí najít krajní bod na 24 půlení a zbylé hledat
relativně k prvnímu, se znalostí "jak asi daleko" bude.
Tomáš
> 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ší informace o konferenci Hw-list