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

[HonzaZ]

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?

---

---

Odpovědi

[buff]

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)

[HonzaZ]

Díky, to mě nenapadlo, určitě něco z toho použiju

[Dr. Eddy]

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

[HonzaZ]

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

[Dr. Eddy]

Rozdeľ si vstupné data na utriedené bloky a potom už robíš iba merge

[Filip Jirsák]

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

[Dr. Eddy]

neni treba to na zacatku tridit, staci rozdelit na bloky, tam spocitat vyskyty a pak mergenout vysledky...

[kaaja]

A co kdyz ty bloky budou zrovna takove, ze se tam moc nebude nic moc opakovat. Pak se zacne byt ten merge dost problematicky.

[Dr. Eddy]

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.

[Filip Jirsák]

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.

[Dr. Eddy]

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.

[Filip Jirsák]

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ý…

[happy barney]

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

[Filip Jirsák]

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

[happy barney]

merge je možné rozdeliť na viacero krokov (v každom postupne niečo)

[Filip Jirsák]

Ano. A z toho začíná být vidět, proč bude ten merge sort pomalejší než bucket sort.

[happy barney]

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")

[Filip Jirsák]

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.

[l4m4]

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.

[Filip Jirsák]

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

[l4m4]

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.

[Filip Jirsák]

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.

[l4m4]

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.

[Filip Jirsák]

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

[l4m4]

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.

[Filip Jirsák]

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

[happy barney]

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

[Messa]

Proč tak složitě, samotný sort od určité velikosti dat dělá to samé.

[happy barney]

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.

[JS]

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.

[Filip Jirsák]

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

[Filip Jirsák]

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…

[JS]

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

[JS]

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.

[Filip Jirsák]

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.

[JS]

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

[JS]

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.

[marek]

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]

Jasně ukaž rádi se mrkneme.

[marek]

Příloha:

• sort.c (13017 bytů)

Zde to je.

Je to jednoucelovy nastroj.

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

Marek

[Radek Miček]

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