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 4 von 7   « Erste     234 56     Letzte » 
alzaimar
(Moderator)

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

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

  Alt 13. Mär 2009, 21:59
Nach dem DRY-Prinzip ('Dont repeat yourself') solltest Du den Aufruf von GetStringLine so ändern, das die Zeilennummer (anstatt dem FileIndex) übergeben wird:
Delphi-Quellcode:
function GetStringLine(I : Integer; Upper : Boolean): string;
var
  CharStr : PAnsiChar;
  index : TIndex;

begin
  index := FileIndex[I];
  CharStr := StrAlloc(Index.size +1);
  FillChar(CharStr^, Index.size +1, #0);
  aSourceFileStream.Seek(Index.offset, soFromBeginning);
  aSourceFileStream.Read(CharStr^, Index.size);
  if Upper then
    Result := AnsiUpperCase(CharStr)
  else
    Result := CharStr;
  StrDispose(CharStr);
end;
"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
 
#32

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

  Alt 13. Mär 2009, 22:23
Aha... für sowas muss man aber ein Auge haben.

Also in dem Fall: Anstatt mehrmals beim Procedure-Aufruf FileIndex[I] schreiben zu müssen, nur "I" schreiben und die Zuweisung innerhalb der Procedure.

Ich geb' mir ja schon Mühe, den Quelltext sauber und strukturiert zu halten. Für solche Dinge, die mir Schreibarbeit sparen, müsste ich wohl mal ein spezialisiertes Buch lesen. Hab' da kaum Ahnung worauf man achten muss bzw. woran man das schnell erkennt.

PS: Hab' es natürlich übernommen, auch ein Teil von himitsu's Variante mit ReadLn zu arbeiten (leider nicht alles, da D5 nicht alles unterstützt). Eine CallBack-Procedure für Progress-Anzeige ist drin... usw. Wenn die Version (mit variabler StringGröße im Index) fertig ist, poste ich das ganze nochmal... in ein paar Monaten.
  Mit Zitat antworten Zitat
k6n

Registriert seit: 13. Feb 2009
13 Beiträge
 
#33

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

  Alt 14. Mär 2009, 01:28
Danke für die vielen super Vorschläge. Ich setz' mich mal dran und versuche es zu verstehen.
  Mit Zitat antworten Zitat
nahpets
(Gast)

n/a Beiträge
 
#34

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

  Alt 16. Mär 2009, 11:12
Hallo,

am Wochenende habe ich mal versucht, ein Programm zu schreiben, das auch große Dateien sortieren kann, ohne dabei allzuviel Speicher zu belegen.

Das Programm ist schnell beschrieben:

Man wähle eine Eingabedatei und eine Ausgabedatei. Wähle die Anzahl der Zeilen aus, die in einem Durchgang sortiert werden sollen, wähle, ob Groß-/Kleinschreibung berücksichtigt werden soll, und starte die Sortierung.

Was passiert nun beim Sortieren?

Die Eingabedatei wird in Teile mit der angegebenen Zeilenzahl aufgeteilt, wobei jeder Teil sortiert wird. Ist die Eingabedatei nun aufgeteilt und die Teile sind sortiert, so werden anschließend die Teile zusammengeführt und dabei wird die Sortierung beachtet. Sofern mehr als 3 Teile erstellt werden, erfolgt die Zusammenführung für vier Teildateien gleichzeitig, andernfalls werden zwei Dateien zusammengeführt.

Die Zusammenführung erfolgt in der Form, dass bei jeder Zusammenführung ein neuer Teil erstellt wird. Dieser Vorgang wird solange wiederholt, bis nur noch ein Teil übrig ist. Die einzelnen Teile werden, sobald sie zusammengeführt wurden gelöscht, um Plattenplatz im Temporärverzeichnis zu sparen. Insgesamt wird hierdurch maximal der zweifache Plattenplatz der Eingabedatei benötigt.

Der Speicherverbrauch des Programmes ist abhängig von der Größe der einzelnen Teile. Je mehr Teile erstellt werden, um so länger ist die Laufzeit des Programmes (es sei denn, dass der Speicherverbrauch so hoch wird, dass Windows die Auslagerungsdatei benutzen muss, dann bricht die Laufzeit stark ein). Bei der Verwendung kleinerer Teile ist der Speicherverbrauch geringer. Allerdings steigt der Speicherverbrauch bei sehr großen Teilen stark an. Welche Größe der einzelnen Teile optimal ist, muss durch Versuch und Irrtum ermittelt werden.

Für die Speicherung der Teile wird das Temporärverzeichnis aus %TEMP% benutzt. Es muss daher sichergestellt sein, dass dort ausreichend Platz zu Verfügung steht. Das Programm prüft, ob der Speicherplatz voraussichtlich ausreicht.

Für die Sortierung wird eine Stringliste benutzt, die für die Sortierung AnsiCompareStr bzw. AnsiCompareText verwendet. Die Sortierung weicht daher von einer Sortierung mit einfachen Größer-/Kleinervergleichen ab.

Das Programm ist weder objektorientiert noch nach irgendwelchen ästhetischen Gesichtspunkten gestaltet, sondern einfach nur nach dem Motto: geht das?

Wer Änderungswünsche hat, realisiere sie bitte und stelle die Ergebnisse hier zur Verfügung
Code:
Laufzeittest mit einer Textdatei von 307.949.380 Byte mit fester Zeilenlänge von 326 Byte.

Rechner 1: Pentium 3 mit 750 MHz und 512 MB Speicher
getrennte Festplatten für Daten, temporäres Verzeichnis und Auslagerungsdatei (3 Festplatten)

Größe der Teile in Zeilen - Laufzeit - Speicherverbrauch - Dateigröße der Teile
     10.000                 00:09:09   ca. 10.720 kByte        3.260.000 Byte
     20.000                 00:08:20   ca. 15.384 kByte        6.520.000 Byte
     50.000                 00:06:48   ca. 35.324 kByte       16.300.000 Byte
    100.000                 00:06:23   ca. 69.708 kByte       32.600.000 Byte
    200.000                 00:06:22   ca. 134.132 kByte       65.200.000 Byte
  1.000.000                 00:36:47   ca. 416.000 kByte      307.949.380 Byte
-------------------------------------------------------------------------------

Rechner 2: Pentium 4 mit 2 GHz und 1024 MB Speicher
eine Festplatte für Daten, temporäres Verzeichnis und Auslagerungsdatei

Größe der Teile in Zeilen - Laufzeit - Speicherverbrauch - Dateigröße der Teile
     10.000                 00:08:57   ca. 13.376 kByte        3.260.000 Byte
     20.000                 00:08:38   ca. 19.000 kByte        6.520.000 Byte
     50.000                 00:07:20   ca. 38.820 kByte       16.300.000 Byte
    100.000                 00:06:35   ca. 71.828 kByte       32.600.000 Byte
    200.000                 00:07:37   ca. 137.780 kByte       65.200.000 Byte
  1.000.000                 00:20:38   ca. 539.144 kByte      307.949.380 Byte
-------------------------------------------------------------------------------
Was schließen wir hier nun aus den Ergebnissen dieser beiden Vergleiche?
Schneller Rechner und viel Speicher sind bei großen Dateien von Vorteil, wenn sie "am Stück" verglichen werden, andernfalls ist die Geschwindigkeit der Festplatten für die Laufzeit nicht unerheblich.

Der Rechner 1 hat deutlich schnellere Festplatten als Rechner 2. Beide Rechner sind nicht unbedingt die neuesten (Alter: Rechner 1: 9 Jahre, Rechner 2: 4 Jahre).

Geändert von nahpets (21. Nov 2017 um 17:41 Uhr)
  Mit Zitat antworten Zitat
Satty67

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

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

  Alt 16. Mär 2009, 11:23
In dem Thread gibt es auch fertigen Code und Klassen zum Problem.

alzaimar hat eine SkipList angepasst und in eine Klasse gesteckt. Das Teil ist höllisch schnell bei wenig Speicherverbrauch. Die derzeit beste Lösung, die ich gesehen hab' um große Dateien elegant zu sortieren.

PS: 600.000 Zeilen / 8,5 MByte in weniger als 3 Sekunden. (Speicherbedarf kann frei gewählt werden)
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
38.256 Beiträge
 
Delphi 10.4 Sydney
 
#36

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

  Alt 16. Mär 2009, 17:17
hab mal das FileQuickSort von Satty67 aus Beitrag #27 von den alten Pascal-Funktionen befreit
und auf direkte WinAPI umgestellt (samt Angabe für Windows zur theoretisch "optiomaleren" Cacheverwaltung),

dann noch in der Callback-Prozedur die Statusstrings durch Enumeratoren ersetzt,

das "Cancel" in die Callback-Prozedur verlegt (Result = false = Abbruch)

und die einzelnen Fortschrittsanzeigen (Laden, Sortieren und Speichern) hintereinander gelegt.
(Laden 0% bis 25%, Sortieren 25% bis 75% und Speichern 75% bis 100%)

[add]
ich weiß jetzt nicht ob eventuell noch Fehler enthalten sind (nicht ausgibig getestet), aber hab hier grad mal eine 5 MB Datei in knapp 'ner Sekunde durchgejagt

[edit]
nicht das FileQuickSort hier auf Beitrag #27, sondern das aus Beitrag #1 im anderem Thread
Angehängte Dateien
Dateityp: 7z filequicksort_v1.0_339.7z (4,6 KB, 14x aufgerufen)
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014
  Mit Zitat antworten Zitat
Satty67

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

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

  Alt 16. Mär 2009, 18:21
Freut mich, das es als Basis gedient hat. Die Routinen würde ich wegen der Vergleichbarkeit gerne mal über meine Testdatei jagen, aber unter D5 meckert er:

"[Fataler Fehler] UFileQuickSort2.pas(58 ): Interner Fehler: C3517
Diese Fehlermeldung sollten Sie niemals erhalten - sie bedeutet, daß ein Programmierungsfehler im Compiler vorliegt."

himitsu vs. D5 Compiler = 1:0

Der Compiler steht beim end; von "Function GetLine". Muss mal schauen was ich dezent verändere, damit man das auch mit D5 compiliert bekommt.

Ok, durch ausklammern, konnte ich die verantwortliche Code-Zeile ermitteln:
Delphi-Quellcode:
If (SetFilePointer(SourceFile, i64.LowPart, @i64.HighPart, FILE_BEGIN) <> i64.LowPart)
  or (i64.HighPart <> LARGE_INTEGER(FileIndex[Idx].Offset).HighPart) Then Exit;

// genauer der Teil:
SetFilePointer(SourceFile, i64.LowPart, @i64.HighPart, FILE_BEGIN) <> i64.LowPart
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
38.256 Beiträge
 
Delphi 10.4 Sydney
 
#38

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

  Alt 16. Mär 2009, 18:51
joar, ist wohl 'nen knuffier Fehler im Delphi/C++-Compiler,
welchen es im D7 nicht mehr gibt (hatte extra D7 genommen, um sowas möglichst zu vermeiden )


versuch es mal so:
Delphi-Quellcode:
Function GetLine(Idx: Integer; Var Line: AnsiString): Boolean;
  Var W: Cardinal;
    i64: LARGE_INTEGER;

  Begin
    Result := False;
    i64.QuadPart := FileIndex[Idx].Offset;
    i64.LowPart := SetFilePointer(SourceFile, i64.LowPart, @i64.HighPart, FILE_BEGIN);
    If i64.QuadPart <> FileIndex[Idx].Offset Then Exit;
    SetLength(Line, FileIndex[Idx].Size);
    If (FileIndex[Idx].Size > 0) and (not ReadFile(SourceFile, Line[1], FileIndex[Idx].Size, W, nil)
        or (Integer(W) <> FileIndex[Idx].Size)) Then Exit;
    Result := True;
  End;
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014
  Mit Zitat antworten Zitat
Satty67

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

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

  Alt 16. Mär 2009, 19:04
Hab' paralell selber gesucht und scheint das casten auf LARGE_INTEGER des Wertes aus einem Record zu sein.

Folgendes hat gereicht:
Delphi-Quellcode:
offset := FileIndex[Idx].Offset; // offset lokal als Int64 declariert
If (SetFilePointer(SourceFile, i64.LowPart, @i64.HighPart, FILE_BEGIN) <> i64.LowPart)
    or (i64.HighPart <> LARGE_INTEGER(Offset).HighPart) Then Exit;
Ok und gleich die Werte mit meinem 8,5 MB Wörterbuch (das hat 600.000 Zeilen und ist anders sortiert, als gewünscht):

PrefetchSize=0 : 33313 ms
PrefetchSize=4 : 16187 ms
PrefetchSize=8 : 10860 ms
PrefetchSize=16 : 9281 ms
PrefetchSize=1024 : 9287 ms

Hätte das OpenSource Wörterbuch gerne als gleiche Test-Basis reingestellt, aber ohne OK eines Moderators mache ich das nicht. (Ich kann keine Quellangabe machen)

Wäre interessant, was ein neuerer Compiler aus den Code macht.
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
38.256 Beiträge
 
Delphi 10.4 Sydney
 
#40

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

  Alt 16. Mär 2009, 19:37
Zitat:
PrefetchSize=1024 : 9287 ms <> PrefetchSize = 1024 : 3.765 ms
da sollte man wohl das "oftmals" so verdamte delphiinterne Caching bei diesen alten Funktionen nicht all zu sehr verdammen

eine Lesecache hab ich ja (in)direkt eingebaut ... mal sehn was passiert, wenn auch eine Schreibcache enthalten ist.


stimmt denn wenigstens die Sortierung?

ach ja, nicht wegen der eingebauten Funktion AnsiCompareText wundern ... wollte es morgen mal in D2009 testen und da ist AnsiCompareText nicht Ansi, sondern Unicode.


bezüglich deines Originalcodes:
bei [i]Offset := Offset + FileIndex.size + 2; mußt du aufpassen, denn es muß nicht immer #13#10 als Zeilentrennung vorhanden sein
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014
  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 10:55 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