Große Datei sortieren ohne komplett in den Speicher zu laden

[Satty67]

Zitat:

Zitat von himitsu

stimmt denn wenigstens die Sortierung?

Dauert noch etwas... die ganze Familie kontrolliert z.Z. noch mit... sind bei Zeile 498.385.

Scherz beiseite... sortiert PERFEKT!

Ubel > ubel > Übel > übel und Z am Ende, nicht die Umlaute

Zitat:

nicht wegen der eingebauten Funktion AnsiCompareText wundern

Sowieso nicht... veruche selber mich langsam daran zu gewöhnen AnsiString statt String zu schreiben. Ist bei D5 noch egal, aber eben wegen der geplanten Umstellung.

Aber denke das genau die korrekte Sortierung die Zeit kostet, auch AnsiUpperCase (das ja noch die Umlaute hinten lässt) kostet enorm Zeit.

Zitat:

nicht immer #13#10 als Zeilentrennung vorhanden sein

Ja... das sind die Dinge die ich immer vergesse. Gibt ja noch Linux und Mac konforme Dokumente.

[Satty67]

Ich hab' bei mir jetzt auch AnsiCompareStr (gleich schnell wie AnsiCompareText) eingebaut. Das hätte ich gleich machen sollen, so sortiert es richtig.

Dadurch konnte ich AnsiUpperCase beim Zeilen Laden entfernen:

Prefetch=0 : 37062 ms
Prefetch=1024 : 6536 ms

Also macht das beim Speicher-Sortieren sehr viel aus. Braucht doppelt solange, aber immer noch fix ;) Reines Datei-Sortieren ist dabei minimal schneller geworden, warum auch immer.

..und die SkipList vergessen wir, das muss ein Objekt aus der Hölle sein. Das kann nicht menschlich sein :twisted:

Ich baue dann noch QuickSort mit InsertSort ein, das bring beim Sortieren nochmal 20-25%. Folgenden Code hab ich mit einer Stringliste getestet und mit purem Quicksort verglichen:

Delphi-Quellcode:

{<<<< QuickInsertSort >>>>}
procedure TFormTestSorter.QuickInsertSort(L,R: Integer);
var
  I, J : integer;
  S, P : String;
begin
  // QuickSort für Elemente, die weiter auseinander liegen
  if (R - L) > 23 then begin

    i := l;
    j := r;
    p := StringList[(l+r) DIV 2];

    repeat
      while StringList[i] < p do i := i + 1;
      while StringList[j] > p do j := j - 1;

      if i <= j then begin
        if i < j then begin
          s := StringList[i];
          StringList[i] := StringList[j];
          StringList[j] := s;
        end;
        i := i + 1;
        j := j - 1;
      end;
    until i > j;

    if l < j then QuickInsertSort(l, j);
    if i < r then QuickInsertSort(i, r);

  // InsertionSort für Element-Entfernungen unter 24
  end else begin

    for I := L + 1 to R do begin
      if (StringList[I] < StringList[I - 1]) then
      begin
        S := StringList[I];
        J := I;
        while ((J > L) and (StringList[J - 1] > S)) do
        begin
          StringList[J] := StringList[J - 1];
          J := J - 1;
        end;
        StringList[J] := S;
      end;
    end;

  end;
end;

[alzaimar]

Ich darf doch nochmals daran erinnern, daß ihr bei großem 'Prefetch' eigentlich die gesamte Datei einlest und In-Memory sortiert, sodaß man auch gleich eine TStringlist mit 'Sort' verwenden könnte, oder irre ich mich?

[Satty67]

Ja fast... TStringList ist aber noch schlimmer. Verglichen mit der 8,5 MByte Datei (600.000 Zeilen), da braucht TStringList 29 MByte Speicher. Also das 3,5 fache... wie weit das skaliert, hab ich allerdings nicht getestet. Prefetch=1024 ist dann ja auch nur, um die Sortieralgorythmen zu testen... bei kurzen Zeilen ist aber auch Prefetch=0 nicht sehr effizient (auf den Overhead hast mich ja aufmerksam gemacht)

