FileQuickSort (Dateien mit wenig Speicherlast sortieren)

[Satty67]

Hatte ich erst auch nicht verstanden, bei PrefetchSize = 0 sollte ja der Zeitaufwand gleich sein. Aber ist es nicht. Test-Datei und Sortier-Routine ist ja bis auf die andere Behandlung der Zeilen identisch.

da ich mich aber auch gleichzeitig noch mit der Klasse an sich beschäftigt hatte, ist da möglicherweise noch ein Fehler drin:

Delphi-Quellcode:

{<--- Holt eine Textzeile aus der Quell-Datei --->}
function TTextFileSorter.LineFromFile(Row : Integer): AnsiString;
var
  CharStr : PAnsiChar;
  index : TLineIndex;
begin
  index := FFileIndex[Row];
  CharStr := StrAlloc(Index.size +1);
  FillChar(CharStr^, Index.size +1, #0);
  FInFileStream.Seek(Index.offset, soFromBeginning);
  FInFileStream.Read(CharStr^, Index.size);
  Result := CharStr;
  StrDispose(CharStr);
end;

{<--- Holt eine Textzeile via Index-Werte --->}
function TTextFileSorter.GetIndexLine(Row: Integer; LineTyp: TGetLineTyp): AnsiString;
begin
  case LineTyp of
    glt_File      : Result := LineFromFile(Row);
    glt_FileUpper : Result := AnsiUpperCase(LineFromFile(Row));
    glt_Prefetch  : Result := FFileIndex[Row].prefetch;
  end;
end;

{<--- Vergleicht Strings genau, also bei Bedarf nachladen --->}
function TTextFileSorter.CompareLinesExact(Row1, Row2 : Integer) : Integer;
begin
  Result := CompareStr(GetIndexLine(Row1, glt_Prefetch),GetIndexLine(Row2, glt_Prefetch));
  // Prefetch gleich, dann aus Quell-Datei vergleichen
  if Result = 0 then
    Result := CompareStr(GetIndexLine(Row1, glt_FileUpper),GetIndexLine(Row2, glt_FileUpper));
end;

{<--- Quicksort des Index mit Nachladen einer Zeile bei Bedarf --->}
procedure TTextFileSorter.SortIndex(LoIndex, HiIndex: Integer);
var
  LoIdx, HiIdx, PivotIdx: Integer;
  Swap : TLineIndex;
  Promille : Integer;
begin
  if FCancelSort then Exit;

  // Lokalen Indexbereich bilden
  LoIdx := LoIndex;
  HiIdx := HiIndex;
  PivotIdx := (LoIndex + HiIndex) div 2;

  repeat
    while CompareLinesExact(LoIdx, PivotIdx) < 0 do Inc(LoIdx);
    while CompareLinesExact(PivotIdx, HiIdx) < 0 do Dec(HiIdx);
    //while GetLine(LoIdx, LineTyp) < Pivot do Inc(LoIdx);
    //while Pivot < GetLine(HiIdx, LineTyp) do Dec(HiIdx);

    if LoIdx <= HiIdx then begin
      if LoIdx < HiIdx then begin
        Swap := FFileIndex[LoIdx];
        FFileIndex[LoIdx] := FFileIndex[HiIdx];
        FFileIndex[HiIdx] := Swap;
      end;
      Inc(LoIdx);
      Dec(HiIdx);
    end;

  until LoIdx > HiIdx;

  // NotifyEvent nur alle 0,1% aufrufen
  if Assigned(FOnSorting) then begin
    Promille := (LoIndex * 1000) div Length(FFileIndex);
    if Promille > FLastPromille then begin
      FLastPromille := Promille;
      FOnSorting(self, tfsSorting , Promille div 10, FCancelSort);
    end;
  end;

  if LoIndex < HiIdx then SortIndex(LoIndex, HiIdx);
  if LoIdx < HiIndex then SortIndex(LoIdx, HiIndex);
end;

Beim Anlegen der Ziel-Datei wird jetzt nur noch Zeile gelesen -> geschrieben

Evtl. könnte man hier

Delphi-Quellcode:

  while CompareLinesExact(LoIdx, PivotIdx) < 0 do Inc(LoIdx);
  while CompareLinesExact(PivotIdx, HiIdx) < 0 do Dec(HiIdx);

Auf Prefetch=0 prüfen und direkt die Dateizeilen (ohne Aufruf von CompareLinesExact) laden.

[Satty67]

Zitat von alzaimar:

Dein Lösungsansatz widerspricht zudem deiner Eingangs gemachten Vorgabe ('Dateien mit wenig speicherlast sortieren').

TStringList liest die Datei komplett ein und ist auch bei genug Speicher die richtige Variante.

Im Ausgangs-Thread (siehe Post#1) ging es um Textdateien ab 300 MB, die eben nicht komplett in den Speicher sollen.

Folgende ungünstige Ausgangs-Situation (ungünstig, da kurze Zeilen):

Wörterbuch mit Zeilen bis 20 Buchstaben Länge.
Prefetch ist auf 5
Dann wird nur ca 25% in den Speicher eingelesen (etwas Overhead durch den Index)
Die ganzen Zeilen werden ja nur zum Vergleichen gelesen und danach wieder verworfen.

Je größer die durchschnittliche Länge einer Zeile, desto geringer der prozentuale Speicherbedarf.

[Satty67]

@alzaimar

Den zusätzlichen Funktionsaufruf bei Prefetch=0 ausklammern hat was gebracht, aber nur bei Prefetch=0;

Delphi-Quellcode:

PivotIdx := (LoIndex + HiIndex) div 2;
PivotFullText := LineFromFile(PivotIdx);

repeat
  if FPrefetchSize = 0 then begin
    while LineFromFile(LoIdx) < PivotFullText do Inc(LoIdx);
    while PivotFullText < LineFromFile(HiIdx) do Dec(HiIdx);
  end else begin
    while CompareLinesExact(LoIdx, PivotIdx) < 0 do Inc(LoIdx);
    while CompareLinesExact(PivotIdx, HiIdx) < 0 do Dec(HiIdx);
  end;

Prefetch=0 ist jetzt so schnell wie Prefetch=5 (1-4 sind langsamer). Also erst ab Prefetch=5 wird der zusätzliche Vergleich durch den genaueren SpeicherIndex kompensiert.

Ich müsste dann also ab Prefetch=6 auf die alte Methode zurückgreifen, um in jeder Situation am schnellsten zu sein. Kommt aber wohl auch etwas auf die Quelle an.

[alzaimar]

Zitat von Satty67:

Wörterbuch mit Zeilen bis 20 Buchstaben Länge.
Prefetch ist auf 5
Dann wird nur ca 25% in den Speicher eingelesen (etwas Overhead durch den Index)

Ein bisserl mehr ist es schon.
Ein (Ansi)String ist ein Zeiger (4 Bytes) auf eine Struktur, die die Länge (4 Bytes) + Referenzzähler (4 Bytes) enhält. Danach folgt der String sowie 2 Nullen (2 Bytes) am Ende des Strings. Macht also 14 Bytes Overhead pro String (hier nachzulesen).
Dein FileIndex verbrät also je Zeile neben dem Prefetch 26 Bytes an Overhead. (14 Bytes vom String, 8 Bytes vom Record und 4 Bytes vom Array). Somit enthält dein FileIndex mehr Daten, als die Datei groß ist.

Wozu benötigst du das denn? Vielleicht gibt es andere Datenstrukturen, um dein Problem zu lösen.

[Satty67]

Zitat von alzaimar:

Ein (Ansi)String ist ein Zeiger (4 Bytes) auf eine Struktur, die die Länge (4 Bytes) + Referenzzähler (4 Bytes) enhält. Danach folgt der String sowie 2 Nullen (2 Bytes) am Ende des Strings.

Gut, der verwendete Datentyp für den Prefetch-String sollte geändert werden. Zwar relativiert sich das bei längeren Zeilen, aber die sind ja nicht garantiert.

Die 8,5 MByte große Testdatei (600.000 Zeilen) belegte bei mir mit Prefetch=0 ca. 4 Mbyte, bei Prefetch=1024 sind es 23 Mbyte. Da muss ich also dringend was ändern.

Zitat von alzaimar:

Wozu benötigst du das denn?

Gar nicht... im Initial-Thread hast Du ja auch Vorschläge gemacht, gebraucht hat das ein anderer. Das ist einfach nur der Reiz ein Problem zu lösen.

[alzaimar]

Zitat von Satty67:

Gar nicht... im Initial-Thread hast Du ja auch Vorschläge gemacht, gebraucht hat das ein anderer. Das ist einfach nur der Reiz ein Problem zu lösen.

Ich würde:
1. Den Prefetch als String[X] (x<=5) statisch deklarieren, somit entfällt ein Großteil des Overheads.
2. Einen Cache zwischenschalten (auch eine Prima Übung).

Der Cache merkt sich die N zuletzt gefetchten Zeilen. Bevor Du eine Zeile aus der Datei liest, fragst Du, ob sie schon im Cache vorhanden ist. Wenn ja, ist gut. Wenn nicht, liest Du sie aus der Datei und packst sie in den Cache. Wenn der Cache voll ist, schmeisst er die am längsten nicht abgefragte Zeile aus dem Speicher raus. Hier musst Du einiges an Gehirnschmalz investieren, damit der Cache nicht zu langsam wird. Speziell das 'Suchen' und 'die am längsten nicht abgefragte Zeile' dürften etwas kniffelig zu implementieren sein, wenn man es richtig schnell machen will.

Vielleicht reicht es, sich die jeweils 3 zuletzt gelesenen Zeilen zu merken. Dann würdest du das Pivot-Element nur 1x pro Sort nachladen müssen. Zudem kannst Du Dir überlegen, kleinere Bereiche (< 10000 Zeilen) komplett in den Speicher zu laden, zu sortieren, und wieder abzuspeichern. Das sollte die Sortierung nochmals vorantreiben

[Satty67]

Gut, also den Datentyp muss ich ändern. Angedacht war ja auch ein array of Char, was aber wieder aufwändiger als ein ShortString wäre. Das hat priorität, weil das ganze ja sonst kein Sinn macht.

TStringList verbrät übrigens mit 29 MB noch mehr Speicher, da wäre ich mit meinen 4 MB ja schon mit der jetzigen Version ganz gut im Rennen. Gleich schnell bin ich aber nur, wenn ich mir auch 23 MB nehme.

***

Caching wird ein wichtiges Thema, das ich mir als zweiten Schritt vornehmen muss. ich denke ich fange mir einem kleinen Cache an, dann kann ich eine korrekte Verwaltung besser kontrollieren. Arbeitet die Verwaltung korrekt, sollte ein Vergrößern dann auch kein Problem sein.

[Luckie]

Also ich habe mir mal deine Klassen Deklaration angeguckt, sieht gut aus.

[alzaimar]

Ich habe mal den Algorithmus im Wiki nachgebaut. Der Vorteil ist, das man den Speicherbedarf festlegen hat. Das Verfahren degeneriert also nicht und funktioniert auch bei beliebig großen Dateien, ist dafür aber langsamer. [Edit]: Nö, sogar schneller.

Im Prinzip passiert Folgendes:

1. Eingabedatei wird in einzelne Abschnitte a <MaxSize> Bytes unterteilt:
1.1 Es werden solange Zeilen eingelesen, bis die Gesamtgröße <MaxSize> erreicht.
1.2 Diese Stringliste wird in-memory sortiert (TStringlist.Sort)
1.3 Abschließend wird diese Liste in einer temporären Datei gespeichert.
2. Ein K-Merge Algorthmus vermischt die K-temporaren Dateien (jeweils sortiert)

Dabei ist (1.2) der eigentliche Bottleneck, obwohl Quicksort zu den schnellsten Sortieralgorithmen gehört.

Kann man das optimieren?

Antwort: Ja.

Der Trick: Wir verwenden eine spezielle (String)Listenstruktur, die Strings beim Einfügen gleich sortiert ablegt und speichern dann den Inhalt in einer Datei ab. Normalerweise würde man das mit einem Array machen, per Binärsuche die Einfügeposition suchen und dort einfügen. Man könnte auch einen Binärbaum verwenden. Das ist aber unter dem Strich nicht schneller als Quicksort, da beide Verfahren vom Aufwand O(log n) sind. Was also tun?

Glücklicherweise existiert eine Listenstruktur, die wesentlich schneller ist: SkipLists. Der Aufwand zum Einfügen eines Objektes ist annähernd O(1), ggü O(log n) bei Binärsuche. Beim Einfügen von n Elementen werde ich also mit einer Skipliste in O(n) fertig sein, ggü O(n log n) bei einer Binärsuche bzw. Quicksort.

Herkömlicher Code:

Delphi-Quellcode:

While not Eof (Inputfile) do begin
  ReadLn (Inputfile, sText);
  sStringList.Add (sText);
End;
sStringList.Sort;
sStringList.SaveToFile (OutputFilename);

optimierter Code;

Delphi-Quellcode:

While not Eof (Inputfile) do begin
  ReadLn (Inputfile, sText);
  sSkipList.Add (sText);
End;
Assignfile (OutputFile, OutputFilename);
Rewrite (OutputFile);
sSkipList.First; // Iterator auf 1.Element setzen
While Not sSkipList.EndOfLine Do Begin // Solange noch Elemente in der Liste sind
  Writeln (OutputFile, sSkipList.CurrentKey); // Aktuellen Iterator-Wert speichern
  sSkiplist.Next; // Zum nächsten Wert gehen
End;
CloseFile (OutputFile);

Anstatt also eine Stringliste zu füllen und anschließend zu sortieren, fülle ich eine Skiplist und speichere den Inhalt ab, indem ich die Liste sequentiell von vorne nach hinten durchlaufe. Der Inhalt ist damit automatisch sortiert

Mit dieser Optimierung sortiert die vorgestellte Klasse eine 6MB-Textdatei in 1.6 anstatt 6.3 Sekunden (bei 1MB Puffer).
150MB werden in 60 Sekunden sortiert, ggü. 160 Sekunden mit herkömmlichem Sort (bei 10MB Puffer).

Auch wenn die hier vorgestellte Klasse langsamer sein sollte, als Satty67's Version (wovon ich mal ausgehe), könnte man das Skiplist-Verfahren auf seine Klasse anwenden, um sie noch weiter zu optimieren.

[Satty67]

Angewendet auf meine Wörterbuch (wegen der Vergleichbarkeit):

Mit Defaultwert aMemoryToUse=10.000.000 belegt es ~59 MB Arbeitsspeicher.
Mit aMemoryToUse=1.000.000 nur noch ~7 MB
(Im Taskmanager sieht man das schlecht, weil es so fix ist)
Das Ding ist in der Version ganz schön schnell (~2200 ms)

Sortiert in der Version jetzt noch Binär, statt alphanumerisch (bei meiner wenigstens A-Z/a-Z korrekt), aber selbst bei Verdoppelung der Zeit, wird es damit nicht langsamer als die QuickSort Variante (mit Speicher).

PS: Der QuickSort von Borland für TList ist 6% langsamer als mein QuickSort (um meine Ehre wenigstens noch zu retten)

Zitat von Luckie:

Also ich habe mir mal deine Klassen Deklaration angeguckt, sieht gut aus.

Danke, ein bisschen Lob kann ich jetzt gebrauchen. War am Ende auch nicht ganz so schlimm, auch wenn ich da noch nicht automatisiert arbeiten kann.

€: gerade gewundert warum bei der SkipList-Klasse die Ergebnisliste kleiner ist. SkipList entfernt doppelte Einträge... müsste man entsprechend ändern, wenn die Datenmenge nicht verändert werden darf.