Programatorsky dotaz: Hleda se struktura!

21.2.2009 21:31 | Přečteno: 2166× | Programování | poslední úprava: 21.2.2009 21:36

rad bych vedel jestli nekdo z vas nepotkal nejakou symapatickou datovou strukturu, ktera by splnovala moje predstavy.

jak by takova struktura mela vypadat:

• mela by pojmout data ve forme <key, value>, kde key se ve strukture vyskytuje maximalne jednou
• mnozstvi dat ulozenych na pocatku je nezname... muze to byt 10 polozek, ale i 10000 nebo 100000
• nejkritictejsi operaci je vlozeni a s tim spojene vyhledani dvojice (mely by byt co nejrychlejsi)
• dalsi a posledni operaci, kterou by to melo zvladnout je vylistovani vsech paru <key, value>
• nemelo by to samozrejme plytvat pameti
• za urcitych okolnosti by sla seslabit podminka o tom, ze key se ve strukture vyskytuje maximalne jednou

nez zacnete rikat, ze je to jednoduche... tak maly seznam kudy cesta nevede:

• spojove seznamy, setridene posloupnosti, atd. -- o tom snad nema cenu ani mluvit
• hash tabulka se separatnim retezenim -- vzhledem k predem neznamemu poctu prvku je nepouzitelna, plytvani mistem vs. hodne pomale hledani
• hash tabulka s otevrenym adresovanim -- zmena velikosti je mooooc draha operace, plytvani mistem
• ruzne stromy (AVL, RB, B) -- vyhledani a obzvlast vlozeni neni to prave orechove; i presto, ze slozitost muze byt relativne nizka, skutecne provedeni operace je casto docela pomale (alokace, vyvazeni, atp.) mimochodem, stromy taky docela plytvaji mistem...

osobne mam jedno reseni, ktere je malinko netradicni... takze predtim nez se pustim do programovani, bych rad vedel, jestli jsem nejakou strukturu neprehledl, jelikoz tipuju, ze se s podobnym problemem uz nekdo nekdy setkal.        

Komentáře

[dad]

kdyz jsem to cetl, tak jsem spontalne myslel na gtree - ale musim priznat, ze to pouzivam pouze intuitivne a vubec jsme netusil ta tvrda fakta:

• vyhledani a obzvlast vlozeni neni to prave orechove
• skutecne provedeni operace je casto docela pomale
• stromy taky docela plytvaji mistem.

 

 

[deda.jabko]

co si mam predstavit pod pojmem ,,gtree''? mate k tomu vic informaci?

jinak ta tvrda fakta jsou vynucena okolnostmi, jelikoz se jedna o cast kodu, ktera je docela vytizena, takze i ,,male zpomaleni dela velkou paseku''.

[Ash]

Nepochopil :)

[Václav HFechs Švirga]

... No kdyz to neni prave orechove, tak pres to proste vlak nejede :). K tematu neporadim.

[Jan Trávníček]

Možná by nebylo na škodu pokud se opravdu žádná optimální struktura nenajde naimplementovat kombinaci respektive vybrat tu která se nejlébe blíží výsledku a nějak zredukovat maximální počet prvků v podstruktuře například key hodnoty rozdělit do intervalů a pro tyto intervaly mít jednotlivé struktury už počet intervalů menší (v ideálním případě). Samozřejmě složitost řešení se tím neovlivní ale to jenom protože složitost se počítá pro nejhorší možný případ.

Třeba je to uplně scestný nápad a cesta do pekel ale možná ne...

[deda.jabko]

ja mam zatim vymyslene reseni jako kombinaci jedne ,,exoticke'' a jedne bezne struktury, ale abych neovlivnoval navrzena reseni, tak ho tady neuvadim.

Samozřejmě složitost řešení se tím neovlivní ale to jenom protože složitost se počítá pro nejhorší možný případ.

takto to samozrejme resi teoretici. v praxi je to se slozitosti vsechno mnohem slozitejsi...

[Vskutečnosti Saýc]

No, to jsou dobre prehnane pozadavky :) To programujete pro nejaky mikropocitac s velmi omezenym mnozstvim pameti? Jinak si to nedokazu vysvetlit, a zaroven mi pripada, ze kdyz nevite jestli bude polozek 10 nebo 100k, a kdyz nevite jak casto je nekdo prida po jedne a jak casto ne, nemate uplne dobre zvladnutou analyzu.

