Dotaz: 200 GB txt subor a sort -u

[tutanchamon]

Chcem dostat unikatne slova z 260 GB suboru. Ako na to casovo aj datovo co najefektivnejsie? Mam iba starsie dvojjadro s 4GB RAM a prepoctom idem k 80 hodinam triedenia a cca 500 GB na temp subory + vysledny subor... Dakujem za postrehy...

---

---

Odpovědi

[OldFrog {Ondra Nemecek}]

Podle mě záleží, jak hodně se ta slova opakují. Naivním přístupem bych načetl slovo po slově a vkládal do Setu ve vhodném programovacím jazyce a ten Set nakonec serializoval. Výběrem vhodné implementace Setu by šlo docílit optimálního výkonu, asi na to budou i specializované knihovny. Šlo by to řešit po částech, aby se všechna aktuálně zpracovávaná data vešla do RAM - rozdělit soubor, zpracovat po částech, získané mezivýsledky zpracovat v druhém průchodu. Možná by stejnou úlohu zajistila i nějaká databáze (třeba MapDB a podobné).

[Kit]

Nacpal bych ta slova jako klíče do databáze DB4 a vypsal její obsah.

[Lazar]

Co rozdělit soubor na desítky(stovky?) menších, stanovit unikátní seznam pro každý z nich a pak stanovit seznam unikátních slov pro sloučené dílčí seznamy? Těch unikátních slov snad bude relativně konečné množství, ne?

[Dikobraz Fik]

Příloha:

• progress.png (5733 bytů)

^^^^^^^^^^^^^^ pozrite si progress... poriesil som to takto - hadam to niekomu niekedy pomoze...

pv $1 | parallel --tmpdir tmp --pipe --files sort -u -T tmp -S512M  --parallel=2 | parallel --tmpdir tmp -Xj1 sort -u -T tmp -S1024M --parallel=2  -m {} ';' rm {} > $2

nutne definovat --tmpdir (u mna v aktualnom adresari) inac si zabijete /tmp (ak tam nemate dost miesta)

[uniq]

Preco si nepouzil program uniq?

[R]

Lebo pred jeho pouzitim sa musia aj tak data usporiadat programom sort?

[pc2005]

Jo klíč by měl být OK. Ono těch slov zas tolik není:

# cat /usr/share/dict/words  | wc -l
38619
# cat /usr/share/dict/words  | wc -c
352846

Pokud by vyhledání klíče bylo rychlý (třeba hash), tak by to mohlo číst až rychlostí blízkou disku. Můj naivní kód v perlu, co parsuje asi 3.5GB lisp-like zdroják to zvládne na c2d asi za 30 minut, ale kromě hledání klíče to dělá i inserty do tisíců spojových seznamů apod (což je mnohem náročnější).

[OldFrog {Ondra Nemecek}]

Pokud ovšem jde o slova z normálního „lidského“ jazyka...

[pc2005]

Hmm to je vlastně pravda. Ale i tak ty klíče samozřejmě pomohou, jen to bude trvat dýl a sežere to víc času.

[Rockhopper]

V prvé řadě je potřeba soubor zkomprimovat a řadit zkomprimovaný. Hrubý odhad bez znalosti typu dat cca. do 10 hodin. Na velikosti RAM víceméně nezáleží, stačí 16 MB, záleží na druhu komprese.

[rastos]

N=100000
split --lines=$N  vstup
for file in x*
do 
  cat $file | tr ' ' '\n' | sort -u > $file.usorted
  mv $file.usorted $file
done
cat x* | sort -u > vystup

Hodnotu N upraviť podľa potreby. To 'tr' je také neotesané riešenie, čo neberie do úvahy bodky, čiarky, atď. Možno by sa dalo nahradiť nejakým šikovnejším sed-om.

[dustin]

Myslím, že pokud bude těch x* hodně, zahlásí bash u cat příliš dlouhý seznam parametrů. Ale to lze snadno vyřešit třeba přes find.

Jsou dvě jádra, tak by se to procházení x* mohlo obalit funkcí a xargsem spouštět dva procesy.

[rastos]

Keď urobíš "wc -l vstup" a vydelíš výsledok 200, tak dostaneš počet riadkov na jeden súbor ktorý bude mat +- 1GB. Ten počet dáš split-u, a budeš mať 200 súborov. Aj keby si to delil 2000 tak budeš mať 2000 súborov po 100MB. To by nemuselo byť moc. Podstatné je, že každý ten kúsok sa tým "sort -u" značne zredukuje, takže aj ich spojenie na konci bude relatívne malé.

[dustin]

Jasně, jen jsem upozorňoval, že bývá dobré na max. počet souborů přes wildcard myslet, je to pak nepříjemná chyba. I když, v bashi je každé ladění nepříjemné

[〹]

Kolik unikátních slov očekáváš? Bavíme se o lidském jazyce?

[cronin]

Chtělo by to vzorek toho souboru. A nabízí se vyhlásit soutěž o nejrychlejší řešení a udělat porovnání použití různých technologií

[Michal Kubeček]

A také dost záleží na tom, jestli to má být jednorázová akce nebo jestli je cílem napsat program, který se bude na podobně velkých souborech spouštět opakovaně. V prvním případě bude stačit něco, co bude přijatelně rychlé, a nemělo by smysl trávit hodinu práce navíc optimalizací, která zrychlí běh o hodinu (nebo třeba i čtyři). Ve druhém už by stálo zamyslet se nad datovou strukturou, která umožní rychlý insert a walkthrough (RB tree?).

[lertimir]

rozhodně bych netřídil původní soubor. použil bych algoritmus typu

setrideny-seznam-unikatnich-slov="prázndný seznam"

slovo=prectu-slovo()
while (slovo!=null){
  if (slovo "je v" setrideny-seznam-unikatnich-slov){ # náročnost operace O(log(N))
     zaradit(slovo, setrideny-seznam-unikatnich-slov) # pro balancované seznam to je tuším také O(log(N)), navíc v předchozím vyhledávání už bylo nalezeno, kde v tom seznamu by tohle slovo mělo být a není takže by ty operace mohly být i rychlejší než log protože není třeba hledat.
  }
}

pak v setrideny-seznam-unikatnich-slov je pořád setříděno a pokud to není těch slov fakt moc tak se to možná i vejde do paměti.

[python]

pokud se slova vejdou do RAM, tohle v pythonu bude svizne :

uniq = set()
with open('README.md') as f:
    for line in f:
        words = line.strip().split()
        for w in words:
            uniq.add(w)
print(len(uniq))

[DaBler]

zkuste awk, cf. odpověď na podobný dotaz