extern sortieren

hallo zusammen,

ich hab ne menge Strukturen, welche binär in eine datei geschrieben sind und die ich gerne sortieren möchte. da es ne datenbankähnliche anwendung werden soll möchte ich es wenn möglich vermeiden alle datensätze in den speicher zu laden. hab mir sagen lassen das sich für diesen job grundsätzlich "mergesort" und "insertionsort" eignen.

nun zu meinem problem:
da mergesort die datenmenge ja zweiteilt, diese fragmente wieder zweiteilt usw. bis die fragmente nur noch aus einem element bestehen, müsste ich ja pro "teilung" mehrere temporäre dateien verwenden. da ich aber nicht wissen kann wie viele zu sortierende strukturen anfallen, könnte das unter umständen auch in mehrere tausend temporärdateien ausarten ... was ich eigentlich vermeiden will.

insertionsort eleminiert das problem, erschafft allerdings dafür ein neues. gehen wir davon aus in der datei liegen mehrere hundert strukturen und insertionsort möcht nun beispielsweise relativ am dateianfang einfügen ... dann müsste ich doch alle daten die hinter der eigefügten struktur stehen, um die größe einer struktur versetzt, wieder in die datei schreiben. wenn also das sortieren eine weile dauert (und das wird es mit insertionsort bei großen datenmengen) hab ich lange und lästige HDD zugriffe, die ich nun so auch wieder nicht möchte.

kennt jemand einen eleganten ausweg?

ach ja, ich poste das hier unter "ANSI C" weil ich das ganze gerne in C realisieren würde bzw. realisieren muss

im voraus besten dank

volkard

Darkseed schrieb:

nun zu meinem problem:
da mergesort die datenmenge ja zweiteilt, diese fragmente wieder zweiteilt usw. bis die fragmente nur noch aus einem element bestehen, müsste ich ja pro "teilung" mehrere temporäre dateien verwenden. da ich aber nicht wissen kann wie viele zu sortierende strukturen anfallen, könnte das unter umständen auch in mehrere tausend temporärdateien ausarten ... was ich eigentlich vermeiden will.

doch, da mußte durch.
aber lass uns ein paar kleine änderungen an mergesort anbringen.

höre nicht bei einem element auf zu teilen, sondern bei 103567 elementen. oder halt so vielen, wie du bewuem in den hauptspeicher bekommt. und im hauptspeicher sortiere so ganzen block dann auf einmal mit introsort, heapsort oder mergesort. so brauchste dann doch relativ wenige dateien.
merge immer sofort weg, was mergebar ist. also teile nicht alle bis unten hin und merge danach alles zusammen.
wenn du ganz pfiffig bist, kannste sogar einen datei-generator machen, der die die riesen-datei ausliest und stück für stück dateinamen liefert mit dateien, in denen (durch hauptspeichersortierung) sortierte blöcke liegen. der empfänger dieser dateinamen muß dann die wieder zusammenmergen. wird aber nicht einfach. ich nehme an, es läuft darauf hinaus, ne rekursion durch künstlichen stack nachzubilden.

insertionsort eleminiert das problem, erschafft allerdings dafür ein neues. gehen wir davon aus in der datei liegen mehrere hundert strukturen und insertionsort möcht nun beispielsweise relativ am dateianfang einfügen ...

und insertionsort hat das problem ständig. es ist im vergleich zu merge-sort einfach nur lahm.

volkard

volkard schrieb:

Darkseed schrieb:

nun zu meinem problem:
da mergesort die datenmenge ja zweiteilt, diese fragmente wieder zweiteilt usw. bis die fragmente nur noch aus einem element bestehen, müsste ich ja pro "teilung" mehrere temporäre dateien verwenden. da ich aber nicht wissen kann wie viele zu sortierende strukturen anfallen, könnte das unter umständen auch in mehrere tausend temporärdateien ausarten ... was ich eigentlich vermeiden will.

doch, da mußte durch.
aber lass uns ein paar kleine änderungen an mergesort anbringen.

höre nicht bei einem element auf zu teilen, sondern bei 103567 elementen. oder halt so vielen, wie du bewuem in den hauptspeicher bekommt. und im hauptspeicher sortiere so ganzen block dann auf einmal mit introsort, heapsort oder mergesort. so brauchste dann doch relativ wenige dateien.
nur 1000 daeien bei 103567*1000 elementen. ist doch schonmal was.

