AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Sprachen und Entwicklungsumgebungen Object-Pascal / Delphi-Language Delphi Große Datei sortieren ohne komplett in den Speicher zu laden

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

Ein Thema von k6n · begonnen am 12. Mär 2009 · letzter Beitrag vom 27. Mai 2009
Antwort Antwort
Seite 7 von 7   « Erste     567
Satty67

Registriert seit: 24. Feb 2007
Ort: Baden
1.566 Beiträge
 
Delphi 2007 Professional
 
#61

Re: Große Datei sortieren ohne komplett in den Speicher zu l

  Alt 18. Mär 2009, 18:43
@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.
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#62

Re: Große Datei sortieren ohne komplett in den Speicher zu l

  Alt 18. Mär 2009, 20:38
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.
Angehängte Dateien
Dateityp: rar textsorter_710.rar (4,0 KB, 13x aufgerufen)
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Satty67

Registriert seit: 24. Feb 2007
Ort: Baden
1.566 Beiträge
 
Delphi 2007 Professional
 
#63

Re: Große Datei sortieren ohne komplett in den Speicher zu l

  Alt 18. Mär 2009, 21:08
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.
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#64

Re: Große Datei sortieren ohne komplett in den Speicher zu l

  Alt 18. Mär 2009, 21:24
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.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Satty67

Registriert seit: 24. Feb 2007
Ort: Baden
1.566 Beiträge
 
Delphi 2007 Professional
 
#65

Re: Große Datei sortieren ohne komplett in den Speicher zu l

  Alt 18. Mär 2009, 21:49
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...
Angehängte Dateien
Dateityp: 7z utextfilesorter_satty_18.03.09_c_581.7z (921,4 KB, 22x aufgerufen)
  Mit Zitat antworten Zitat
Dipl Phys Ernst Winter

Registriert seit: 14. Apr 2009
Ort: Jena
103 Beiträge
 
Delphi 3 Professional
 
#66

Re: Große Datei sortieren ohne komplett in den Speicher zu l

  Alt 27. Mai 2009, 20:02
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
Angehängte Dateien
Dateityp: zip wortliste_198.zip (114,7 KB, 8x aufgerufen)
Autor: DP Ernst Winter
  Mit Zitat antworten Zitat
Satty67

Registriert seit: 24. Feb 2007
Ort: Baden
1.566 Beiträge
 
Delphi 2007 Professional
 
#67

Re: Große Datei sortieren ohne komplett in den Speicher zu l

  Alt 27. Mai 2009, 20:07
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
  Mit Zitat antworten Zitat
Satty67

Registriert seit: 24. Feb 2007
Ort: Baden
1.566 Beiträge
 
Delphi 2007 Professional
 
#68

Re: Große Datei sortieren ohne komplett in den Speicher zu l

  Alt 27. Mai 2009, 20:36
/self Quote, Sorry
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +2. Es ist jetzt 04:11 Uhr.
Powered by vBulletin® Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf