Forum » Programiranje » sortiranje neznano dolge datoteke v pascalu
sortiranje neznano dolge datoteke v pascalu
mmisv ::
po dolgem času iščem pomoč na slo-techu, ker mi drugje ne znajo pomagat :(
pri seminarski nalogi se mi pojavi problem in sicer sortranje neznano dolge datoteke v pascalu. datoteka vsebuje string.
poskusil sem nekako takole:
procedure sortiraj(n:integer);
var t:array [1..n]; {tu se zatakne!!!!}
begin
{vse elemente datoteke prepišemo v tabelo, jo sortiramo, nobenega problema}
end;
begin
assign
{prešteješ vse elemente v datoteki, dobiš število n, kličeš podprogram}
sortiraj(n);
end.
na mestu, kjer se zatakne, bi moral najti neko novo rešitev. u bistvu sem mislil rešiti z neko tabelo, ki bi ji velikost 'določil' šele v programo, ko bi klical to proceduro. kako to rešiti??? ali obstaja kaka druga rešitev, ali mi ostane le graditev binarnega urejenega drevesa (dinamična struktura) in potem prepisovanje v datoteko??
kako bi vi to naredili?
hvala
pri seminarski nalogi se mi pojavi problem in sicer sortranje neznano dolge datoteke v pascalu. datoteka vsebuje string.
poskusil sem nekako takole:
procedure sortiraj(n:integer);
var t:array [1..n]; {tu se zatakne!!!!}
begin
{vse elemente datoteke prepišemo v tabelo, jo sortiramo, nobenega problema}
end;
begin
assign
{prešteješ vse elemente v datoteki, dobiš število n, kličeš podprogram}
sortiraj(n);
end.
na mestu, kjer se zatakne, bi moral najti neko novo rešitev. u bistvu sem mislil rešiti z neko tabelo, ki bi ji velikost 'določil' šele v programo, ko bi klical to proceduro. kako to rešiti??? ali obstaja kaka druga rešitev, ali mi ostane le graditev binarnega urejenega drevesa (dinamična struktura) in potem prepisovanje v datoteko??
kako bi vi to naredili?
hvala
Čist trivialna stvar...
Thomas ::
Jest bi na pascal pozabil.
C++
Basic
Java
Sploh ne vem, kaj vas še pojajo po tem pascalu - res ne.
Ampak ok. Neznano dolgo datoteko se ne more posortati v nobeni tabeli. Ker za še tako veliko tabelo, ki jo lahko postaviš, je datoteka lahko daljša.
Zato bi bil najboljši tale sort:
Bereš 32 (naprimer) elementov in jih posortaš in zapišeš v dat.1 ... naslednjih 32 v dat.2 ... in tako naprej.
Potem moraš narediti pa zlivanje. Bereš paralelno dve datoteki in ju zlivaš. Boš najdu source za merge komot z Googletom.
Če potem zlivaš po dve datoteki, jih imaš kmalu pol manj. Ponavljaš, dokler nimaš samo ene.
A si kej zapopadu?
C++
Basic
Java
Sploh ne vem, kaj vas še pojajo po tem pascalu - res ne.
Ampak ok. Neznano dolgo datoteko se ne more posortati v nobeni tabeli. Ker za še tako veliko tabelo, ki jo lahko postaviš, je datoteka lahko daljša.
Zato bi bil najboljši tale sort:
Bereš 32 (naprimer) elementov in jih posortaš in zapišeš v dat.1 ... naslednjih 32 v dat.2 ... in tako naprej.
Potem moraš narediti pa zlivanje. Bereš paralelno dve datoteki in ju zlivaš. Boš najdu source za merge komot z Googletom.
Če potem zlivaš po dve datoteki, jih imaš kmalu pol manj. Ponavljaš, dokler nimaš samo ene.
A si kej zapopadu?
Man muss immer generalisieren - Carl Jacobi
mmisv ::
pascal.. jah zdej smo začel v pascalu, je treba tud dokončat. se prav datoteko razdeliš na recimo 32 zapisov velike datotekce, jih posortiraš, potem jih združiš in med združevanjem (zlivanjem) verjetno tudi gledaš kater zapis je večji in kater manjši in tako zlivaš dokler ne dobiš ene datoteke, ki je sortirana.
sem prav razumel? še vedno se mi zdi dinamična rezervacija prostora s kazalci (en drevešček) enostavnejša.. no bom videl kaj mi bo rata skup spacat
hvala!
sem prav razumel? še vedno se mi zdi dinamična rezervacija prostora s kazalci (en drevešček) enostavnejša.. no bom videl kaj mi bo rata skup spacat
hvala!
Čist trivialna stvar...
blabla ::
Brez veze se je za take stvari zafrkavat. Narediš maxint dolgo tabelo in ti program deluje za sortiranje neznano dolge datoteke do velikosti par milijonov elementov.
mmisv ::
kakšna pa je deklaracija take kode? t:array[1..maxint] of string; ??
Čist trivialna stvar...
mile ::
al pa na to foro
tabelca = array of integer;
Potem pa nastavljas velikost SetLength(tabelca,n)
tabelca = array of integer;
Potem pa nastavljas velikost SetLength(tabelca,n)
ElectricMan ::
takole gre. Pri glavni datoteki poiščeš delno urejenost podatkov in kopiraš na prvo pomožno datoteko. Drugo delno urejenost podatkov pa na drugo pomožno datoteko, potem pa spet na prvo in tako naprej ponavljaj dokler ne zmanjka podatkov. Lahko pa uporabljaš več pomožnih datotek, ampak raje ne, ker se stvar bolj komplicira. Ko imaš dve pomožni datoteki nafilan, sledi postopek zlivanje. Zlivaš tako, da primerjaš obe datoteki in tisti manjši element zapišeš na glavno datoteko. Pri tem pa moraš paziti, da dve pomožni datoteki delno urejeni podatki nista enaki dolgi. Po končanem zlivanju, pa spet v fazo porazdeljevanja tako kot je navedeno zgoraj, nato zlivanje. Ta postopek ponavljaš tako dolgo, dokler je glavna datoteka urejena.
MUC ::
Se da urejat takšne datoteke in to še brez dodatne uporabe pomnilnika.
Najenostavnejša in tudi najpočasnejša metoda takega zunanjega urejanja je tole:
Prebereš število i in i+1 v datoteki. Če je i>i+1, potem jih zamenjaš in zapišeš nazaj v datoteko. To ponoviš n^2 krat (kjer je n število števil v datoteki).
Če imaš kej več pojma vzameš v uporabo tudi glavni pomnilnik in v njem zgradiš recimo kopico, vstavljaš vanj števila (lahko jih je skoraj neskončno, ker bo račnulanikk čez več miljard števil pač swapal). Ko je kopica zgrajena, prebereš vsa števila po vseh nivojih v zaporedju in wola... mađik happens
Najenostavnejša in tudi najpočasnejša metoda takega zunanjega urejanja je tole:
Prebereš število i in i+1 v datoteki. Če je i>i+1, potem jih zamenjaš in zapišeš nazaj v datoteko. To ponoviš n^2 krat (kjer je n število števil v datoteki).
Če imaš kej več pojma vzameš v uporabo tudi glavni pomnilnik in v njem zgradiš recimo kopico, vstavljaš vanj števila (lahko jih je skoraj neskončno, ker bo račnulanikk čez več miljard števil pač swapal). Ko je kopica zgrajena, prebereš vsa števila po vseh nivojih v zaporedju in wola... mađik happens
MUC ::
Kar pa je zapisal ElectricMan je tudi res in je še ena možna rešitev. Teh je toliko, da si lahko še celo izbirčen.
Vredno ogleda ...
Tema | Ogledi | Zadnje sporočilo | |
---|---|---|---|
Tema | Ogledi | Zadnje sporočilo | |
» | Računalništvo na maturi - več vprašanj, da vidimo kolko znate!Oddelek: Šola | 4904 (2976) | seaclam |
» | [Turbo Pascal] Rabu bi nekaj ur inštrukcijOddelek: Programiranje | 1760 (1262) | DimmniBurek |
» | Preimenovanje datotekOddelek: Programiranje | 819 (773) | |Luka| |
» | [Turbo Pascal] Pomoč...Oddelek: Programiranje | 1487 (1389) | Grey |
» | C++ in datoteke problemčekOddelek: Programiranje | 742 (643) | BigWhale |