Nicmene.

Hashtabulky umi byt chytre, a umi se napriklad zvetsovat kdyz potrebuji. Double hashing nebo retezeni bych resil spis pokud vas zajima pomer hit time a miss time. Krom toho, pokud vase klice a hodnoty jsou neco vetsiho nez int, zabere samotna tabulka mnohem mene mista nez data na ktera ukazuje.

Pokud jde o stromy -- RB strom bych psat nechtel (z toho rebalancingu mi sla hlava kolem, kdyz jsem to naposledy delal), ale pokud najit jednu z milionu polozek v petadvaceti operacich neni "prave orechove", nejsem si jisty co je. vkladani je stejne, moc nerozumim tomu co myslite alokaci. ale netvori rebalancing prirazeni jedne nebo nekolika referenci odnekud nekam? pokud jste na architekture kde vymena intu za jiny je moc draha operace, neco je spatne.

Na druhou stranu, jsem trochu zvedavy jake datove struktury pouziva treba ten opevovany O(1) planovac v linuxu na informace o procesech, treba v tom pujde najit neco zajimaveho.

[deda.jabko]

To programujete pro nejaky mikropocitac s velmi omezenym mnozstvim pameti? Jinak si to nedokazu vysvetlit, a zaroven mi pripada, ze kdyz nevite jestli bude polozek 10 nebo 100k, a kdyz nevite jak casto je nekdo prida po jedne a jak casto ne, nemate uplne dobre zvladnutou analyzu.

je to program pro normalni i686/amd64/sparc... problem je, ze se venuju low-level vecem (jako je treba prace s pameti) a ne psani ,,ucetnictvi''... takze

a) nejsem schopen predikovat jak se bude chovat aplikace nad tim

b) ty hodnoty vychazi z realnych pozorovani

c) i male mnozstvi kodu navic dela paseku

nejsem si jisty co je. vkladani je stejne, moc nerozumim tomu co myslite alokaci.

abych mohl vlozit do stromu nejakou hodnotu musim mu alokovat uzel coz zere docela cas i misto (ono se to nezda).

vymena intu za jiny je moc draha operace

to je zase ciste teoreticky pohled... ty vymeny intu jsou spojeny s podminenymi skoky... a to jsou potvory

[Vskutečnosti Saýc]

Podminenych skoku bych se na modernich architekturach nebal, jednak si s tim procesory umi poradit (spekulativni provadeni) a druhak penalizace za spatne odhadkuty podmineny skok je dva tri rady mensi nez penalizace za cache miss, a pokud tech polozek bude hodne a nevejdou se do cache, nemusite se podminenymi skoky vubec vzrusovat ;)

Jinak, ohledne dobre vymyslene prace s pameti se jde podivat dovnitr memcached.

[deda.jabko]

Podminenych skoku bych se na modernich architekturach nebal, jednak si s tim procesory umi poradit (spekulativni provadeni)

treba takovy sparc s tim ma zasadni potize.

[Vskutečnosti Saýc]

Nestalo by za to odprofilovat ten kod a pouzit statickou predikci, kterou SPARC mel, kdyz jsem pro nej naposledy programoval? Ale argument o skryte pameti porad stoji. Proc optimalizovat cast kodu ktera na vykon nema vliv?

[Jardík]

Krom toho, pokud vase klice a hodnoty jsou neco vetsiho nez int, zabere samotna tabulka mnohem mene mista nez data na ktera ukazuje.

Pokud jsem dobře pochopil, co myslíte, tak žijete v paralelním vesmíru, kde je pointer všude stejně veliký jako int.

[Vskutečnosti Saýc]

To jste to nepochopil dobre ;)

[pht]

Na druhou stranu, jsem trochu zvedavy jake datove struktury pouziva treba ten opevovany O(1) planovac v linuxu na informace o procesech, treba v tom pujde najit neco zajimaveho.

Pokud vím, tak používá několik spojových seznamů, do kterých si řadí procesy dle dynamické priority.

[Vskutečnosti Saýc]

To dava smysl. Videl jsem na tohle viceurovnove hash tabulky, ale uz si nevzpominam kde.

