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

[Satty67]

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 (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

[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 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)