Jak abecedně setřídit hodně velkých souborů?

[pangolin]

Pracoval jsem kdysi s textovym korpusem kolem 1.5T (zhruba cely cesky internet v te dobe). Z techto textu se pocitaly nejake zakladni veci jako histogramy slov/n-gramu (zaznam <slovo/n-gram> <pocet vyskytu>). Moje zkusenost je, pokud to chcete zpracovavat pouze na 1 stroji, neni nic rychlejsiho nez `sort` z prikazove radky s patricnymi parametry.

Pro dany problem bych postupoval na 2 kroky:
1. setridil obsah vsech souboru do jednoho velkeho, neco jako

Kód: [Vybrat]

find ./ -type f -exec cat {} \; | pv | LC_ALL=C sort -S 32G --parallel=16 -T /rychly/docasny/adresar >all_in_one.txt
`pv` je program pipeview, aby bylo videt, kdy se nacte vstup, lze nahradit `head -n 10000` pro otestovani. 32G je RAM, 16 pocet jader
Protoze se data nevlezou do pameti, sort bude odkladat mezivysledky do adresare -T. Doporucuju neco, kde je dostatek mista , minimalne na cela vstupni data.

2. nejakym jednoduchym skriptem z velkeho souboru udelal pozadovanou adresarovou strukturu.

V podstatě ano, ale raději bych volil postup nejdříve rozdělit podle prvního písmene do jednotlivých souborů (a la bucketsort) a až pak `sort` na jednotlivé soubory (plus následně rozpad na menší, když jsou "kbelíky" nad limit).

[Reklama]

[Kada]

Jinak pokud by bylo potreba neco jako databaze, tak urcite v 2. postu zminena RocksDB (nemam zkusenost) nebo LMDB, Python binding (mam zkusenost a doporucuju).

V podstatě ano, ale raději bych volil postup nejdříve rozdělit podle prvního písmene do jednotlivých souborů (a la bucketsort) a až pak `sort` na jednotlivé soubory (plus následně rozpad na menší, když jsou "kbelíky" nad limit).

Muze byt, ale nez bych to napsal, tak to ten sort setridi, 800G neni zas tolik, zalezi, kolik je k dispozici RAM.

[_Jenda]

Su k tomu niekde tie subory dostupne?
Takuto ulohu k pohovoru by som si rad vyskusal.

Mohly by tě zajímat opendatovky KSP - úlohy s ikonkou diskety (příklad) můžeš řešit i jako nestudent (někde se tam při registraci dá vybrat že nechceš přiřadit školu) a mají tam k tomu automatické vyhodnocovátko, takže se rovnou dozvíš, jestli je tvoje řešení správné a dostatečně rychlé(!).

[czmiho]

Pocet souboru od aa - zz je 676, to si klidne muzes dovolit drzet otevrene.

Jelikoz zadani nerika, ze obsah souboru ma byt serazeny, tak je od toho mista zadani myslim snadne. Ctes zdrojove soubory po polozkach a rovnou zapisujes do vysledneho souboru s bufferovanim aby IO probehlo az po mnoha zapisech. Hotovo Jelikoz jsou takove ulohy obvykle limitovany poctem IOPS a ten podle me lepe udelat nejde, tak nic rychlejsiho nebude.

[jjrsk]

...
Slova (ascii, case-insensitive) jsou v každém souboru náhodně a já bych je potřeboval uspořádat a abecedně setřídit tak, aby:
- slova začínající na AA byly v souboru AA.txt, AB v souboru AB.txt, ...
nebo
- slova začínající na A byly v souborech po 1000 řádků ve složce A, tzn. ./A/1txt, ./A/2.txt, ...
...

Hele nechci ti kecat do zadani ... ale uz si videl jak treba kodi uklada obrazky? Ono si to defakto totiz tu databazi na disku vytvari, a nepotrebuje to k tomu nejaky dalsi soubory do kterych by to zapisovalo.

Takovy uplne nejjednodussi pristup je ze co pismeno to uroven, samozrejme to pak muze vist na stovky az desitky tisic urovni (podle toho co ti fs umozni). A nazev souboru bude trebas to tvoje score.

Pokud mas slov omezene a omezene delky, tak ta struktura bude samozrejme vyznamne mensi, ale vyhoda je, ze proste jednou vytvoris, a pak uz do toho uplne primitivne davas co kam patri a nepotrebujes resit, jak nekde odsunout nejaky data, natoz nejaky sileny databaze a indexy a vi buh co v rameti.

Tzn ... alfa80.txt ... bys ulozil jako A>L>F>A>80.txt

[Reklama]