[hikikomori82]

"premature optimization is root of all evil"

proste pouzi jednorozmerne pole a sekvencne vyhladavanie a ked budes mat realne data tak to optimalizuj az potom

[deda.jabko]

muzu te uklidnit, problem s ,,premature optimization'' ani s nicim podobnym nemam. ty pozadavky vychazi z realnych pozorovani na funkcnim programu.

[alblaho]

A není to jedno? Na nějakých blbých 100k prvků?

Asi bude celkem jedno, jestli to bude nějaký rozumný strom nebo třeba scatter-index hashtabulka.

Evidentně máš slušné znalosti, takže vyloženě vedle asi nešlápneš. Spíš mám pocit, že se už teď dopouštíš předčasné optimalizace, tedy pokud to nebude běžet na něčem co má pod 100 MHz a pět megabajtů paměti.

[Deleted [8409]]

Pokud jde o C++ a chcete jinou hash table než tu v stl, tak mám v záložkách google sparsehash.

[deda.jabko]

C++ nepouzivam... ale diky, mrknu se co pouzivaji za triky

[Martin Böhm]

Která hash table je v STL?

[AraxoN]

Možno keby si povedal niečo viac o tom, z akej množiny budú keys... Ale myslím, že ako prvé by som sa pozrel, či sa nedá použiť Berkley DB a až potom, keby to zlyhalo by som začal uvažovať, že budem implementovať nejakú svoju divotvornú štruktúru.

[deda.jabko]

ja, a to je moje zvlastnost, si datove struktury zasadne pisu sam.

[AraxoN]

NIH syndróm? :-P

Ak sú kľúčom vždy dva pointery rovnakej dĺžky, a ak hovoríme o architektúre, kde sú pointery rôzne od int čo implikuje viac RAM, tak ja osobne by som spravil to, že by som kľúč rozsekal na menšie kúsky, napríklad po 16 bitov a pre každý kúsok si spravil jednu úroveň index tabuliek, kde by ako index išlo rovno tých 16 bitov. Tabuľka z prvej úrovne by sa potom odkazovala na tabuľky druhej úrovne, kde by ako index išlo druhých 16 bitov, a tak dookola až po úroveň poslednú, ktorá by sa potom odkazovala (alebo obsahovala) už priamo výsledné dáta. Pri málo záznamoch (100k) by to pravdepodobne zožralo dosť RAM, pričom väčšina tých tabuliek by obsahovala skoro samé NULL, ale na druhej strane výpočtová zložitosť operácií je konštantná, a žiadne podmienené skoky sa nekonajú, len priamy výber z poľa. Dokonca aj to preliezanie po rôznych úrovniach by sa dalo unloopnuť z cyklu do slíža inštrukcií.

[deda.jabko]

NIH syndróm? :-P

ne, jenomze pritom, co delam si nemuzu dovolit ten komfort pouzivat (cizi) knihovny

Pri málo záznamoch (100k) by to pravdepodobne zožralo dosť RAM

a ted je tech tabulek v RAM soucasne treba dvacet nebo tricet... uff... to je jeden z duvodu, proc v mem pripade delaji hash tabulky potize...

[Josef Kufner]

Pokud se budou klice pohybovat v nejakem rozumnem rozmezi... treba 0 az milion, dalo by se alokovat proste pole pointeru na hodnotu. Vlozeni ma jednotkovou slozitost, hledani taky.

Problem by mohl byt, pokud by klice byly prilis ridce rozptyleny v prilis velikem prostoru, ale tomu by se mohlo dat zabranit pouzitim mapovaci funkce. Tady hodne zalezi na povaze dat.

Ale jinak... pri milionu moznych klicu mas 4MB na index (to pole pointeru) + data. To na dnesni pomery neni mnoho. A kdyz vemu v uvahu rychlost a jednoduchost implementace...

[Josef Kufner]

No pokud jsou klíčem dva pointery, tak lze předpokládat, že ty pointery budou ukazovat do nějakého relativně malého prostoru -- že jádro bude programu dávat aspoň trošku souvislé bloky a nebude každá položka někde úplně jinde.

Takže ta mapovací funkce by mohla rozebrat klíči adresovatelný prostor na bloky, třeba po půl MB a pokud se nový klíč netrefí do již alokovaného bloku, tak ho alokovat. Tím se omezí spotřeba paměti na přijatelnou mez a na rychlosti se to prakticky neprojeví.