Dann ist TSringList auch extrem langsam... hat zwar intern eine QuickSort-Variante verbaut, aber verliert irgenwo Zeit für die Verwaltung. Wenn ich mit Quicksort die Liste "von Hand" sortiere bin ich schon um 40% schneller. (SkipList war 90% schneller, wenn ich mich recht erinnere!)

Jetzt brauchen wir ja nicht um den heißen Brei reden... das ganze kann nur noch Spass am programmieren sein. An die Leistung, die deine Klasse mit der SkipList bring, kommen wir mit konventionellen Methoden im Leben nicht ran.

Ich hab' auch schon den Code der Skiplist analysiert... da bastel ich noch ein AnsiCompareStr rein. Zudem will ich eine CallBack-Funktion, wofür ich noch die richtigen Stellen suche (Obwohl wohl auch eine Meldung "Bitte kurz warten..." reichen würde :lol: ). Das Ergebnis poste ich dann natürlich.

Zitat:

Zitat von himitsu

bei [i]Offset := Offset + FileIndex.size + 2; mußt du aufpassen, denn es muß nicht immer #13#10 als Zeilentrennung vorhanden sein :!:

Ich hab' gestern noch Deine TextFile-Pos verbaut, funktioniert prima!

[alzaimar]

Satty67, in der letzten von mir geposteten Version ist eine angepasste SkipList, be der Du nur die virtuelle Methode 'CompareKeys' überschreiben musst, so etwa:

Delphi-Quellcode:

Type
  TMySkipList = Class (TcsStringSkipList)
  Protected
     Function CompareKeys (Const aKey1, aKey2 : String) : ShortInt; Override;
  End;
...

Function TMySkiplist.CompareKeys (Const aKey1, aKey2 : String) : ShortInt; 
Begin
  // ..Hier die eigene 'Compare'-funktion
End;

Und -wupps- hast Du schon einen Vorteil der OOP: Überschreiben von Methoden zur Anpassung der Funktionalität.

Diese "TMySkipList" kannst Du dann verwenden.


P.S.: Wieso verbesserst Du deinen Code nicht mit dem SkipList-Sortieren?

[himitsu]

sag mal, hattest du zufällig bei deinem Geschwindigkeitstest diese Zeile bemerkt?

Delphi-Quellcode:

Const TempSize = {64 * 1024}128;      // 64 KB

hatte zum Testen, ob der richtig einliest, die Größe verringert und wohl vergessen es wieder rauszunehmen :oops:

so wäre es richtig:

Delphi-Quellcode:

// Zeile 28+29
    Const TempSize   = 64 * 1024;                           // 64 KB
      FileIndexBlock = 1024 * 1024 div SizeOf(TLineIndex);  //  1 MB

[Satty67]

Gesehen, aber nichts bei gedacht ;) Lasse eine Testreihe laufen... melde mich gleich wieder.

***

So... also nachdem ich komische Ergebnisse hatte, hab' ich gleich mal eine Test-Datei erstellt:

500.000 Random-Lines A-Z (variable Länge 1-20 Zeichen), zusätzlich ubel, Ubel, übel & Übel um DIN-Sortierung zu testen. Die Datei ist in der Anlage (ausgepackt knapp 6 MB).

Zuvor hatte ich ja ein 600.000 Zeilen starkes Wörterbuch, das aber A-Z vor a-z sortiert hatte (ich sortierte gleich Case Insensitive, weshalb das gut zum Testen war). Die Werte der neuen Datei schmettern mich aber nieder...

Code:

SorterTestFile   himitsu(1)  himitsu(2)  alzaimar(3)  satty(4)  TList.Sort(5)

