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

[martyd420]

Ahoj,
mám tisíce souborů v různých podadresářích ve formátu:
nějaké_slovo;nějaké_score

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

Po nějakém googlení se mi pár jednoduchých pokusů podařilo, ale jde mi o rychlost. Jak tohle řešit s ohledem na výkon a rychlost zpracování? Uvedená struktura jen pro představu, jde mi prostě o rozdělení tisíců dlouhých souborů (desítky tisíc řádků) tak, abych je nemusel všechny prohledávat když skládám větu a vím, že potřebuju něco na PIV, tak to najdu ve složce P v souboru PI.txt

Zkoušel jsem to i importovat do mysql a naindexovat do sphinxu. I když jsem dělal inserty po 10 000 řádcích, trvalo to 2 dny a následná indexace den, což je na měnící se data trochu nepohodlné.

[Reklama]

[modnar]

Problem, ze system ukladani do souboru v takovem meritku je kravovina a vytvari to dalsi problemy.

Zamyslel bych se nad pouzitim neceho smysluplnejsiho jako RocksDB. Klasicka relacni databaze asi nebude uplne vhodna.

Zaroven tim odpadnou dalsi tvoje potize jako vyhledavani a razeni.

[CPU]

Tohle mi přijde jako úkol pro postgreSQL....

[CPU]

BTW - můžeš mít jen uložené správné názvy souborů třeba (255558887444486.file) nebo rovnou vracet obsah.
Pokud bys chtěl ze shellu pouštět komplexní dotaz, ulož ho klidně na ramdisk spolu s tím, co potřebuješ, klidně i s celou databází.

psql -h asilocalhost -d databáze -U postgres nebo uživatel jen pro čtení -p 5432 -a -q -f /cestaKsouboru/soubor.sql

nebo jednoduchý dotaz

psql -U postgress nebo uživatel jen pro čtení -d databáze -c 'SELECT * FROM mojetabulka'

[_Jenda]

A na co ses přišel zeptat? Jestli na to není hotové řešení? Nebo jak bychom to dělali? Já bych načetl všechny soubory do jednoho velikého slovníku v Pythonu a pak je z toho vypsal do těch souborů podle požadavků. Pokud je toho tolik že se to ani nevejde do paměti, tak bych to udělal na více průchodů.

Nicméně jak píší ostatní, výsledek takové „databáze v souborech“ nebude příliš efektivní. Pokud vyžaduješ vysokou rychlost vyhledávání, buď budeš muset použít nějakou databázi (já rád používám sqlite) s vhodně nastavenými indexy, nebo si udělat nějakou samodomo datovou strukturu (binární vyhledávání, B-strom…).

Kolik těch dat dohromady je? (megabajty, gigabajty, stovky gigabajtů?) Pokud do giga tak bych to normálně držel in-memory v nějakém slovníku, setříděném seznamu (snadno to v tom najdeš binárním vyhledáváním) nebo jiné vhodné struktuře co tvůj programovací jazyk nabízí.

[Reklama]

[Jose D]

Noo nejdřív jsem myslel, že to je pohovor do nejmenované karlinske firmy, ale spíš ne..

Jak myslíš ta "měnící se data" ? Jen insert, nebo I vyhazuješ?

V momentě když už máš zatříděný ten výchozí dataset (na což by šel asi spáchat nějaký paralelní algoritmus, který by byl omezený spíš iops storage, než nějakou výpočetní složitostí), tak řešíš v zásadě jak vložit novou položku do existující struktury..

A tam mi přijde docela omezující ta pevná definice souborů po 1000 řádcích.

Kdybys povolil i menší, tak se obejdeš bez nějakého přetékání obsahu mezi soubory, které ti z jednoho zápisu udělá lavinu IO.

[anonacct]

Jo celkem to vypadá jak otázka co padla v nějakém pohovoru - PureStorage, Google?

