<div dir="ltr">Tak vzhledem k novym informacim si dovolim nove poznamky:-)<div>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</div><div>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...</div><div>Marek</div></div><div class="gmail_extra"><br><div class="gmail_quote">2015-02-12 14:15 GMT+01:00 Martin Záruba <span dir="ltr"><<a href="mailto:swz@volny.cz" target="_blank">swz@volny.cz</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">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.<br>
<br>
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.<br>
<br>
Martin Záruba<br>
<br>
Dne 12.2.2015 v 14:01 Galloth napsal(a):<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">
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.<br>
<br>
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).<br>
<br>
Záleží hlavně na tom, jak často hledáte oproti tomu, tak často přidáváte záznamy.<br>
Honza<br>
<br></span>
Dne 12. února 2015 13:46 Marek Sembol <<a href="mailto:hwm.land@gmail.com" target="_blank">hwm.land@gmail.com</a> <mailto:<a href="mailto:hwm.land@gmail.com" target="_blank">hwm.land@gmail.com</a>>> napsal(a):<span class=""><br>
<br>
Predpokladam, ze v klic ma "hlucha mista" (nektere hodnoty jsou<br>
vynechany), jinak by to bylo prilis jednoduche:)<br>
No mozna by se algoritmu dalo pomoct "inteligentnejsim" delenim<br>
intervalu, ale nebude to pak plne deterministicke (vyjimecne se<br>
muze hledani i zhorsit), zalezi jak "rovnomerne" jsou rozlozene<br>
klice.<br>
Uvedu postup na prikladu. Mam treba 1000 zaznamu, prvni je 0,<br>
posledni 10000. Hledam cislo 1000. Hledam cislo v 1/10 meho<br>
rozsahu hodnot. Pokud budu vychazet z toho, ze klice jsou cca<br>
rovnomerne rozdelene, tak zkusim pokracovat v hledani ne na<br>
zaznamu 500 (polovina intervalu), ale zkusim zaznam rekneme 200<br>
(ja vim, v desetine intervalu je 100, ale cim bliz k te 100 pujdu,<br>
tim vetsi je riziko, ze mi ne nevyjde a hledana hodnota bude v<br>
"nadpolovicnim" zbytku).<br>
<br>
No a jeste vic by samozrejme pomohlo (pokud to jde) drzet si v<br>
pameti nejaky index (cim vice bodu, tim mensi interval prohledavam)<br>
Marek<br>
<br>
2015-02-12 13:19 GMT+01:00 Martin Záruba <<a href="mailto:swz@volny.cz" target="_blank">swz@volny.cz</a><br></span>
<mailto:<a href="mailto:swz@volny.cz" target="_blank">swz@volny.cz</a>>>:<span class=""><br>
<br>
Váhal jsem, zda mail označit OT:, ale jde o data z PLC, tak<br>
snad to sem patří.<br>
Mám soubor dat, který se stále doplňuje daty, přečtenými z<br>
PLC. V současnosti má cca 9 000 000 vět. Každá věta má 8 byte<br>
klíč, podle kterého je setříděn a 48 byte data, takže na disku<br>
cca 480MB . Pro nalezení potřebné věty nyní používám půlení<br>
intervalu. Existuje nějaká jiná efektivnější forma hledání?<br>
Nyní je na to třeba cca 24 skoků.<br>
<br>
-- <br>
Martin Záruba<br>
<br>
______________________________<u></u>_________________<br></span>
HW-list mailing list - sponsored by <a href="http://www.HW.cz" target="_blank">www.HW.cz</a> <<a href="http://www.HW.cz" target="_blank">http://www.HW.cz</a>><br>
<a href="mailto:Hw-list@list.hw.cz" target="_blank">Hw-list@list.hw.cz</a> <mailto:<a href="mailto:Hw-list@list.hw.cz" target="_blank">Hw-list@list.hw.cz</a>><br>
<a href="http://list.hw.cz/mailman/listinfo/hw-list" target="_blank">http://list.hw.cz/mailman/<u></u>listinfo/hw-list</a><br>
<br>
<br>
<br>
______________________________<u></u>_________________<br>
HW-list mailing list - sponsored by <a href="http://www.HW.cz" target="_blank">www.HW.cz</a> <<a href="http://www.HW.cz" target="_blank">http://www.HW.cz</a>><br>
<a href="mailto:Hw-list@list.hw.cz" target="_blank">Hw-list@list.hw.cz</a> <mailto:<a href="mailto:Hw-list@list.hw.cz" target="_blank">Hw-list@list.hw.cz</a>><span class=""><br>
<a href="http://list.hw.cz/mailman/listinfo/hw-list" target="_blank">http://list.hw.cz/mailman/<u></u>listinfo/hw-list</a><br>
<br>
<br>
<br>
<br>
______________________________<u></u>_________________<br>
HW-list mailing list - sponsored by <a href="http://www.HW.cz" target="_blank">www.HW.cz</a><br>
<a href="mailto:Hw-list@list.hw.cz" target="_blank">Hw-list@list.hw.cz</a><br>
<a href="http://list.hw.cz/mailman/listinfo/hw-list" target="_blank">http://list.hw.cz/mailman/<u></u>listinfo/hw-list</a><br>
</span></blockquote><div class="HOEnZb"><div class="h5">
<br>
______________________________<u></u>_________________<br>
HW-list mailing list - sponsored by <a href="http://www.HW.cz" target="_blank">www.HW.cz</a><br>
<a href="mailto:Hw-list@list.hw.cz" target="_blank">Hw-list@list.hw.cz</a><br>
<a href="http://list.hw.cz/mailman/listinfo/hw-list" target="_blank">http://list.hw.cz/mailman/<u></u>listinfo/hw-list</a><br>
</div></div></blockquote></div><br></div>