merge immer sofort weg, was mergebar ist. also teile nicht alle bis unten hin und merge danach alles zusammen.
so brauchste nur noch 10 dateien bei 103567*1000 elementen. ist doch schonmal was.

wenn du ganz pfiffig bist, kannste sogar einen datei-generator machen, der die die riesen-datei ausliest und stück für stück dateinamen liefert mit dateien, in denen (durch hauptspeichersortierung) sortierte blöcke liegen. der empfänger dieser dateinamen muß dann die wieder zusammenmergen. wird aber nicht einfach. ich nehme an, es läuft darauf hinaus, ne rekursion durch künstlichen stack nachzubilden.
das erlaubt dem generator, auch größere blöcke zu bilden, wenn die daten zum teil vorsortiert vorliegen. sagen wir mal, er benutzt insertionsort, um die blöcke zu schreiben. und wenn der block voll ist, wird einfach das erste element rausgeschrieben und weiter inserted. sobald das erste element aber rausgeschrieben ist, muss drauf geachtet werden, daß weitere inserts kein element vor den jetzrt im ram ersten platz schieben. sobald das der fall ist, muss die der ram-inhalt weggeschrieben werden und der neue block beginnt im ram mit dem element, was nicht eingefügt werden konnte.
so wird dein merge-sort unempfindlich gegen vorsortierte daten. bei ganz sortierten daten haste O(n).

insertionsort eleminiert das problem, erschafft allerdings dafür ein neues. gehen wir davon aus in der datei liegen mehrere hundert strukturen und insertionsort möcht nun beispielsweise relativ am dateianfang einfügen ...

und insertionsort hat das problem ständig. es ist im vergleich zu merge-sort einfach nur lahm.

danke erstmal für die schnelle antwort!

wie viele geöffnete dateien verkraftet ein betriebssystem im allgemeinen, windows im besonderen?
wenn ich den algorithmus implementiere muss ich ja den grenzwert abfangen ab dem das programm abschmieren würde ...

volkard

Darkseed schrieb:

wie viele geöffnete dateien verkraftet ein betriebssystem im allgemeinen, windows im besonderen?

auf FAT-platten ist das root-verzeichnis stark beschränkt. da ist nach ein paar-hundert eunfach schluss.

auf anderen platten gibts keine obergrenze, aber bei vielen dateien (so um 30000) wird alles extrem lahm.

wenn man tausende von dateien unter win anlegen muss, macht man unterverzeichnisse. also statt 00000.tmp 00001.tmp 00002.tmp macht man einfach 0\00\00.tmp 0\00\01.tmp 0\00\02.tmp

oder man läßt es und ist sich sicher, daß es auf dem nächsten windows keine probleme gibt.

wenn ich den algorithmus implementiere muss ich ja den grenzwert abfangen ab dem das programm abschmieren würde ...

nein, brauchste nicht.

du brauchst nur ld(dateianzahl) dateien *gleichzeitig*.
also bei 1000 dateien nur 10 gleichzeitig.
bei 1000000 dateien nur 20 gleichzeitig.
bei 1000000000 dateien nur 30 gleichzeitig.

wir wollen doch davon ausgehen, daß du immer weniger als 1000000000000 dateien brauchst und daß das dateisystem immer 40 dateien erlaubt. dann verzichte auf besondere maßnahmen.

warum so wenige dateien gleichzeitig?

ich nenne mal q die quelldatei und q->0 soll sagen, daß auis der quelldatei die datei namens 0 abgespalten wird. außerdem soll 0+1=0 heißen, daß die dateien 0 und 1 gemerged werden und der neue name 0 sein wird.

q->0_0
(1 datei)
q->0_1
(2 dateien)
0_0+0_1=1_0
(1 datei)
q->0_2
(2 dateien)
q->0_3
(3 dateien)
0_2+0_3=1_1
(2 dateien)
1_0+1_2=2_0
(1 datei)
q->0_4
(2 dateien)
q->0_5
(3 dateien)
0_4+0_5=1_2
(2 dateien)
q->0_6
(3 dateien)
q->0_7
(4 dateien)
0_6+0_7=1_3
(3 dateien)
1_2+1_3=2_1
(2 dateien)
2_0+2_1=3_0
(1 dateien)
q->0_8
(2 dateien)
q->0_9
(3 dateien)
0_8+0_9=1_4
(4 dateien)
q->0_10
(3 dateien)
q->0_11
(4 dateien)
0_10+0_11=1_5
(3 dateien)
1_4+1_5=2_2
(2 dateien)
usw...