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 02:20 | Zajímavý článek

David Revoy, autor open source webového komiksu Pepper&Carrot nebo portrétu GNU/Linuxu, upozorňuje na svém blogu, že nový Inkscape 0.92 rozbíjí dokumenty vytvořené v předchozích verzích Inkscape. Problém by měl být vyřešen v Inkscape 0.92.2 [reddit].

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

Øyvind Kolås, hlavní vývojář grafických knihoven GEGL a babl, které využívá grafický program GIMP, žádá o podporu na Patreonu. Díky ní bude moci pracovat na vývoji na plný úvazek. Milník 1000 $, který by stačil na holé přežití, se již téměř podařilo vybrat, dalším cílem je dosažení 2500 $, které mu umožní běžně fungovat ve společnosti.

xkomczax | Komentářů: 12
21.1. 23:54 | Pozvánky

DevConf.cz 2017, již devátý ročník jedné z největších akcí zaměřených na Linux a open source ve střední Evropě, proběhne od pátku 27. ledna do neděle 29. ledna v prostorách Fakulty informačních technologií Vysokého učení technického v Brně. Na programu je celá řada zajímavých přednášek a workshopů. Letos je povinná registrace.

Ladislav Hagara | Komentářů: 0
21.1. 22:11 | Nová verze

Byla vydána verze 1.0.0 emulátoru terminálu Terminology postaveného nad EFL (Enlightenment Foundation Libraries). Přehled novinek v poznámkách k vydání.

Ladislav Hagara | Komentářů: 0
20.1. 17:00 | Nová verze

Byl vydán Docker 1.13. Přehled novinek na YouTube a v poznámkách k vydání na GitHubu. Docker umožňuje běh aplikací v softwarových kontejnerech (Wikipedia).

Ladislav Hagara | Komentářů: 4
20.1. 15:51 | Komunita

Mozilla.cz informuje, že nástroje pro webové vývojáře se možná oddělí od Firefoxu a stanou doplňkem. Nástroje pro webové vývojáře prošly velkým přepisem a tým, který se stará o jejich vývoj, by uvítal možnost jejich častějších aktualizacích nezávisle na vydávání nových verzí Firefoxu.

Ladislav Hagara | Komentářů: 10
20.1. 07:00 | Humor

Čtenářům AbcLinuxu vše nejlepší k dnešnímu Dni zvýšení povědomí o tučňácích (Penguin Awareness Day).

Ladislav Hagara | Komentářů: 0
20.1. 06:00 | Komunita

Bylo spuštěno hlasování o přednáškách a workshopech pro letošní InstallFest, jenž proběhne o víkendu 4. a 5. března v Praze. Současně byla oznámena změna místa. InstallFest se letos vrací zpět na Karlovo náměstí do budovy E.

Ladislav Hagara | Komentářů: 0
20.1. 02:48 | Komunita

Greg Kroah-Hartman potvrdil, že Linux 4.9 je jádrem s prodlouženou upstream podporou (LTS, Long Term Support). Podpora je plánována do ledna 2019. Aktuální jádra s prodlouženou podporou jsou tedy 3.2, 3.4, 3.10, 3.12, 3.16, 3.18, 4.1, 4.4 a 4.9.

Ladislav Hagara | Komentářů: 0
20.1. 00:11 | Zajímavý článek

Výrobce síťových prvků, společnost Netgear, spustila nový program, který slibuje vývojářům, expertům, ale i běžným uživatelům vyplacení finanční odměny za nalezení bezpečnostních chyby v jejich produktech. Za nalezení zranitelnosti v hardware, API nebo mobilní aplikaci nabízí odměnu od 150 do 15 tisíc dolarů (dle závažnosti).

Michal Makovec | Komentářů: 0
Jak se stavíte k trendu ztenčování přenosných zařízení (smartphony, notebooky)?
 (10%)
 (2%)
 (74%)
 (3%)
 (10%)
Celkem 363 hlasů
 Komentářů: 25, poslední 21.1. 13:34
Rozcestník
Reklama

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: 687×
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: 66 | 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: 66 | 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: 23 | 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: 66 | 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: 66 | 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: 66 | 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: 66 | 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: 66 | 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: 66 | 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: 66 | 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: 66 | 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: 66 | 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: 66 | 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: 66 | 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: 66 | 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.