[Petr]

trie?

[deda.jabko]

trie jsou zajimave... i kdyz pro muj pripad potrebuji asi malinko priohnout...

[Martin Mareš]

Velmi záleží na tom, co je klíč – jestli číslo z rozumného rozsahu nebo nějaký variabilně dlouhý řetězec.

Hashovací tabulky se separovanými řetězci bych každopádně nezatracoval. Pokud začnete s malou tabulkou a pokaždé, když se naplní, ji zdvojnásobíte a vše přehashujete, bude mít přehashovávání v přepočtu na jedno vložení prvku konstantní složitost.

[deda.jabko]

Velmi záleží na tom, co je klíč – jestli číslo z rozumného rozsahu nebo nějaký variabilně dlouhý řetězec.

rozumny dotaz. klice jsou dva pointery. ...i kdyz je za nema skryta dalsi logika, nema smysl ji do toho tahat...

Pokud začnete s malou tabulkou a pokaždé, když se naplní, ji zdvojnásobíte a vše přehashujete

tak treba toto reseni je lepsi nez nejaky spojovy seznam, ale v mem pripade nikam nevede, protoze s vetsima tabulkama se to zacne realne chovat mizerne...

[Martin Mareš]

tak treba toto reseni je lepsi nez nejaky spojovy seznam, ale v mem pripade nikam nevede, protoze s vetsima tabulkama se to zacne realne chovat mizerne...

Opravdu jste to zkoušel? Zejména pokud je struktura, jak zmiňujete jinde, téměř write-only, měla by se taková hashovací tabulka chovat velmi dobře. Ještě ji jde upravit tak, aby se lépe cacheovala: přihrádky nebudou přímo seznamy položek, ale seznamy bloků velkých jako řádek cache, ve kterých bude několik položek.

[xyz]

Nevymýšlej blbosti, použij knihovní RB strom nebo hashtable a hotovo -- jakákoli pomalost toho co jsi napsal nebude kvůli struktuře (tuplem ne když mluvíš o nějakých 100k prvcích).

[Filip Jirsák]

Na to, jak specifické máte požadavky, jste toho napsal moc málo. Když vylučujete hashovací tabulky nebo stromy, pravděpodobně máte ještě dost dalších informací, které jste do zápisku nenapsal. Možná víte něco o náhodnosti rozložení vkládaných klíčů; možná víte něco o náhodnosti pořadí vkládání klíčů; možná víte, že počet hodnot nebude kdekoli mezi 10 a milionem, ale bude to buď asi deset, nebo asi tisíc, nebo asi milion; možná víte, že pár nějakých hodnot hodnot se bude vkládat mnohem častěji, než ostatní; možná víte, že je nějak omezena množina klíčů. S ohledem na znalost dalších informací je pak možné navrhnout nějakou lepší datovou strukturu postavenou na míru vašemu problému. Zatím je to svou obecností pouze dotaz „hledáme strukturu, která je lepší než hashtabulka a strom dohromady; teoretikové za ty desítky let zatím nic neobjevili, tak schválně, jestli se chytíte vy, já už jsem na něco přišel, ale neprozradím to“. Možná jste to tak nemyslel, ale zápisek tak vyznívá.

[microcz]

+1 ...pokud by autoři kontejnerových datových typů běžných jazyků měli prostředky k tomu jak je zefektivnit, určitě by to již dávno udělali, tedy jak napsal Filip prostor pro optimalizace vzniká konkretizací požadavků

[deda.jabko]

Možná víte něco o náhodnosti rozložení vkládaných klíčů; možná víte něco o náhodnosti pořadí vkládání klíčů;

moc toho nevim... jelikoz se jedna o pointry... tak je pravdepodobne, ze obcas se budou objevovat skupiny blizkych hodnot... ale jak blizkych, jakych hodnot a jak casto nelze predem odhadnout

možná víte, že počet hodnot nebude kdekoli mezi 10 a milionem

uz jsem psal o nejaky prispevek vyse: nevim.

víte, že pár nějakých hodnot hodnot se bude vkládat mnohem častěji, než ostatní;

muze to nastat, ale nelze urcit predem.

