sortare fisiere mari

D

devilus

New Member
Am o problema de genul asta:
Am un fisier unde pe fiecare linie este un cuvant. Fisierul dat poate atinge
dimensiuni mari(>200mega), scopul este sa scot duplicatele din aceasta
lista.

Cum fac asta? Atentie! Nu pot incarca fisierul in memorie in intregime
pentru ca se presupune ca calcul nu are prea mult RAM.

Deci, cum?
Ia sa va vad, minti luminate ale plaiului mioritic. :wink:

:demon:
la provod
 
uite.. asha eu ash face... file 1 -> fisierul mare ; file'ul 2 -> fisierul mic.
se incepe un ciclu pentru fiecare rind din file'ul tau cel mare in care faci asha ceva:
pentru fiecare rand din file'ul 1 verifici :
a) daca se contine acest cuvint in file'ul 2 (mic) atunci treci la urmatoarea iteratie a

ciclului (next - pentru urmatorul rand).
b) daca nu exista asha rind in file'ul 2 -> atunci il pui la sfirshit shi mai departe

verifici urmatorul cuvint.
Verificarea tot o faci printr-un ciclu -> fiecare rind din file'ul 2 (mic) il compari cu

cuvintul curent din file'ul 1 (mare).
 
Oleg, asta ar fi o idee, dar gandeste asa:
  • operatia prin care eu determin daca cuvantul din file1 este in file2
    inseamna ca eu trebuie sa parcurg tot file2.
Inchipuiti acum scenariul asta, ca am un fisier de 100Mb cu cuvinte de
lungimea medie 40 caractere -> am peste 2 milioane de cuvinte. File1
nu contine prea multe duplicate aprox 50% sunt unice.

Acum inhipueiti ca am parcurs 1milion de cuvinte din file1, ceea ce inseamna
ca in file2 avem cam 0.5 milioane de cuvinte unice(aprox 25Mb). Acum pentru
fiecare cuvant din file1 noi o sa parcurgem 25M de informatie, si asta
pentru restul de 1milion de cuvinte care au mai ramas... :P

ceea ce inseamna ca noi o sa rupem hardu cu asa program. :D

think about it....

:demon:
la provod
 
si in plus gindeste-te cit timp o sa ia cu algoritmul ista.
iti recomand sa intrebi pe sheva NNTP tipa microsoft.progamming.algorithms
 
nu cred ca ar fi vreo solutie mai rationala decat cea care a propuso oleg, oricum cuvintele tre incarcate intrun file ori memorie si verificate toate :) si n-ar fi 25 mb pt fiecare cuvant, dar incepand cu cativa baiti la primul(ca se verifica mai putin, de exemplu se verifica 1 cuvant la al doilea rand bagat, doua la al treilea, shamd) , si terminand cu cei 25 la ultimul.

alta solutie ar fi de bagat totul intro baza, pe un filesystem mai sanatos decat fat ori ntfs (merge si pe astea numa ca o sa tormozeasca)), si de facut acolo. numai ca asta e mai complicat, si cere si cunostinte de db. si oricum procesezi volum mare de informatie :)
 
ideea cu db nu-i deloc rea. se poate de incercat cu mysql-ul ca cel putin nie imi pare destul de accesibil si simplu de utilizat. si oricum o sa se "muta" cu vintul, ori asa ori altfel.

anyway, amus intreb eu lume mai prodvinutaia si pina miine poate va spun ceva.
 
Devilus, ai vre-un sistem de operare normal(linux/unix) sub miina? :)
Daca da atunci tiparesti urmatoarea linie:
sort fisier.txt | uniq
 
Mask said:
Devilus, ai vre-un sistem de operare normal(linux/unix) sub miina? :)
Daca da atunci tiparesti urmatoarea linie:
sort fisier.txt | uniq
Click to expand...
asta desigur ii bine, numa ca din cat am inteles eu baietu vrea sa faca programa lui :)
 
xx said:
asta desigur ii bine, numa ca din cat am inteles eu baietu vrea sa faca programa lui :)
Click to expand...
Defapt am vazut ca scopul la el e altul :)
Si anume:
devilus said:
scopul este sa scot duplicatele din aceasta
lista.
Click to expand...

fiind neatent, l-am chiar si sortat, dar era deajuns sa scriu numai "uniq fisier.txt"
 
inseamna ca noi toti care ne-am dat cu idei mai sus am fleim-uit degeaba :lol: ca utils-uri pentru sortari sunt destule si pt win si pt nix :)
 
