Hledani ve velkem souboru dat

[Martin Záruba]

V podstate tak to dělám. Jenže pokud se nemýlím, tak počet skoků je 
úměrný logaritmu počtu vzorků při základu 2. Takže nejpomalejší je to 
"konečné dohledání". Ale jak psal pan Sembol, je fakt, že poslední kroky 
spadají často do stejného sektoru na disku, takže jsou již v paměti. Je 
to výrazně znát, pokud dáte znova zobrazit to samé, disk se nerozsvítí, 
viditelně všechny sektory, kde se hledalo jsou již v paměti.

Martin Záruba

Dne 12.2.2015 v 14:23 Tomáš Hamouz napsal(a):
> 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
> _______________________________________________
> HW-list mailing list  -  sponsored by www.HW.cz
> Hw-list na list.hw.cz
> http://list.hw.cz/mailman/listinfo/hw-list
>