abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
včera 21:17 | Komunita
Evropský parlament schválil návrh rozpočtu EU na rok 2015. V návrhu rozpočtu (pdf) je zmíněn i svobodný software. Milion eur je naplánováno na "Pilotní projekt – Správa a kvalita softwarového kódu – audit svobodného softwaru a softwaru s otevřeným zdrojovým kódem". Dalších půl milionu eur je naplánováno na "Pilotní projekt – Prosazování otevřených propojitelných dat, svobodného softwaru a účasti občanské společnosti při tvorbě právních předpisů v EU (otevřená propojitelná data AT4AM/LEOS a integrace svobodného softwaru)".
Ladislav Hagara | Komentářů: 3
včera 21:17 | Bezpečnostní upozornění
Bezpečnostní tým společnosti Google nalezl několik zranitelností v ntpd verzích nižších než 4.2.8. Jedna z těchto zranitelností může vést až ke spuštění libovolného kódu. Několik z těchto zranitelností již bylo aktivně exploitováno. Doporučuje se co nejdříve provést aktualizaci. [CSIRT.CZ]
Ladislav Hagara | Komentářů: 0
včera 00:30 | Nová verze
Po více než 10 letech vývoje vyšel NetworkManager 1.0.0, sada nástrojů pro správu síťových připojení. Nejnovější verze přichází například s novou klientskou knihovnou libnm, novým DHCP klientem nebo vylepšeným nmcli.
Ladislav Hagara | Komentářů: 20
19.12. 02:09 | Komunita
V listopadu přešla Wikimedia z Bugzilly na Phabricator. K migraci se v příspěvku na svém blogu vrací André Klapper. Bugzilla byla používána 10 let. Vloženo bylo 73681 oznámení. Registrováno bylo přibližně 20000 uživatelských účtů. Porovnání Bugzilly s Phabricatorem na stránkách MediaWiki.
Ladislav Hagara | Komentářů: 83
18.12. 23:04 | Zajímavý software

Dnes vyšla na Steamu linuxová verze počítačové hry. Civilization: Beyond Earth Stalo se tak necelé dva měsíce po vydání Windows verze.Díky vánoční slevové akci lze hru na Steamu do zítřejších 19 hodin koupit s 40% slevou.

menphis | Komentářů: 14
18.12. 23:03 | Pozvánky
7. a 8.3.2015 proběhne na pražském Strahově další InstallFest. Můžete posílat náměty na přednášky nebo si rovnou svoji přednášku či svůj workshop přihlásit.
Jendа | Komentářů: 1
18.12. 23:02 | Nová verze
Laboratoře CZ.NIC vydaly ostrou verzi desktopové aplikace Datovka nesoucí označení 4. Tato verze plně nahrazuje starší Datovku 3.1 napsanou v jazyce Python. Podrobnější popis Datovky 4 a informace o rozdílech a vylepšeních naleznete na stránkách projektu nebo na blogu CZ.NIC. … více »
Vilem Sladek | Komentářů: 16
18.12. 18:00 | Nová verze
Byl vydán PostgreSQL 9.4. Nejnovější verze tohoto relačního databázového systému s otevřeným zdrojovým kódem přináší celou řadu nových vlastností a vylepšení. Zdůraznit lze například podporu nového datového typu JSONB. Podrobnosti v poznámkách k vydání.
Ladislav Hagara | Komentářů: 0
18.12. 02:30 | Nová verze
Byla vydána verze 14.12.0 KDE Aplikací (KDE Applications). Většina z nich je založena na knihovnách KDE Platform 4. Některé, například Kate, KWrite nebo Konsole, jsou už ale založené na KDE Frameworks 5. Podrobnosti v kompletním seznamu změn a na stránce s dalšími informacemi. Před několika dny vyšly také knihovny KDE Frameworks 5.5.0 a prostředí KDE Plasma 5.1.2.
Ladislav Hagara | Komentářů: 23
18.12. 02:30 | Bezpečnostní upozornění
Organizace ICANN se stala terčem spear phishingového útoku, při kterém útočníci získali přístup do několika zaměstnaneckých e-mailů. Následně získali administrátorský přístup také do aplikace "Centralized Zone Data System". Z tohoto důvodu byla hesla na účtech uživatelů CZDS deaktivována a uživatelé si musí požádat o reset hesla. Zároveň se uživatelům doporučuje provést změnu hesla i v dalších systémech, pokud někde používali stejné přihlašovací údaje. [CSIRT.CZ]
Ladislav Hagara | Komentářů: 8
Disketu jsem naposledy použil během
 (46%)
 (3%)
 (11%)
 (37%)
 (3%)
