abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
    dnes 12:44 | Nová verze

    Standard Matter (Wikipedie, GitHub), původně Project Connected Home over IP (CHIP), pro propojení IoT a domácí automatizaci byl vydán ve verzi 1.4.

    Ladislav Hagara | Komentářů: 0
    včera 15:55 | Komunita

    Fedora Linux je aktuálně k dispozici v 5 edicích: Workstation, Server, IoT, Cloud a CoreOS. Pro desktopové nasazení je určena edice Workstation, což je prostředí GNOME. Vývojářům a uživatelům KDE Plasma se dlouhodobě nelíbí, že jejich prostředí je schováno mezi spiny, tj. alternativními desktopy. Prosadili si, že s následující verzí Fedora Linuxu KDE Plasma povýší ze spinu na edici a bude tak na úrovni Workstation.

    Ladislav Hagara | Komentářů: 8
    včera 15:11 | Nová verze

    UBports, nadace a komunita kolem Ubuntu pro telefony a tablety Ubuntu Touch, vydala Ubuntu Touch OTA-6 Focal, tj. šesté stabilní vydání založené na Ubuntu 20.04 Focal Fossa.

    Ladislav Hagara | Komentářů: 0
    včera 01:22 | Nová verze

    Byla vydána nová verze 8.0 (𝕏) frameworku pro vývoj webových aplikací Ruby on Rails (Wikipedie). Přehled novinek v příspěvku na blogu, v poznámkách k vydání a na GitHubu.

    Ladislav Hagara | Komentářů: 0
    7.11. 17:44 | Nová verze

    Byla vydána verze R14.1.3 desktopového prostředí Trinity Desktop Environment (TDE, fork KDE 3.5, Wikipedie). Přehled novinek v poznámkách k vydání, podrobnosti v seznamu změn.

    JZD | Komentářů: 8
    7.11. 16:00 | Komunita

    Dnes v 17:00 má na YouTube online premiéru krátký film Project Gold od Blender Studia představující možnosti rozšíření Blenderu pro "malířský vzhled".

    Ladislav Hagara | Komentářů: 0
    7.11. 13:33 | IT novinky

    Byl představen oficiální Raspberry Pi USB 3 Hub. Cena je 12 dolarů.

    Ladislav Hagara | Komentářů: 6
    7.11. 12:33 | Komunita

    Na YouTube byly zveřejněny sestříhané videozáznamy přednášek z letošního OpenAltu. Dostupné jsou také přímo z programu po kliknutí na přednášku.

    Ladislav Hagara | Komentářů: 3
    7.11. 00:33 | Humor

    Co přesně se děje, když se pomocí curlu připojujeme ke google.com? Proč to psát do terminálu, když si to můžeme pustit jako videoklip curl -v https://google.com na YouTube. 😂

    Ladislav Hagara | Komentářů: 22
    6.11. 22:33 | Nová verze

    Open source platforma Home Assistant (Demo, GitHub, Wikipedie) pro monitorování a řízení inteligentní domácnosti byla vydána ve verzi 2024.11.

    Ladislav Hagara | Komentářů: 0
    Rozcestník

    Dotaz: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?

    8.2.2011 14:40 HonzaZ
    Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Přečteno: 765×
    Narazil jsem na zajímavý problém, se kterým si nevím rady. Mám hrozně velký soubor a zpracovávám jeho řádky. Chci vědět např., kolikkrát se každý řádek vyskytuje v celém souboru. Těch řádků je taky hrozně moc, takže se všechny do paměti nevejdou - musím to ukládat jinak (nemůžu prostě do nějakého asociativního pole přiřadit pro každý řádek počty). Některý řádky tam třeba budou častěji, ale stále se budou objevovat nové a nové. Dělám to v perlu, ale to asi není důležité.

    Jak by se to dalo udělat? Napadly mě 2 řešení.

    1.: zpracovávat to po částech a pak nějak spojovat výsledky

    2.: ty řádky, které se vyskytují hodně nechat v paměti, ostatní někde v souboru (nebo nevím kde)?

    Ale ani jedno se mi moc nelíbí. Jak se takové věci normálně dělaj?

    Řešení dotazu:


    Odpovědi

    Řešení 1× (buff)
    8.2.2011 15:01 polymorf | skóre: 14 | blog: tar_zxpf
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    3. Naimportuj do databazy, sprav index nad tym stlpcom, jednoduchy selekt (select riadok, count(*) from tabulka group by 1)

    4. sort velkysubor; sekvencne spracuj v jednom kroku (nacitas riadok, pocitas na kolkych dalsich riadkoch je, pri zmene ziskas pocet)
    8.2.2011 15:21 HonzaZ
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Díky, to mě nenapadlo, určitě něco z toho použiju :-)
    Řešení 1× (Dr. Eddy)
    8.2.2011 15:25 Filip Jirsák | skóre: 68 | blog: Fa & Bi
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Nepracujte s celými řádky, ale jenom s hashem. Tj. načtete řádek, spočítáte z něj hash a podíváte se, jestli už jste takový viděl. Pokud ano, podívejte se k hashi na seznam odpovídajících řádků (např. jen začátek řádku v souboru a jeho délka). Když řádek v seznamu najdete, zvyšte jeho počitadlo, jinak řádek přidejte do seznamu a poznamenejte si k němu jeho začátek a délku. Když hash nenajdete vůbec, založte pro něj seznam a přidejte řádek. Hashe bych nehledal v asociativním poli, ale rovnou bych je použil jako index pole – tj. zvolte tak krátký hash, ať se vám pole s takovým počtem prvků vejde do paměti (samozřejmě s dalšími údaji).
    8.2.2011 15:31 HonzaZ
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Hmm zajímavé, to by mě taky nenapadlo. Ale těch dat může být tolik, že ani tak to nebude stačit, takže použiju jiné řešení. Ale díky za koment & rozšíření obzorů.
    Řešení 1× (Dr. Eddy)
    9.2.2011 08:41 happy barney | skóre: 34 | blog: dont_worry_be_happy
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Rozdeľ si vstupné data na utriedené bloky a potom už robíš iba merge :-)
    9.2.2011 09:31 Filip Jirsák | skóre: 68 | blog: Fa & Bi
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    To je hezké, jak se tady radí ten soubor setřídit. Jenže setřídit ten soubor znamená udělat to samé, jako je popsáno v dotazu, a ještě navíc přesouvat data v něm. A protože jde o řádky, které tedy asi nejsou stejně dlouhé, bude to znamenat vytvořit vedle ještě jednou stejně velký soubor. Buď se podaří ten soubor setřídit nějakým jiným zde popsaným postupem rovnou, a pak se ten pomocný soubor vytvoří jen jednou, nebo se bude muset třídit postupně asi bublinkou, a pak se ten pomocí soubor bude vytvářet x-krát a celý se tedy bdue x-krát kopírovat. Opravdu vám to připadá jako zjednodušení?
    9.2.2011 09:37 Dr. Eddy | skóre: 9 | blog: glog | České Budějovice
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    neni treba to na zacatku tridit, staci rozdelit na bloky, tam spocitat vyskyty a pak mergenout vysledky...
    9.2.2011 10:34 kaaja | skóre: 24 | blog: Sem tam něco | Podbořany, Praha
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    A co kdyz ty bloky budou zrovna takove, ze se tam moc nebude nic moc opakovat. Pak se zacne byt ten merge dost problematicky.
    9.2.2011 10:50 Dr. Eddy | skóre: 9 | blog: glog | České Budějovice
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    jasne, pak to bude dele trvat a vysledny soubor poroste. Nicmene si stejne myslim, ze je to lepsi, nez cely vstupni soubor na zacatku setridit. Tady se prakticky budou tridit jen vysledky, kterych je <= nez radku na vstupu.
    9.2.2011 10:56 Filip Jirsák | skóre: 68 | blog: Fa & Bi
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Jenže je potřeba pořád vyřešit tu otázku, jak to udělat. sort nebo merge jsou pořád operace, které uvnitř používají tu samou logiku, na kterou se tazatel ptal.
    9.2.2011 11:16 Dr. Eddy | skóre: 9 | blog: glog | České Budějovice
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Prakticky to bude totez, jako kdybyste uz mel vysledky a uz je jen setridil mergesortem. Jinak na tom nevidim nic tajemneho.

    Soubory obsahujici vysledky muzete zapsat uz setrizene a pak je jen sloucite. Podobne, jako to dela mergesort, jen s tim rozdilem, ze pokud budou klice stejne, sloucite je do jednoho a pocty vyskytu sectete.

    Jen nevim, jak to bude rychle.
    9.2.2011 11:57 Filip Jirsák | skóre: 68 | blog: Fa & Bi
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Problém je v tom „jen je sloučíte“. Pokud bude ve vstupním souboru každý řádek jiný, budete mít na vstupu slučování úplně to samé, jako na úplném začátku. Takže tím se problém nevyřešil. A čím více bude jednotlivých dílů, tím více se výsledek bude blížit tomuhle stavu „každý řádek jiný“ (protože opakující se řádky budou v různých částech). Jenže abyste mohl díly zpracovávat čistě v paměti, potřebujete co nejmenší díly a tedy co nejvyšší počet dílů.

    Neříkám, že to zpracování po částech nemůže pomoci, ale není to všelék. Záleží na charakteru vstupních dat, na tom, kolik místa máte na disku a jak je rychlý…
    9.2.2011 12:04 happy barney | skóre: 34 | blog: dont_worry_be_happy
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    skúste sa googlu spýtať na "merge sort"

    ak sú všetky bloky utriedené, tak stačí prečítať jeden riadok z každého bloku do poľa, utriediť pole, prvú položku zapísať na výstup, nahradiť ďalšou z toho istého bloku, utrieť, vyradiť, nahradiť, ...
    9.2.2011 12:14 Filip Jirsák | skóre: 68 | blog: Fa & Bi
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    To ale předpokládá, že máte tak málo bloků, že se pole řádků po jednom z každého bloku vejde do paměti. Což nevyhovuje zadání.
    9.2.2011 12:21 happy barney | skóre: 34 | blog: dont_worry_be_happy
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    merge je možné rozdeliť na viacero krokov (v každom postupne niečo)
    9.2.2011 12:31 Filip Jirsák | skóre: 68 | blog: Fa & Bi
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Ano. A z toho začíná být vidět, proč bude ten merge sort pomalejší než bucket sort.
    9.2.2011 13:03 happy barney | skóre: 34 | blog: dont_worry_be_happy
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    ani nie ... zrátajte si náročnosť bucket a merge sortu pri limite "max 2 open files".

    samozrejme, ak máte dostatok zdrojov (čo nie je prípad tejto otázky), existujú rýchlejšie algoritmy ako merge sort. Tuná však bol pôvodne navrhovaný postup "split-sort-process-merge-process". (merge ako operácia, nie ako "merge sort")

    9.2.2011 13:21 Filip Jirsák | skóre: 68 | blog: Fa & Bi
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Nechápu, kde se vzal limit „max 2 open files“.

    Nezapomínejte na to, že zadáním není řazení, ale třídění. A právě ta práce navíc s řazením je důvod, proč bude v tomto případě merge sort pomalejší, než bucket sort. Oba principy jsou založené na tom, že si vstupní data rozdělíte do menších skupin, které zvládnete zpracovat. Rozdíl je v tom, že v merge sortu potřebujete dál porovnávat prvky mezi jednotlivými skupinami, což u bucket sortu ale nemusíte. Nebo-li:

    Merge sort:
    • rychle rozdělí do skupin
    • zpracuje skupiny
    • sloučí skupiny
    Bucket sort:
    • pomaleji rozdělí do skupin
    • zpracuje skupiny
    Mohou nastat případy, kdy to rychlejší dělení do skupin převáží nevýhodu nutnosti následného slučování, to ale nebude případ zadání – operace počítání hashe bude zanedbatelná proti zdržení způsobenému nutnosti data načítat z pomalého média. Něco jiného by bylo médium se sekvenčním přístupem, ale předpokládám, že tazatel má data na médiu s náhodným přístupem.
    9.2.2011 14:00 l4m4
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    A jak to tedy přesně provede? Řešení se slučnováním lze zapsat jako poměrně jednoduchý skript v shellu. Od někoho, kdo od všech ostatních požaduje detaily realizace, mi toto přijde jako teoretické kecy.
    9.2.2011 14:17 Filip Jirsák | skóre: 68 | blog: Fa & Bi
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Postupem popsaným v komentáři 3. To, že lze něco napsat jako skript v shellu, ještě neznamená, že ten skript neskončí na nedostatek zdrojů. Ono na to není potřeba psát žádný skript, stačí spustit uniq -c – ovšem silně pochybuju o tom, že si s tím uniq jen tak z ničeho nic efektivně poradí.
    9.2.2011 11:22 l4m4
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Nikoli, merge setříděných komponent potřebuje pouze O(n) paměti, kde n je počet komponent. Nepotřebuje paměť úměrnou velikosti komponenty.
    9.2.2011 12:11 Filip Jirsák | skóre: 68 | blog: Fa & Bi
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    To by mne tedy zajímal popis toho algoritmu, jak byste to dělal. Ne „setřídit a spojit“, ale popsat, co se kdy načte a co se uloží do paměti nebo na disk.
    9.2.2011 13:01 l4m4
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Eh? Každá komponenta je setříděná, to znamená, že do každé potřebuji pouze ukazatel (v obecném smyslu, ne nutně C pointer) na aktuální posici. Všechny věci před ukazatelem v každé komponentě jsou menší a za ním větší než ta aktuální hodnota. Takže algoritmus je:

    1. Inicializuji ukazatele na začátky komponent.

    2. Některá z odkazovaných hodnot je nejmenší, tak tu mergnu (může se vyskytovat ve více komponentách), vypíšu ji a posunu odpovídající ukazatele.

    3. Opakuji 2, dokud všechny ukazatele neukazují na konce komponent.

    Je to standardní algoritmus, určitě je i v Knuthovi.
    9.2.2011 13:11 Filip Jirsák | skóre: 68 | blog: Fa & Bi
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Já jsem se ptal na celý postup od začátku. A v zadání rozhodně není nic o tom, že každá komponenta je setříděná. Pak tam máte takovou drobnost „vypíšu ji“, což jinými slovy znamená, že ji zapíšete do výstupního souboru. Tedy na konci zpracování budete mít vstupní soubory a výstupní soubor, potřebujete tedy celkovou kapacitu úložného zařízení na dvojnásobek dat.

    Nezajímá mne teoretický algoritmus, ale právě to praktické provedení s načítáním a ukládáním dat. Ono se vám totiž v tom teoretickém popisu algoritmu snadno do frází „vypíšu ji“ schovají věci jako „v průběhu zpracování musím na disku vytvořit druhý soubor, stejně velký, jako je vstup“.
    9.2.2011 13:46 l4m4
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    A já jsem opovídal na tu část, která by mohla být nejasná tazateli. Řekl bych, že určitě dokáže rozdělit vstup na části a každou si někde zvlášť setřídit. Je možné to udělat různě a klidně i někde jinde. Ne, nebudu ti sem psát kompletní program nebo skript, jelikož mne za to ani neplatíš, ani nejsi původní tazatel, jen prudíš.
    Tedy na konci zpracování budete mít vstupní soubory a výstupní soubor, potřebujete tedy celkovou kapacitu úložného zařízení na dvojnásobek dat.
    Obecně více než na dvojnásobek objemu výstupních dat, protože opakování v každé komponentě je menší než ve sloučeném výstupu. No a? Ke každé komponentě se po setřídění přistupuje sekvenčně a výsledek se též dostává sekvenčně a již setříděný, takže je klidně budu tahat rourou přes ssh a vypisovat výsledek zrovna tak, když na to přijde... Je to jedno, toto není ta obtížná část.
    9.2.2011 13:52 Filip Jirsák | skóre: 68 | blog: Fa & Bi
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Přesunout ta data někam jinam, kde bude třeba víc paměti, je samozřejmě také řešení. Ovšem pokud tazatel nemá data na vyloženě pomalém disku nebo nemá opravdu málo paměti, je to řešení neefektivní. Stejně jako je neefektivní řešit to řazením a slučováním, když se to dá vyřešit tříděním. Netvrdil jsem, že váš postup je nemožný, je pouze méně efektivní, než jiný postup v diskusi navržený.
    9.2.2011 11:59 happy barney | skóre: 34 | blog: dont_worry_be_happy
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    no, začnime napr takto:
    mkdir parts
    split -l 10000 big-file parts/
    for i in parts/*; do sort $i > $i-s; done
    
    pokračujme napr takto:
    sort --merge parts/*-s > big-file-sorted
    
    a dokončime
    uniq -c big-file-sorted
    
    9.2.2011 12:56 Messa | skóre: 39 | blog: Messa
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Proč tak složitě, samotný sort od určité velikosti dat dělá to samé.
    9.2.2011 13:07 happy barney | skóre: 34 | blog: dont_worry_be_happy
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    aby bol zrejmý princíp.

    iná výhovorka: takéto veľké objemy dát majú zvyk rásť a operácie s nimi ostávať. V prípade ukladania predtriedených blokov je pridanie dalšieho milióna jednoduchšie. :-)
    9.2.2011 13:08 JS
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Ano. Nebo alternativne: Udelat kratky hash, aby se cela hash tabulka vesla do pameti vcetne prikladu radku. A pak pokazde, kdyz se narazi na konflikt, zalozit novy soubor s radky, ktere jsou v konfliktu. Takhle projet cely soubor. Pak zpracovat konkretni male soubory s pravdepodobne shodnymi radky zvlast.
    9.2.2011 13:22 Filip Jirsák | skóre: 68 | blog: Fa & Bi
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Pokud budete mít hodně různých řádků, nevejde se to do paměti – v nejhorším možném případě (každý řádek jiný) by to znamenalo načíst do paměti celý vstup, což nevyhovuje zadání.
    9.2.2011 13:23 Filip Jirsák | skóre: 68 | blog: Fa & Bi
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Dá se to ale použít jako cache – uložit si do paměti třeba sto nejčastějších řádků. Když už se ta četnost zjišťuje…
    9.2.2011 13:50 JS
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Ne, nenacitat kazdy radek, jenom ten prvni s kazdym hashem. Ten pak ulozit do toho zakladaneho souboru spolu s temi, co maji stejny hash. (Slo by to i tak, ze by se do pameti zadne radky neukladaly, ale pak by se musel ten vstupni soubor projit na konci jeste jednou.)
    9.2.2011 13:53 JS
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Konkretne co by bylo vyhodnejsi zavisi na tom, kolik konfliktu cekate. Pokud jich cekate hodne, je lepsi ty prvni radky s danym hashem do pameti neukladat, a projet ten vstup 2x. Pokud jich cekate jen malo, asi se to vyplati spis naopak. Ale to uz je celkem detail. Rozhodne je tento postup lepsi nez trideni.
    9.2.2011 13:55 Filip Jirsák | skóre: 68 | blog: Fa & Bi
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Jak jsem psal – v případě, kdy by na vstupu byl každý řádek jiný, znamená to uložit celý vstup do paměti (protože „první s každým hashem“ by byl každý řádek). To ale podle zadání nejde.
    9.2.2011 14:50 JS
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Pokud by byly radky omezene delky (coz je casto mozne, treba u nejakych ciselnych dat), a byl to kratky hash (jak jsem psal), tak v tom neni zadny problem a zvladne se to s konstantni velikosti pameti. A jak uz jsem rikal, jde to celkem dobre obejit tim, ze se ten soubor projde 2x (a jen se hledaji kolize pri tom prvnim pruchodu, a pri tom druhem se pridaji ty prvni radky do tech souboru, co maji stejne hashe).
    9.2.2011 16:45 JS
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Vlastne by se to dalo castecne udelat i s coreutils. Pomoci treba sha1sum by se nechal spocitat hash kazde radky (a pripojil pred ni), a pak by se vysledek poslal do csplit, ktere by to rozdelilo do souboru podle toho hashe. Tohle opakovat, dokud velikost tech souboru nebude pod rozumnou mezi.
    9.2.2011 13:54 marek
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?

    Dobry den.

    Mam hotovy kod, ktery je schopen cist data ze stdin a rovnou online radit do binarniho stromu. To znamena, ze nemusim mit cela data v pameti (tedy pokud je tam dostatek shod).

    Mel jsem to pustene na logy, ktere pribyvali radove v tisicich radku za secundu.

    Pokud se radky casto opakovaly, pak to bylo v pohode zvladnutelne.

    Je to napsano v C, vicevlaknove:

    Prvni vlakno nacita z stdin, predava do bufferu.

    Druhe vlakno bere z bufferu a uklada do stromu.

    Treti vlakno vyhodnocuje strom a obcas ho zoptimalizuje.

    Pak je tam jeste neco na prubezny vypis.

    Muzu nabidnout zdrojove kody (v C bezne nepisu, takze stabni kultura nic moc...)

    Marek

    Saljack avatar 11.2.2011 09:27 Saljack | skóre: 28 | blog: Saljack | Praha
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Jasně ukaž rádi se mrkneme.
    Sex, Drugs & Rock´n Roll.
    11.2.2011 09:55 marek
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Příloha:

    Zde to je.

    Je to jednoucelovy nastroj.

    Optimalizovano je jen to, co jsem uznal za dulezite, za zbytrek se stydim.

    Marek

    9.2.2011 17:05 Radek Miček | skóre: 23 | blog: radekm_blog
    Rozbalit Rozbalit vše Re: Jak zpracovat tolik dat, že se ani výsledek nevejde do paměti?
    Jak se takové věci normálně dělaj?
    Nejjednodušší bude soubor setřídit třeba příkazem sort, a pak to spočítat.

    Asi rychlejší bude použít hašování a v hašovací tabulce si ukládat počty výskytů (je třeba počítat s tím, že jedno počítadlo může být společné pro více řádků).

    Založit nové vláknoNahoru

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

    ISSN 1214-1267   www.czech-server.cz
    © 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.