teoretikové za ty desítky let zatím nic neobjevili

jo, jenomze to neni problem ciste teoreticky...

navic jestli jste cetl pozorne... mne jde o strukturu, ktera je vicemene write-only...

[Jary]

Write only? Tak to vřele doporučuji strukturu /dev/null.
To čtení má vracet data nějak seřazená? Nebo ti jde o náhodný přístup ke kterémukoliv prvku?

[Ladicek]

Judy Array?

[deda.jabko]

diky, to jsem neznal... i kdyz reimplementovat se mi to teda nechce.

[Ladicek]

Reimplementovat takovou šílenost by mohl jenom blázen Mne by spíš zajímalo, jak to doopravdy funguje. Tohle porovnání je takové ambivalentní, a jinak vím jenom tolik, že se to používá v Erlang ETS Table.

[Ladicek]

jak to doopravdy funguje

Myslím jestli to doopravdy funguje, resp. jestli to má opravdu znatelný přínos.

[HS]

Byt mnou, tak bych zvolil AVL strom.  Nic lepsiho me nenapada. Mozna B stromy by byl lepsi, ale zalezelo by na konkretnich datech.  Jinak jsem zvedav s im novym prides.

 

[Martin Mareš]

Velmi záleží na tom, jestli má struktura udržovat uspořádání nebo ne. Pokud ano, chová se obvykle velmi dobře B-strom nastavený tak, aby se jeden vrchol vešel přesně do jednoho řádku cache; pokud nikoliv, vedou většinou hashovací tabulky.

Pokud je struktura dost velká (tj. nevejde se do cache), v podstatě jediné, na čem její efektivita záleží, je počet přístupů do paměti. Tam hashovací tabulky se separovanými řetězci jasně vedou (v průměru dva přístupy), zatímco strom jich má v průměru logaritmický počet (minus konstanta za vršek stromu, který se ucacheuje, případně děleno konstanta, pokud zvolíte chytřejší uložení stromu, třeba van Emde-Boasovo, které se ale docela těžko udržuje dynamicky).

[Semo]

Pokial je to ale blizke velkosti RAM, tak zase vedie strom, kvoli pamatovej uspornosti. Hash veduci na disk nikoho nepotesi.

[Martin Mareš]

Tomu nerozumím. Proč by hashovací tabulka měla zabírat víc paměti než strom? Obvykle tomu bývá naopak

[default]

• Java Collections
• Apache Commons Collections

[Martin Mareš]

Řekl bych, že tazatel měl zájem o něco rychlého, čímž je Java jaksi mimo hru

[Jardík]

Hlavně by mu to sežralo o 100MB víc paměti

[Filip Jirsák]

To jako že by to JIT zkompiloval za běhu optimálně pro cílovou architekturu a navíc optimálně podle typu využití, což optimalizátor C v době kompilace udělat nemůže (pokud nemá křišťálovou kouli), a tímhle „podvodem“ by mohla Java nakonec zvítězit, tak je nutné ji diskvalifikovat rovnou na startu? Ono pokud jde o ukazatele, tak se dá čekat, že to Java nebude, a běžné datové struktury, které Java Collections API nabízí, autor blogu zavrhl hned na začátku – ale ta rychlost asi zrovna nejlepší protiargument nebude…

[Martin Mareš]

Ano, just-in-time kompilátory mají teoreticky šanci produkovat výrazně lepší kód než statické kompilátory, ale v praxi to zatím jaksi nedovedou. Mimo jiné se jim to nedaří proto, že optimalizují malé kousky kódu, neb za běhu není na velké globální optimalizace čas. Jinak i co se JITů týče, daleko víc než na Javu bych sázel na LLVM nebo na Parrota.

[Filip Jirsák]

Nicméně pro běžné použití™ jsou už dnešní rozumné virtuální stroje (mezi které počítám i Sunovské JVM) natolik výkonné, že aplikaci bude zdržovat s největší pravděpodobností něco jiného, než interpretace bajtkódu nebo JIT kompilace. A pak existují samozřejmě výjimky, což je asi případ tohoto zápisku, kde je potřeba optimalizovat jednotlivé instrukce, velikost cache atd. Problém toho klišé, že Java je pomalá, je taky v tom, že to vytváří dojem, že rychlost výsledného programu závisí na tom, zda to bude nějaký interpretovaný jazyk nebo C/C++. Běžný programátor ale daleko víc zkazí výběrem špatného algoritmu nebo špatným vícecláknovým zpracováním, než tím, že si nezvolí C.