posibil :)
da posibil d-nul devilus nu a pus corect intrebarea.
Poate ca el nu shtie despre utilitele existente si si-a pus drept scop sa scrie una :)
 
Eh, Mask, defapt daca scoti cate o replica din context
te poti trezi ca vorbesti de unul singur :)
si defapt, daca citim mai jos
Atentie! Nu pot incarca fisierul in memorie in intregime
pentru ca se presupune ca calcul nu are prea mult RAM.
Click to expand...
oare nu inseamna asta un detaliu cu care te confrunti cand
implementezi singur ceva?
dar pana la urma, dumnezeu i-i stie pe vor defapt :)
ia sa-l intrebam pe devilus, el singur stie ce vrea?
sau pe TRiX, cel care se "tusuie" in cercuri mai "prodvinutie"...
 
apropo, in privinta teoriei cu ram-ul consumat, eu nefiind deacord, si fiind om curios, m-am bagat pe o vechitura de 386 cu 64 ram. Si am pus un file de 20mb cu 10 cuvinte scrise in coloana care se repetau. Am dat comanda sort file.txt |uniq >file2.txt Si iaca rezultatul:
Code: 
bash-2.05a$ ps -ux
USER       PID %CPU %MEM   VSZ  RSS TTY      STAT START   TIME COMMAND
xx        1329  0.0  1.8  5244 2300 pts/0    S    09:48   0:00 bash
xx        1411 39.5  3.6 15364 5840 pts/0    R    09:56   0:03 sort file.txt
procedura o durat vreo 3 minute, si din cate se vede, se consuma o cantitate mizera de ram, mai mult ii frecat protsul :) asa ca devilus, daca te-ai apucat de scris progi, nu inventa din nou bicicleta da foloseste ceea ce este deja :)
 
way.
nu va certati!

inainte de a intreba aici, io am petrecut cateva ore incercand
sa descurc sursele sort-ului de GNU, dar am vazut ca acolo se
foloseste o mutca serioznaia...

ma intresa ideea.

iaca ce am reusit sa aflu de la niste flacai, care credeti-ma stiu si UNIX
si tot ceea ce ati pomenit mai devreme:
http://www.experts-exchange.com/Programming/Programming_Languages/C/Q_20663524.html

PS: pentru propunerea cu DB vreau sa zic ca, chestia pe care o fac
este anume pentru a nu o face prin serv de SQL, care s-a dovedit in
practica destul de incet, si cerdeti-ma ca e configurat bine.

:demon:
la provod
 
devilus said:
PS: pentru propunerea cu DB vreau sa zic ca, chestia pe care o fac
este anume pentru a nu o face prin serv de SQL, care s-a dovedit in
practica destul de incet, si cerdeti-ma ca e configurat bine.

:demon:
la provod
Click to expand...
devilus, eu pana la urma tot n-am inteles ce vrei de fapt(si am incercat, crede-ma!)
parca ti-au zis un algoritm, daca te intereseaza la nivel de ideie.
daca vrei ceva practic, de ce nu folosesti sort-ul?
eu am lucrat cu unele bd si crede-ma ca poti obtine un tabel sortat din fisierul
tau destul de repede. nu insera datele cate o inregistrare, si fa enable la index-ul definit
pe field-ul care-l vrei sortat abia dupa ce-ai adus datele in tabel.
 
tot sortare :)

se da un tabel N\times D, care contsine cifre binare (0 sau 1). Se cere de extras liniile unice shi numarul de "occurences" (nu mai tsin minte cuvintul in romana...) pentru fiecare.

evident ca prima idee este de a sorta shi dupa aia totul devine simplu.

Partea mai grea este ca se cere o metoda eficienta (in timp) de a face acest lucru. Alte conditsii, care de fapt nu reprezinta nimic special: tabelul poate fi incarcat in memorie (presupunem ca intotdeauna este de ajuns), dar parcurgerea lui in intregime este costisitoare din cauza ca N shi D sunt mari (10^6...10^7 \times 10^3...10^4) => trebuie de minimizat numarul de parcurgeri.

mai intii ashtept sugestiile voastre, dupa aia va spun o solutsie eleganta. dar sa vad daca o descoperitsi shi voi :)

PS: din pacate se pare ca problema nu prea are o solutsie optima unica - totul depinde de N shi de D...
 
You must log in or register to reply here.
Back
Top