Celkem 1620 hlasů
 Komentářů: 54, poslední 9.12. 17:16
    Rozcestník
    Reklama
    Autoškola testy online Levný benzín

    Programatorsky dotaz: Hleda se struktura!

    21.2.2009 21:31 | Přečteno: 1902× | 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: nez zacnete rikat, ze je to jednoduche... tak maly seznam kudy cesta nevede: 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.        

    Hodnocení: 100 %

            špatnédobré        

    Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

    Komentáře

    Vložit další komentář

    21.2.2009 22:00 dad
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!

    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.

     

     

    21.2.2009 22:36 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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''.
    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    22.2.2009 08:56 Ash | skóre: 53
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    Nepochopil :)
    21.2.2009 22:46 Václav HFechs Švirga | skóre: 26 | blog: HF | Kopřivnice
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    :-D... No kdyz to neni prave orechove, tak pres to proste vlak nejede :). K tematu neporadim.
    Baník pyčo!
    21.2.2009 22:07 Jan Trávníček | skóre: 10 | blog: ehonza | Existuje
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!

    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...

    To mess up a Linux box, you need to work at it; to mess up your Windows box, you just have to work on it.
    21.2.2009 22:50 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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...
    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    21.2.2009 23:09 Vskutečnosti Saýc | skóre: 7
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    21.2.2009 23:54 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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
    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    22.2.2009 00:59 Vskutečnosti Saýc | skóre: 7
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    22.2.2009 03:23 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    22.2.2009 12:29 Vskutečnosti Saýc | skóre: 7
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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 avatar 22.2.2009 04:35 Jardík | skóre: 40 | blog: jarda_bloguje
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    Věřím v jednoho Boha.
    22.2.2009 12:26 Vskutečnosti Saýc | skóre: 7
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    To jste to nepochopil dobre ;)
    22.2.2009 11:33 pht | skóre: 48 | blog: pht
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    In Ada the typical infinite loop would normally be terminated by detonation.
    22.2.2009 12:30 Vskutečnosti Saýc | skóre: 7
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    To dava smysl. Videl jsem na tohle viceurovnove hash tabulky, ale uz si nevzpominam kde.
    hikikomori82 avatar 21.2.2009 23:23 hikikomori82 | skóre: 18 | blog: foobar | Košice
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    "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
    21.2.2009 23:56 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    muzu te uklidnit, problem s ,,premature optimization'' ani s nicim podobnym nemam. ty pozadavky vychazi z realnych pozorovani na funkcnim programu.
    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    alblaho avatar 21.2.2009 23:31 alblaho | skóre: 17 | blog: alblog
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    22.2.2009 00:05 Deleted [8409] | skóre: 14 | blog: darkblog
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    Pokud jde o C++ a chcete jinou hash table než tu v stl, tak mám v záložkách google sparsehash.
    22.2.2009 02:29 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    C++ nepouzivam... ale diky, mrknu se co pouzivaji za triky
    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    22.2.2009 14:50 Martin Böhm | skóre: 17 | blog: Martinův stánek | Je mi to MFFUK
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    Která hash table je v STL?
    5 z 0 přetečení bufferu doporučuje Korespondenční seminář z programování (pro středoškoláky programátory).
    AraxoN avatar 22.2.2009 00:11 AraxoN | skóre: 44 | blog: slon_v_porcelane | Košice
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!

    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. :-)

    A fine is a tax for doing wrong. A tax is a fine for doing well.
    22.2.2009 02:30 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    ja, a to je moje zvlastnost, si datove struktury zasadne pisu sam.
    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    AraxoN avatar 22.2.2009 08:31 AraxoN | skóre: 44 | blog: slon_v_porcelane | Košice
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!

    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í.

    A fine is a tax for doing wrong. A tax is a fine for doing well.
    22.2.2009 09:22 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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...
    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    Josef Kufner avatar 22.2.2009 00:27 Josef Kufner | skóre: 64
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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...
    Hello world ! Segmentation fault (core dumped)
    Josef Kufner avatar 22.2.2009 11:09 Josef Kufner | skóre: 64
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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í.
    Hello world ! Segmentation fault (core dumped)
    22.2.2009 00:30 Petr
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    trie?
    22.2.2009 02:41 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    trie jsou zajimave... i kdyz pro muj pripad potrebuji asi malinko priohnout...
    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    22.2.2009 00:43 Martin Mareš
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    22.2.2009 03:13 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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...
    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    22.2.2009 10:42 Martin Mareš
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    22.2.2009 06:06 xyz
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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).
    22.2.2009 09:06 Fa & Bi | skóre: 65 | blog: Delfinárium
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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 avatar 22.2.2009 09:52 microcz | skóre: 18 | blog: Michalův zápisník | Praha
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!

    +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ů

    22.2.2009 10:08 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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...
    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    22.2.2009 11:10 Jary | skóre: 29 | blog: Jary má blog | Dům
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!

    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?

    .sig virus 3.2_cz: Prosím, okopírujte tento text do vaší patičky.
    22.2.2009 10:44 Ladicek | skóre: 28 | blog: variace | Havlíčkův brod
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    Judy Array?
    Ještě na tom nejsem tak špatně, abych četl Viewegha.
    22.2.2009 22:01 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    diky, to jsem neznal... i kdyz reimplementovat se mi to teda nechce.
    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    23.2.2009 14:54 Ladicek | skóre: 28 | blog: variace | Havlíčkův brod
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    Ještě na tom nejsem tak špatně, abych četl Viewegha.
    23.2.2009 14:55 Ladicek | skóre: 28 | blog: variace | Havlíčkův brod
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    jak to doopravdy funguje
    Myslím jestli to doopravdy funguje, resp. jestli to má opravdu znatelný přínos.
    Ještě na tom nejsem tak špatně, abych četl Viewegha.
    22.2.2009 10:54 HS | skóre: 12
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!

    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.

     

    22.2.2009 11:02 Martin Mareš
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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).
    22.2.2009 15:41 Semo | skóre: 44 | blog: Semo
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    Pokial je to ale blizke velkosti RAM, tak zase vedie strom, kvoli pamatovej uspornosti. Hash veduci na disk nikoho nepotesi.
    If you hold a Unix shell up to your ear, you can you hear the C.
    22.2.2009 16:51 Martin Mareš
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    Tomu nerozumím. Proč by hashovací tabulka měla zabírat víc paměti než strom? Obvykle tomu bývá naopak :-)
    default avatar 22.2.2009 12:09 default | skóre: 22 | Madrid
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    22.2.2009 13:45 Martin Mareš
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    Řekl bych, že tazatel měl zájem o něco rychlého, čímž je Java jaksi mimo hru :-)
    Jardík avatar 22.2.2009 15:55 Jardík | skóre: 40 | blog: jarda_bloguje
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    Hlavně by mu to sežralo o 100MB víc paměti :-)
    Věřím v jednoho Boha.
    22.2.2009 18:22 Fa & Bi | skóre: 65 | blog: Delfinárium
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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…
    22.2.2009 19:44 Martin Mareš
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    22.2.2009 21:19 Fa & Bi | skóre: 65 | blog: Delfinárium
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    22.2.2009 22:44 podlesh | skóre: 38 | Praha
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    22.2.2009 23:32 Ondrej 'SanTiago' Zajicek
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!

    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.

    23.2.2009 09:53 Michal Vyskočil | skóre: 60 | blog: miblog | Praha
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    When your hammer is C++, everything begins to look like a thumb.
    23.2.2009 23:06 Martin Mareš
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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 :-)
    23.2.2009 13:05 Deleted [8409] | skóre: 14 | blog: darkblog
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    23.2.2009 14:19 Martin Mareš
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    23.2.2009 14:46 Ladicek | skóre: 28 | blog: variace | Havlíčkův brod
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    Ještě na tom nejsem tak špatně, abych četl Viewegha.
    23.2.2009 23:03 Martin Mareš
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    Jaké nevýhody vlastně registrové stroje mají?
    24.2.2009 10:03 Ladicek | skóre: 28 | blog: variace | Havlíčkův brod
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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ě.
    Ještě na tom nejsem tak špatně, abych četl Viewegha.
    23.2.2009 15:22 Deleted [8409] | skóre: 14 | blog: darkblog
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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 avatar 23.2.2009 18:34 xkucf03 | skóre: 44 | blog: xkucf03
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!

    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.

    Mám rád, když se lidé přou, znamená to, že vědí, co dělají, a že mají směr. Frantovo.cz, SQL-Výuka.cz, Nekuřák.net
    23.2.2009 19:26 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    22.2.2009 22:59 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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!
    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    22.2.2009 23:24 Ondrej 'SanTiago' Zajicek
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!

    > 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?

    22.2.2009 23:50 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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?
    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    23.2.2009 00:30 Ondrej 'SanTiago' Zajicek
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!

    > 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.

    23.2.2009 00:46 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    Josef Kufner avatar 22.2.2009 23:47 Josef Kufner | skóre: 64
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    Btw, co těch 55 % ?
    Hello world ! Segmentation fault (core dumped)
    23.2.2009 00:08 Vskutečnosti Saýc | skóre: 7
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    Treba je to offtopic. Jako tenhle prispevek ;)
    23.2.2009 10:23 Fa & Bi | skóre: 65 | blog: Delfinárium
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    23.2.2009 08:27 Martin Mareš
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    23.2.2009 15:48 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.

    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    23.2.2009 19:15 Ladicek | skóre: 28 | blog: variace | Havlíčkův brod
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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í?
    Ještě na tom nejsem tak špatně, abych četl Viewegha.
    23.2.2009 19:41 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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 ;-]
    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    23.2.2009 23:02 Martin Mareš
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.
    24.2.2009 00:31 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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...

    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    24.2.2009 09:12 Martin Mareš
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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 avatar 23.2.2009 18:43 xkucf03 | skóre: 44 | blog: xkucf03
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!

    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)
    Mám rád, když se lidé přou, znamená to, že vědí, co dělají, a že mají směr. Frantovo.cz, SQL-Výuka.cz, Nekuřák.net
    23.2.2009 19:47 deda.jabko | skóre: 23 | blog: blog co se jmenuje "každý den jinak" | za new york city dvakrát doleva a pak už se doptáte
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    moje reseni je bohuzel zadratovane uprostred programu...

    ale hodim sem mensi blogspot o LLRB.
    Asi před rokem se dostali hackeři na servry Debianu a ukradli jim zdrojové kódy.
    23.2.2009 07:50 ...
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    Co nejaka halda?
    1.3.2009 19:57 zde | skóre: 9 | blog: Linuch | Brno
    Rozbalit Rozbalit vše Re: Programatorsky dotaz: Hleda se struktura!
    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.

    Táto, ty de byl? V práci, já debil.

    Založit nové vláknoNahoru

    ISSN 1214-1267   Powered by Hosting 90 Server hosting
    © 1999-2013 Argonit s. r. o. Všechna práva vyhrazena.