Prefetch=0      24781 ms    36641 ms    1735 ms       24968 ms  2515 ms
Prefetch=4      17937 ms    29672 ms    1706 ms       18791 ms
Prefetch=8      17171 ms    28516 ms    1757 ms       17328 ms
Prefetch=16     14797 ms    26344 ms    1735 ms       15172 ms
Prefetch=1024   14110 ms    26000 ms    1765 ms       14438 ms

Wörterbuch 8,5 MB

Prefetch=1024   8375 ms     22125 ms    3156 ms      6750 ms   3640 ms

(1) TempSize 128 Byte, API-Funktionen
(2) TempSize 64 KB
(3) csSkipList, Keine DIN-Sortierung möglich! Vorerst noch disqualifiziert wegen cheaten.
(4) QuickInsertSort, relativ hoher Speicherbedarf
(5) Einfach aber auch großer Speicherbedarf, Ignoriert PrefetchSize

Jetzt muss man dazu sagen, das TList.Sort als Speicherliste schlechter sortiert. Boden geht hier wohl beim Laden aus der Datei verloren (TList läd' ja einfach alles rein).

Die Klasse csSkipList bekomme ich nicht zum Ansi-Sortieren. Blicke bei dem Teil immer noch nicht ganz durch, aber denke das es eine Binäre Einordnung der Strings braucht (AnsiCompareStr oder AnsiUpperCase bricht mit Zugriffsverletzung ab.. in Insert wählt der Code irgendwann einen Node.ndKey mit Wert NIL als Vergleichs-String).

PS: Das 64 K TempSize langsamer ist, ist kein Fehler... kannst ja jetzt selber testen... :gruebel:

€: Werte SkipList korrigiert (war noch ignoreDuplicates=True), ändert aber nicht viel...

[himitsu]

man erlebt immer wieder Wunder ... wie was nicht so geht, wie man denken würde :shock:

Zitat:

Jetzt muss man dazu sagen, das TList.Sort als Speicherliste schlechter sortiert.

wie schlechter sortiert?
(notfalls kannst'e auch da die Vergleichsroutine ersetzen)

[Satty67]

Zitat:

Zitat von himitsu

wie schlechter sortiert?

Also wenn die Liste im Speicher ist und ich einfach Items via QuickSort sortiere bin ich 40% schneller gegenüber TList.Sort.

Will damit sagen, das TList nur dadurch so gute Werte hat, weil es ja einfach die Liste komplett einliest ohne auf den Speicher zu achten und dann wieder rausklatscht. Vorteil oben wird dadurch erkauft, dass Speicherbedarf bei 3,5x Dateigröße liegt.

Bei über 300 MB oder mehr sprengt TList den Speicher mancher Rechner... was ja zu umgehen war.

€: das die Logik beim Laden/Speicher das Problem ist, bestätigt noch ein anderer Umstand:

Bei einem 500.000 Items großen ArrayOfString sortiert QuickInsert etwa 23% schneller als reines QuickSort. Um genau zu sein in 1015 ms. In TextFileSort implementiert kommt da nur noch 2% bei rüber, d.h. der Sortierung-Algorithmus selbst ist nicht das Problem.

[alzaimar]

Zitat:

Zitat von Satty67

Die Klasse csSkipList bekomme ich nicht zum Ansi-Sortieren. Blicke bei dem Teil immer noch nicht ganz durch, aber denke das es eine Binäre Einordnung der Strings braucht (AnsiCompareStr oder AnsiUpperCase bricht mit Zugriffsverletzung ab..

Durchblicken ist auch nicht so einfach... Aber Der Grund für die AV ist die von mir schlampigerweise falsch deklarierte Funktion 'CompareStr'. Die muss einen 'INTEGER' liefern, keinen 'ShortInt'! :wall:

Um doppelte Einträge *nicht* unter den Tisch fallen zu lassen, setze 'TcsStringSkipList.IgnoreDuplicates' auf FALSE. Damit wird das Teil natürlich langsamer...

Verwende lieber eine Testdatei, die keine doppelten Einträge enthält. Dann sind die Messungen vergleichbarer.