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í
×
eParkomat, startup z ČR, postoupil mezi finalisty evropského akcelerátoru ChallengeUp!
Robot na pivo mu otevřel dveře k opravdovému byznysu
Internet věcí: Propojený svět? Už se to blíží...
dnes 11:44 | Zajímavý projekt

Na Indiegogo byla spuštěna kampaň na podporu herní mini konzole a multimediálního centra RetroEngine Sigma od Doyodo. Předobjednat ji lze již od 49 dolarů. Požadovaná částka 20 000 dolarů byla překonána již 6 krát. Majitelé mini konzole si budou moci zahrát hry pro Atari VCS 2600, Sega Genesis nebo NES. Předinstalováno bude multimediální centrum Kodi.

Ladislav Hagara | Komentářů: 0
dnes 00:10 | Nová verze

Byla vydána verze 4.7 redakčního systému WordPress. Kódové označením Vaughan bylo vybráno na počest americké jazzové zpěvačky Sarah "Sassy" Vaughan. Z novinek lze zmínit například novou výchozí šablonu Twenty Seventeen, náhledy pdf souborů nebo WordPress REST API.

Ladislav Hagara | Komentářů: 0
včera 12:00 | Zajímavý projekt

Projekt Termbox umožňuje vyzkoušet si linuxové distribuce Ubuntu, Debian, Fedora, CentOS a Arch Linux ve webovém prohlížeči. Řešení je postaveno na projektu HyperContainer. Podrobnosti v často kladených dotazech (FAQ). Zdrojové kódy jsou k dispozici na GitHubu [reddit].

Ladislav Hagara | Komentářů: 20
včera 11:00 | Bezpečnostní upozornění

Byly zveřejněny informace o bezpečnostní chybě CVE-2016-8655 v Linuxu zneužitelné k lokální eskalaci práv. Chyba se dostala do linuxového jádra v srpnu 2011. V upstreamu byla opravena minulý týden [Hacker News].

Ladislav Hagara | Komentářů: 2
5.12. 22:00 | Komunita

Přibližně před měsícem bylo oznámeno, že linuxová distribuce SUSE Linux Enterprise Server (SLES) běží nově také Raspberry Pi 3 (dokumentace). Obraz verze 12 SP2 pro Raspberry Pi 3 je ke stažení zdarma. Pro registrované jsou po dobu jednoho roku zdarma také aktualizace. Dnes bylo oznámeno, že pro Raspberry Pi 3 je k dispozici také nové openSUSE Leap 42.2 (zprávička). K dispozici je hned několik obrazů.

Ladislav Hagara | Komentářů: 6
5.12. 06:00 | Zajímavý software

OMG! Ubuntu! představuje emulátor terminálu Hyper (GitHub) postavený na webových technologiích (HTML, CSS a JavaScript). V diskusi k článku je zmíněn podobný emulátor terminálu Black Screen. Hyper i Black Screen používají framework Electron, stejně jako editor Atom nebo vývojové prostředí Visual Studio Code.

Ladislav Hagara | Komentářů: 50
5.12. 06:00 | Zajímavý článek

I letos vychází řada ajťáckých adventních kalendářů. QEMU Advent Calendar 2016 přináší každý den nový obraz disku pro QEMU. Programátoři se mohou potrápit při řešení úloh z kalendáře Advent of Code 2016. Kalendáře Perl Advent Calendar 2016 a Perl 6 Advent Calendar přinášejí každý den zajímavé informace o programovacím jazyce Perl. Stranou nezůstává ani programovací jazyk Go.

Ladislav Hagara | Komentářů: 10
3.12. 16:24 | Nová verze

Byla vydána Mageia 5.1. Jedná se o první opravné vydání verze 5, jež vyšla v červnu loňského roku (zprávička). Uživatelům verze 5 nepřináší opravné vydání nic nového, samozřejmě pokud pravidelně aktualizují. Vydání obsahuje všechny aktualizace za posledního téměř půldruhého roku. Mageia 5.1 obsahuje LibreOffice 4.4.7, Linux 4.4.32, KDE4 4.14.5 nebo GNOME 3.14.3.

Ladislav Hagara | Komentářů: 17
3.12. 13:42 | Pozvánky

V Praze probíhá konference Internet a Technologie 16.2, volné pokračování jarní konference sdružení CZ.NIC. Konferenci lze sledovat online na YouTube. K dispozici je také archiv předchozích konferencí.

Ladislav Hagara | Komentářů: 0
2.12. 22:44 | Komunita

Joinup informuje, že Mnichov používá open source groupware Kolab. V srpnu byl dokončen dvouletý přechod na toto řešení. V provozu je asi 60 000 poštovních schránek. Nejenom Kolabu se věnoval Georg Greve ve své přednášce Open Source: the future for the European institutions (SlideShare) na konferenci DIGITEC 2016, jež proběhla v úterý 29. listopadu v Bruselu. Videozáznam přednášek z hlavního sálu je ke zhlédnutí na Livestreamu.

Ladislav Hagara | Komentářů: 26
Kolik máte dat ve svém domovském adresáři na svém primárním osobním počítači?
 (32%)
 (24%)
 (29%)
 (8%)
 (5%)
 (3%)
Celkem 781 hlasů
 Komentářů: 50, poslední 29.11. 15:50
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: 686×
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: 22 | 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.