[podlesh]

Tak schválně, nakolik se to teď rozmázne? Já myslím že je zaděláno na pěkný stopříspěvkový flamewar. Samozřejmě zcela offtopic, protože autor blogu se pohybuje jaksi na zcela jiné úrovni.

[Ondrej 'SanTiago' Zajicek]

No nevhodny algoritmus urcite muze program zkazit vyrazne hur, na druhou stranu ve znacne casti programu neni problem mit program z algoritmickeho hlediska (asymptoticky) optimalni, protoze v nem proste zadne algoritmicky slozite problemy nejsou. A tam uz pouziti interpretovaneho jazyka je znacny rozdil.

[Michal Vyskočil]

Jinak i co se JITů týče, daleko víc než na Javu bych sázel na LLVM nebo na Parrota.

Mohu se zeptat proč? Přeci jenom jsou možnosti Sunu investovat do vývoje JVM poněkud větší, než možnosti organizací stojící za LVVM, nebo Parrotem.

Ale, LVVM se už ve spojitosti s JVM používá Zero Shark FAQ, i když jenom experimentálně. Ale důvodem je možnost portace OpenJDK na ne-x86 platformy. I kdyby LVVM v budoucnu dokázal dělat lepší JIT, než je současný HotSpot, asi by nebyl takový problém ho začít jednoduše používat.

[Martin Mareš]

Mohu se zeptat proč?

Jak LLVM, tak Parrot mi hlavně přijdou daleko lépe navržené než JVM. Ale zvláště Parrotovi ještě asi bude pár let trvat než do svého potenciálu doroste. Uvidíme, už se docela těším

Přeci jenom jsou možnosti Sunu investovat do vývoje JVM poněkud větší, než možnosti organizací stojící za LVVM, nebo Parrotem.

Životaschopnost návrhu většinou závisí daleko víc na jiných věcech než na investicích

[Deleted [8409]]

Obávám se, že s tím Parrotem a LLVM jste to poněkud přestřelil

Parrot je VM pro dynamicky typované jazyky, které musí být už logicky pomalejší, než ty staticky typované. LLVM je zase low level virtual machine, kde základní typ proměnné je 'double'. Myslím si, že Parrot i LLVM mají svůj význam, ale srovnávat je něčím tak komplexním jako je JVM bych se nepokoušel.

[Martin Mareš]

Parrot je pro dynamicky typované jazyky, ale dynamické typování je spíše rozšířením než něčím, co by přeložený kód nutně brzdilo. Naopak jeho registrová architektura se daleko lépe zpracovává než zásobníková JVM.

Co se LLVM a typů týče, doporučuji mrknout se na zvěřinec jeho typů, je rozhodně daleko bohatší, než píšete.

Já ostatně neříkám, že JVM není komplexní, jen tvrdím, že kód, který z něj padá, nestojí za příliš a že jiní mají lepší šance.

[Ladicek]

Když jsem četl popis Parrotu, říkal jsem si (nemyslím to vážně): to mi ještě něco říkejte o registrových architekturách, když to má čtyři zásobníky!

Registrové stroje jsou v poslední době oblíbenější, ale mají proti zásobníkovým i nevýhody. Pokud vím, překlad zásobníkového kódu do strojového (registrového) se dá docela dobře optimalizovat (eh, vždyť zásobníkový kód se dá použít i jako mezikód v překladači, i když netuším, jestli to dneska někdo dělá), ovšem hodnotit výsledky JIT překladu HotSpotu se neodvažuju.

[Martin Mareš]

Jaké nevýhody vlastně registrové stroje mají?

[Ladicek]

Záleží na tom, co kdo považuje za nevýhody Delší a pomalejší instrukce, větší a složitější kód, v zásadě.

[Deleted [8409]]

Je ale zajímavé, že i v tutoriálu používají například toto:

//===----------------------------------------------------------------------===//
// "Library" functions that can be "extern'd" from user code.
//===----------------------------------------------------------------------===//