Většinou to bude o tom, že všechny ty data se do paměti nevlezou, takže vytvořit in-memory index prostě není možné. Na druhou stranu ty paměťové nároky se dají zmenšit, třeba pokud máš opravdu jen ASCII znaky v názvu a třeba jen malé nebo velké písmena, můžeš místo 8 bitů na znak použít 5, což ty data zmenší o 1/3. Toto je ale hodně nízkoúrovňové, těžko říct jestli relevantní.

Jinak pokud se jedná o masivní množství dat, tak nevim jestli tradiční DB jsou řešení. Toto by chtělo první zmenšit problém, třeba opravdu vzít první 2 písmena a udělat nad tím partitioning, a pak s tím něco dělat, pokud se opravdu jedná jen o lookup. A pokud už ten partitioning uděláš, tak ty písmena pak už neopakovat dál (a díky tomu se ušetří ddalší místo, atd...).

Jinak moc nemám představu z toho popisku, abych se přiznal, takže jen plácám...

[oss]

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

[politickynekor]

masivni data nejdou importovat pres inserty, ale pouzivaje se loadery/external tables pro danou databazi (https://dev.mysql.com/doc/refman/8.0/en/load-data.html)

[martyd420]

A na co ses přišel zeptat? Jestli na to není hotové řešení?

Jo, to by pomohlo. Běžně používám sphinx, ale tady už je to asi moc velké.

Jsou to desítky tisíc souborů, celkem asi 800 mio řádků. Dohromady asi 800GB, do ramky to nevejde.. Mysql tabulka bez potřebného indexu nad požadovaným sloupcem už měla 2TB     Zkusím dneska něco nacpat do pgsql, holt budu muset experimentovat..

[Ink]

Řadicích algoritmů jsou mraky a určitě se dá vybrat nějaký, který zvládne práci s externím úložištěm, tedy že všechna data nebudou v RAM. Soubory s názvem A/1 mi nepřijdou jako dobrý nápad, AA a AB už spíš. Pokud by ta slova byla rozdělena v rozumných chuncích (rozumně velkých souborech), dalo by se v nich podle mě poměrně rychle binárně vyhledávat. Zároveň by se ty chunky daly i celkem rychle updatovat. Problém vidím v tom, že Ty to chceš "rychle", ale nikde neuvádíš, co to znamená rychle. Budou k tomu přistupovat přes web desítky lidí za sekundu? Stovky? Nebo to chceš jenom "rychle" pro vlastní potřebu? Teoreticky by ten soubor mohl být i zkomprimovaný, pokud chceš optimalizovat místo, ne?

Mimochodem, ani ta tabulka v SQL databázi nemusí obsahovat všechna slova, těch tabulek může být klidně 1000, ne? To by taky mohlo řešit problémy s reindexováním apod...

[alex6bbc]

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

tak si stahni v textaku nejakou tlustou knihu z netu, nacti kapitolu a do souboru vypis slova z kapitoly a kolikrat se to slovo objevilo. udelej tohle pro vsecky kapitoly, a treba i pro vic knih. a pak az to budes mit tak to nasypej nekam a setrid podle abecedy a podle frekvence vyskytu slov sumarne pro vsecky kapitoly/knihy.

[Ondrej Nemecek]

Jak bylo řečeno: Ukládání i hledání dle prefixu lze dobře optimalizovat (různé typy stromů). Vhodně zvolený index může problém řešit (s důrazem na to vhodně zvolený), pro uložení slov lze použít kompresi, případně tam ta hodnota nemusí být uložena vůbec, protože se odvodí z indexu. To zredukuje prostorovou náročnost. Hledal bych databázi, která toto bude umět. Postgres bych zkusil mezi prvními. Data bych nahrál tím přímým importem, nikoli insertem.

[oss]

Za mna toto je priam klasicka uloha pre merge sort. Ak chce clovek hotove rienie tak bud Cassandra, alebo RavenDb.

[Kada]

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.