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.

[Satty67]

Zitat:

Zitat von alzaimar

Die muss einen 'INTEGER' liefern, keinen 'ShortInt'! [...] Um doppelte Einträge *nicht* unter den Tisch fallen zu lassen, setze 'TcsStringSkipList.IgnoreDuplicates' auf FALSE.

Beides hatte ich schon geändert... SmallInt -> Integer hatte ich mich schon gefreut, aber bei wenn ich CompareText durch AnsiCompareText ersetze gibt es eine Zugriffsverletzung in INSERT.

Er weist q den Wert NIL (p^.ndfwd[k]) zu, was bei der nächsten Abfrage q^.ndKey dann halt schief geht.

IgnoreDuplicates hab' ich geändert und die Werte oben angepasst.

PS: Das Wörterbuch hat keine doppelten Einträge (bis auf zwei Leerzeile). Nachdem die Werte aber immer komischer wurden, wollte nur auf die schnelle eine Datei haben, die ich hier online stellen kann.

[himitsu]

ich hab grad mal dein Program (anderer Thread #1) auf eine 138 MB-Datei losgelassen (alzaimar's Zufallswertedatei)
und es meinte es war nach 220ms fertig ... tatsächlich waren es nur 14 Minuten
(prefetch 0 .. bei größeren werten bekam ich nach wenigen Seunden eine "Zu wenig Arbeitsspeicher."-Meldung)

[add]
ok, Stopuhr = Word = maximal ~65.000 millisekunden
[/add]

ich find es aber schon komisch, daß selbst bei einem Prefetch von 1 bei schon 188 MB Arbeitsspeicher (laut Taskmanager) OutOfMemory kommt :gruebel: (dein und mein Code)

[Satty67]

Ja StopUhr gehört Int64.

Die 138 MB Datei hat wohl nur sehr kurze/viele Zeilen? Das es aber schon bei 188 MB abbricht ist komisch, obwohl... der Taskmanager zeigt evtl. nicht allen Speicher an, den der MM reserviert.

[himitsu]

je 5-20 Zeichen pro Zeile

so, mein Laden/Speichern ist schneller, aber dafür dein sortieren

wobei ich grad eine 14 MB Datei / 1.000.000 Zeilen
mit Prefetsch 0
bei mir in 58 und bei dir in 70 Sekunden durchbekam :stupid:

[Satty67]

Ja, das hin und her und die vieln Beispiel verwirren... auch die ganzen Units mit gleichen Namen hätten mich fast meinen Code gekostet ;)

Werde morgen mal aktualisieren... jetzt bin ich zu Müde, da mache ich nur wieder was falsches. Aber der Int64 vs. Word Fehler bei der Stopuhr hat mich gleich eine Klasse basteln lassen (ich soll ja üben):

Delphi-Quellcode:

unit UStopUhr;

interface

type

TStopUhr = class
  private
    FStoppedTime : Int64;
    FStartTime,
    FStopTime : TDateTime;
  protected
    function GetStoppedTime: String;
  public
    Constructor Create;
    Destructor Destroy; Override;
    procedure Start;
    procedure Stop;
    property StartTime: TDateTime read FStartTime;
    property StopTime: TDateTime read FStopTime;
    property StoppedTime: Int64 read FStoppedTime;
    property StoppedTimeStr: String read GetStoppedTime;
  end;

implementation

uses SysUtils;

{ TStopUhr }

constructor TStopUhr.Create;
begin
  FStartTime := Now;
  FStopTime := FStartTime;
  FStoppedTime := 0;
end;

destructor TStopUhr.Destroy;
begin
  inherited;
end;

function TStopUhr.GetStoppedTime: String;
var
  Dbl : Double;
begin
  Dbl := FStoppedTime;
  Result := Format('%.0n ms',[dbl]);
end;

procedure TStopUhr.Start;
begin
  FStartTime := Now;
end;

procedure TStopUhr.Stop;
var
  Hour, Min, Sec, MSec: Word;
begin
  FStopTime := Now;
  DecodeTime(FStopTime - FStartTime, Hour, Min, Sec, MSec);
  FStoppedTime := MSec + (Sec * 1000) + (Min * 60 * 1000) + (Hour * 60 * 60 * 1000);
end;

end.

[alzaimar]

Zitat:

Zitat von Satty67