/// putchard - putchar that takes a double and returns 0.
extern "C" 
double putchard(double X) {
  putchar((char)X);
  return 0;
}

Oni berou double totiž jako výchozí typ pro importování funkcí. Ale jinak máte pravdu, těch typů je tam celkem hodně.

[xkucf03]

Tazatel nenapsal dostatek podrobností, takže se ostatní mohou leda domýšlet… A že se jedná o nějakou nízkoúrovňovou/systémovou záležitost a ne aplikační z něj vylezlo až v komentářích.

[deda.jabko]

vic podrobnosti jsem nechtel psat, protoze bych musel jit do vyraznejsich detailu, coz by za prve popis jeste vic zkomplikovalo. za druhe by me do toho jeste vic lidi zacalo kafrat, jak mam programovat... viz nekolik poznamek o predcasnych optimalizacich, atp.

[deda.jabko]

dekuju, vsem za prispevky... dovolim si mensi shrnuti....

prosel jsem si diskuzi a me zavery jsou nasledujici:

• 10 % prislo s nejakym zajimavym napadem
• 15 % si mysli, ze mam pouzit nejakou knihovnu
• 20 % si mysli, ze jsem idiot a bud nevim co chcu, nebo si moc vymyslim

a ted moje navrhovane reseni...

prvni: horni bity usporadat do binarni trie tvorici jen maly strom, ktery ma v listech hash tabulky a v nich zaznamy rozhozene podle dolnich bitu, takze objekty jsou blizko sebe z cehoz by cache asi mela radost a neplytvalo by to mistem.

druhe: (pouzite reseni) left-leaning red-black tree poskladany v tabulce. vyhoda LLRB proti klasickym RB je, ze jsou opravdu, ale opravdu jednodussi, pri zachovani vsech featur. poskladat strom do tabulky/tabulek ma tu vyhodu, ze se misto jednotlivych uzlu, alokuje cela skupina uzlu... -> eliminuji se cas i misto, ktere je potreba k alokaci jednoho samostatneho uzlu. diky poskladani do tabulky, jde vylistovani provest v konstantni pameti! jako bonus, to neplytva mistem a u mensich stromu jsou uzly blizko sebe. ...proste (cela implementace ma asi 40 radku), ale ucinne!

[Ondrej 'SanTiago' Zajicek]

> horni bity usporadat do binarni trie tvorici jen maly strom, ktery ma v listech hash tabulky a v nich zaznamy rozhozene podle dolnich bitu, takze objekty jsou blizko sebe z cehoz by cache asi mela radost a neplytvalo by to mistem.

Tipuji, ze pokud by ten klic byl z rovnomerneho rozdeleni, tak by tohle moc pameti neusetrilo.

> eliminuji se cas i misto, ktere je potreba k alokaci jednoho samostatneho uzlu.

Eliminace techto veci se casto resi tim, ze se vrcholy alokuji jednoduchym fixed-size alokatorem. Ma tve reseni proti tomu jeste nejakou vyhodu?

[deda.jabko]

Tipuji, ze pokud by ten klic byl z rovnomerneho rozdeleni, tak by tohle moc pameti neusetrilo.

jo, jenomze to jsou pointery, tak to bude mit tendenci hledat shluky dat alokovanych blizko sebe.

Eliminace techto veci se casto resi tim, ze se vrcholy alokuji jednoduchym fixed-size alokatorem.

co si mam predstavit pod pojmem fixed-size alokator?

Ma tve reseni proti tomu jeste nejakou vyhodu?

ve srovnani s cim?

[Ondrej 'SanTiago' Zajicek]

> jo, jenomze to jsou pointery

Ty by snad sly take nejakou jednoduchou hashovaci funkci zrovnomernit.

> co si mam predstavit pod pojmem fixed-size alokator?

Pomocny alokator, ktery alokuje bloky pevne velikosti (od systemu si necha pridelit velky blok pameti a s nim si hospodari). Rychlost velka, rezie minimalni.

[deda.jabko]

Pomocny alokator, ktery alokuje bloky pevne velikosti (od systemu si necha pridelit velky blok pameti a s nim si hospodari). Rychlost velka, rezie minimalni.

