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

[Satty67]

@himitsu:

hab' gerade festgestellt, dass Dein Programm bei offenem FireFox Browser nur halb so schnell ist bei Prefetch > 0. Ist der Browser geschlossen, gibt es richtig Gas. Das kann ich beliebig wiederholen... Browser offen -> langsamer, Browser geschlossen -> schnell. Nur Prefetch= 0 zeigt nahezu gleiche Werte

Die anderen Programme sind nicht derart beeinflusst...

Die schnelleren Werte hab' ich im Post oben auch mit dazu.

[alzaimar]

Satty67 und Himitsu: Die AnsiCompareStr / AnsiCompareText Funktionen sind ja unglaublich langsam. Ich habe mir erlaubt, dies etwas zu optimieren. Die Grundidee ist die, anhand der AnsiCompareXXX-Routinen eine 'SortOrder'-Tabelle für einzelne Zeichen zu erzeugen und die Strings Zeichen für Zeichen mit Hilfe dieser Tabelle zu vergleichen.

Dazu erstelle ich ein Array Of Char, mit A[c] = c. Danach sortiere ich dieses Array mit Hilfe der Ordnungsfunktion 'AnsiCompareStr'. Der Index des Zeichens 'C' ist also seine Ordnung. Wenn Index[C] > Index [D] (C und D sind Zeichen), dann liegt C in der Sortierreihenfolge hinter D. Logisch, irgendwie.

Nun nehme ich mir diese Indexfunktion und vergleiche mit ihrer Hilfe zwei Strings Zeichen für Zeichen. Ich vergleiche also nicht die Zeichen direkt, sondern ihren Index.

Hier die Routinen:

Delphi-Quellcode:

Var
  SortOrder : Array [Char] Of Integer;

Procedure CreateSortOrder;
var
  Samples: array[Char] of String;
  c, d, h: Char;

begin
  for c := #0 to #255 do
    Samples[c] := c;

// Bubblesort the array
  for c := #0 to #255 do
    for d := succ(c) to #255 do
      if AnsicompareStr(Samples[c], Samples[d]) > 0 then begin
        h := Samples[c];
        Samples[c] := Samples[d];
        Samples[d] := h
      end;

// Create the 'Index'-function
  for c := #0 to #255 do
    SortOrder[Samples[c]] := Ord(c);
end;

Und nun die Vergleichsfunktion

Delphi-Quellcode:

function FasterAnsiCompareString(const aKey1, aKey2: string): Integer;
Var
  P1,p2 : PChar;

Begin
  p1 := @aKey1[1];
  p2 := @aKey2[1];

  While (SortOrder[p1^] = SortOrder[p2^]) and (p1^<>#0) and (p2^<>#0) do Begin
     inc(p1);
     inc(p2);
  End;
  if SortOrder[p1^] = SortOrder[p2^] then
    Result := 0
  else if p1^ = #0 then 
    Result := -1
  else if p2^ = #0 then 
    Result := 1
  else Result := SortOrder[p1^]-SortOrder[p2^];
end;

Ich habe es ein wenig getestet, aber bitte prüft nochmal. Es ist 'etwas' schneller als AnsiCompareStr (bei mir: 43x )

Das, und eine robustere Version der Skiplists sollte die Disqualifikation aufheben. Auf meinem Laptop wird die Testdatei in 2300ms so sortiert, wie Satty67 es wünscht.

[Satty67]

Also hab jetzt erst mal schnell die neue Version von csSkipList (noch ohne AnsiCompareStr) getestet.

Liegt bei der schwierigsten Datei Sample.txt deutlich vorne mit 4.500 ms (gegenüber 8.100 bzw 11.200 ms). Speicher-Einstellung hat bei der relativ kleinen Datei kaum Auswirkung auf die Zeit, weshalb mit 60 MB viel Luft für deutlich größere Dateien ist.

Ich baue dann noch heute noch die schneller Version von AnsiCompareStr in meine Klasse und in csSkipList ein und schaue was bei rauskommt.

[alzaimar]

Zitat von Satty67:

Ich baue dann noch heute noch die schneller Version von AnsiCompareStr in meine Klasse und in csSkipList ein und schaue was bei rauskommt.

Schau dir einfach die Unit 'UTextFilesorter.Pas' an. Dort wird eine abgeleitete Klasse 'TStringSorterSkipList' deklariert, die den schnelleren Vergleich implementiert.

[Satty67]

Ja, gerade das Ergebnis begutachtet, ist ja schon implementiert. Hatte schon TTextFileSorter aus der Unit genommen.

Also hier nochmal ein paar Werte:

Code:

.
                 SorterTestfile                        Sample.txt
                 FileIO/AnsiCompStr/FasterAnsiComStr   FileIO/AnsiCompStr/FasterAnsiComStr
csFasterSkipList    ---  /  ---    / 1875 ms             ---    /  ---     / 4375 ms
QuickInsertSort   800 ms / 4171 ms / 2203 ms            1800 ms / 11437 ms / 4688 ms

FileIO ist nur Laden/Speichern, hab' ich einfach durch ausklammern der Sort.Routine ermittelt.
SorterTestfile ist eine vergleichsweise einfach zu sortierende Datei (zum Sortierung Testen)
sample.txt ist die schwierig zu sortierende Datei (mit himitsus Frontend in default Einstellung erstellt)

Dank FasterAnsiCompareStr bekommt meine Routine einen Schub von bis zu 60%! Einfach genial

csFasterSkipList liegt noch knapp vorne, kann aber zusätzlich durch die flexible Speicherverwaltung punkten (bleibt also locker Sieger) und diesmal ganz legal mit passender Sortierung.

Also ich denke damit sollte der Thread-Starter ein optimales Tool in der Hand haben:

TTextFileSorter mit csFasterSkipList

ich hab' immerhin Klassen ganz lieb gewonnen und einen klassischen Code (den ich wenigstens in der Funktion verstehe ) der immerhin ganz gut mithalten kann.

Ob himistu noch nachlegen kann weis ich nicht, sein Programm war zum Teil besser als meines, da könnte noch was gehen...

[Dipl Phys Ernst Winter]

Ich verstehe nur Bahnhof!
Was soll eigentlich sortiert werden?
Zeilen nach ihrer Länge? Dazu passt 'alphnumerisch' nicht.

Die Wörter? Die müßten erst aus der Datei herausgezogen werden.
Ein Wort soll nur alphanumerische Zeichen enthalten, alle anderen Zeichen sind Trennzeichen. Damit ist eine Wortliste zu erstellen, wobei man die Datei zeilenweise lesen kann.

Diese ist bereits alphanumerisch sortiert, womit die Aufgabe erledigt wäre

[Satty67]

Was ursprünglich sortiert werden sollte, wurde nie bekannt

Aber getestet wurde es an einem Wörterbuch (Wort pro Textzeile, bis zu 1.000.000 Zeilen), das in unkonventionell sortierter oder unsortierter Form vorliegt. Später zur besseren Vergleichbarkeit dann himitsus/alzaimars zufällig generierte Textdatei.

Sortieren war nie das Problem... Aufgabe war: Arbeitsspeicher schonen und Schnelligkeit.

alzaimars Methode war nahezu perfekt, bis auf die Tatsache, das nur er es verstanden hat... glaube ich zumindest

[Satty67]

/self Quote, Sorry