Er weist q den Wert NIL (p^.ndfwd[k]) zu, was bei der nächsten Abfrage q^.ndKey dann halt schief geht.

Das liegt daran, das beim AnsiCompareText der String #255#255 < 'YYY' ist. Die Skiplist benötigt eine Markierung für das Listenende. Diese Markierung muss einen Schlüssel enthalten, der größer als alle anderen ist. Er wird im Initialization-Abschnitt erzeugt. Du musst also nur die CompareKeys-Methode so ändern, das sie immer 1 liefert, wenn aKey1 = <EndeMarkierung> ist.

Dann wird das Teil genauso langsam/schnell wie Eure Versionen. Das liegt dann wohl eindeutig am 'AnsiCompareString'.

[himitsu]

wie wäre es eigentlich, wenn statt dem Prefetch ein Bäumchen für die ersten Buchstaben genutzt würde?
bei richtiger Implementierung dürfte dann, egal wie groß "prefetch" wäre, der Speicherverbrauch nicht (groß) ansteigen.

da könnte man dann beim Laden diesen baum schon teilsortiert anlegen und müßte dann nur noch die Zweige sortieren.

[Satty67]

Also gestern hatte ich erst wie blöd optimiert, dann 3 Stunden gesucht, wo ich bei der Optimierung einen Fehler reingebaut hab' ;)

Bäumchen dachte ich auch, nur braucht ein Node ja auch 2 Pointer (Parent/Childlist) oder? Wenn dann 1 Zeichen nicht reicht, sind es wieder >9 Byte pro Zeile. Evtl. kann man auf Parent verzichten, der Baum wird ja immer von oben abgetastet?

Wollte auch mit Array of Char arbeiten, aber der Vergleich kostet wieder enorm Zeit. Umwandeln in AnsiString -> AnsiCompareStr... und das ganze in eine Funktion, da sich sowas komplexes nicht mehr direkt in die Schleife integrieren lässt.

[himitsu]

ich hatte mal versucht das AnsiCompareString aufzusplitten
füllte vorher ein Array mit den Vergleichswerten und geh dann beim Vergleich darüber.

jupp, Parent hätt ich auch weggelassen (wenn man wirklich mal zurück muß, dann könnte man sich ja notfalls den Rückweg kurz merken)

[Satty67]

Ok, die neuen Werte mit hitsumi's und meiner optimierten Version:

Code:

SorterTestFile   himitsu(1)  himitsu(1b)  alzaimar(3)  satty(4)  Satty(4b)  TList.Sort(5)
==============
Prefetch=0       24781 ms    18640 ms     1735 ms      24968 ms  21656 ms   2515 ms
Prefetch=4       17937 ms    13969 ms     1706 ms      18791 ms  15435 ms
Prefetch=8       17171 ms    13813 ms     1757 ms      17328 ms  12547 ms
Prefetch=16      14797 ms    12250 ms     1735 ms      15172 ms   6906 ms
Prefetch=1024    14110 ms    11531 ms     1765 ms      14438 ms   4171 ms

Wörterbuch 8,5 MB
=================
Prefetch=1024     8375 ms     4641 ms     3156 ms       6750 ms   5609 ms

Sample.txt
==========
Prefetch=0                   51828/50906 ms                      66203 ms
Prefetch=4                   19140/9156 ms                       35110 ms
Prefetch=8                   18016/8188 ms                       29109 ms
Prefetch=16                  18313/8231 ms                       17766 ms
Prefetch=1024                18404/8119 ms                       11437 ms

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

Meine Version poste ich gleich... muss nur den Ordner noch aufräumen ;)

PS: Hatte gesucht, warum meine Version so schlecht skaliert... und gefunden!

PPS: Noch eine B-Version angehängt, macht nicht viel aus, aber im InsertSort-Teil fehlte noch was. CompareTextExact-Funktion fällt dadurch komplett weg.

***

Hab' beide Programme noch auf Sample.txt losgelassen, dass Dein Programm erzeugen kann. Da musste ich schon QuickSort ab 20 einstellen, um mithalten zu können. Der InsertPart bringt kaum was bei so verwürfelten Texten. Immerhin skaliert mein Programm ganz gut (und frisst viel zu viel Speicher) ;)

[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 :gruebel:

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 :mrgreen: )

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:

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 :-D

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 :stupid: ) 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