preskladani stromu do tabulky je de facto uplne to same. s tim, ze to ma i sva pozitiva... zpracovani nejake operace nad vsema prvkama jde provest v jednoduche smycce misto rekurizvniho prohledavani stromu. jednotlive uzly na sebe nemusi odkazovat pointrama, i.e., i 64bitech jde mit 32bit odkazy.

[Josef Kufner]

Btw, co těch 55 % ?

[Vskutečnosti Saýc]

Treba je to offtopic. Jako tenhle prispevek ;)

[Filip Jirsák]

Když zjistili, že se jedná o pointery a tedy se dá předpokládat shlukování klíčů, usoudili, že řešení jsou dvě -- hashovací tabulka podle nějakého prefixu klíče a strom. Zjistili tedy, že řešení existuje, a šli přihodit polínko do nějakého flameware.

[Martin Mareš]

LLRB tree je hezký nápad, ale stejně moc nevěřím tomu, že by mohly být rychlejší než slušně napsaná hashovací tabulka (viz můj argument o přístupech do paměti kdesi výše).

Mimochodem, libovolný vyhledávací strom lze vylistovat v konstantní paměti, má-li uloženy pointery na otce.

[deda.jabko]

tu hash tabulku jsem opravdu implementovanou mel (oba dva typy)... a nechovalo se to hezky pri vetsich objemech dat ... tipuju na problemy s lokalitou + asi rezie na preskladani.

[Ladicek]

To by mne vůbec zajímalo, proč si každý dynamicky typovaný jazyk implementuje vlastní hashovací tabulku (nebo ty ten LLRB strom – btw díky za tip, tuhle strukturu jsem neznal). V Beautiful Code je třeba kapitola, jak to dělali v Pythonu. To opravdu není možné použít nějakou knihovnu (když pominu nutkání všechno si psát sám)? Nebo se to tolik výkonnostně vyplatí?

[deda.jabko]

ono se to docela vyplati...

a) napsat jednoduchou strukturu nezabere tolik mista/casu

b) jde to prizpusobit danym podminkam presne na miru

c) kdyz mas strukturu primo soucasti kodu umoznuje to prekladaci delat zasadni optimalizace jako inlining... a pokud tu strukturu pouzivas opravdu intenzivne (par milionu volani)... tak se to opravdu pozna...

d) pythonisti jsou loseri ;-]

[Martin Mareš]

Já se právě ptám proto, že jsem před časem naměřil pravý opak – srovnával jsem různé stromy s různými hashovacími tabulkami a hashování vyhrávalo na celé čáře. Stromy nicméně mohou být rychlejší, pokud jsou dotazy rozložené nerovnoměrně a koncentrované spíš do intervalů. Tam se projeví lokalita. Naopak pokud jsou dotazy více méně náhodné, lokalita vůbec nepomůže a mnohem lépe se chová hashování.

Mimochodem, pokud mají dotazy takový charakter, mohl by daleko lépe než RB strom dopadnout starý dobrý Splay strom.

[deda.jabko]

testovani algoritmu muze byt casto zavadejici, protoze nasimulovat realny beh je docela komplikovana zalezitost... a kazda aplikace se chova trochu jinak...

ja jsem uz nekolikrat zazil, ze se mi program choval na ruznych pocitach uplne jinak. a dokonce jsem nekolikrat videl, ze stacilo v jedne strukture preskladat poradi prvku a program se rapidne zrychlil...

[Martin Mareš]

Inu, to vím moc dobře, to mé testování také nebyl žádný syntetický benchmark, nýbrž zcela reálný program s dost komplikovanými access patterny (jako obvykle kus indexeru od Sherlocka).

[xkucf03]

BTW: když už si napíšeš vlastní strukturu, bude z ní veřejně dostupná knihovna, nebo si ji necháš pro sebe? Jde mi o to, že určitě nejsi jediný na světě, kdo stojí před tímhle problémem, tudíž buď:

1. řešení už existuje, někdo to už napsal a jen o tom nevíš
2. tvoje řešení by se mohlo hodit i někomu jinému (OSS projekty)

[deda.jabko]

moje reseni je bohuzel zadratovane uprostred programu...

ale hodim sem mensi blogspot o LLRB.

[...]

Co nejaka halda?

[zde]

Mě se hrozně líbí implementace hashtable v lua- nemusí se plýtvat místem na malém fill factoru, a přitom to nedegraduje.