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 3 von 7     123 45     Letzte » 
Benutzerbild von stoxx
stoxx

Registriert seit: 13. Aug 2003
1.111 Beiträge
 
#21

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

  Alt 13. Mär 2009, 03:24
Zitat:
So, hab jetzt mal ein bisschen rumprobiert, komme damit aber überhaupt nicht klar.
Es scheitert schon beim blockweisen auslesen. Wenn man einen Block ließt, ist es ja nicht immer sicher, das komplette Zeilen im Block liegen, sondern auch mal abgehackte Zeilen.
´


Da Deine Probleme auch noch im technischen und nicht nur algorithmischen Bereich liegen, schau Dir mal diese Funktion hier an.

diese kannst Du nach Deinen belieben Verändern und nutzen, Dein Index File mit der StartPos und Länge aufzubauen.
Danach solltest Du auch damit gezielt von LineStart bis LineEnd lesen können.

Aber bitte diese Funktion "GrabLine" nicht SO NUTZEN wie sie ist, um eine bestimmte Zeile zu lesen, die Funktin geht nämlich JEDESMALL immer von vorn durch und zählt die Zeilen .... das würde natürich ewig dauern ...


http://www.swissdelphicenter.ch/de/showcode.php?id=1628



...
Phantasie ist etwas, was sich manche Leute gar nicht vorstellen können.
  Mit Zitat antworten Zitat
Satty67

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

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

  Alt 13. Mär 2009, 09:18
Zitat von k6n:
Hallo Satty, Deine Methode habe ich soweit verstanden, aber verbraucht diese Methode nicht auch ziemlich viel Speicher, wenn die Datei z.B so um die 300-500MB groß ist? Dan landet man auch ganz schnell jenseits der 100MB, oder? Ich glaub ich gebs auf.
Ja, wenn die Zeilen nur so lang wie der "part" sind, liest Du sogar die ganze Datei in den Speicher.

Entweder eine Methode, die auf der Festplatte sortiert, dann reicht ein einfacher Index (notfalls auch auf der Festplatte angelegt). Aber dann musst Du jeden String zum Vergleichen neu auslesen. So wie ich das sehe, ist beim besten Sortierverfahren immer noch Faktor 16 beim Element Zugriff nötig, also bis in den mehrstelligen GByte Bereich von der Festplatte lesen.

Wenn Festplattenzugriff nahezu egal sind, ist die Umsetzung ein Kinderspiel... Verglichen wird statt Array[n] eben StringFromFile[n]. Beim "Swap" werden dann Index-Einträge oder gleich die Strings in der Datei getauscht (wobei bei letzterem eben das Problem der unterschiedlichen Record-Länge auftaucht)
  Mit Zitat antworten Zitat
blauweiss

Registriert seit: 19. Jun 2007
142 Beiträge
 
#23

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

  Alt 13. Mär 2009, 09:46
Meine naive Frage:
Wäre es nicht deutlich geschickter, diese "sehr große" Textdatei in eine Datenbank einzulesen, dort zu sortieren und ggfs. am Ende wieder in eine Textdatei zurückzuschreiben ?

Blauweiss
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

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

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

  Alt 13. Mär 2009, 10:00
das mit der Liste wurde ja schon mehrfach gesagt und wenn man darin den Zeilenanfang mit ablegt, kann man estmal grob vorsortieren und müßte dann nur noch für einen Teil der Vergleiche (vor der Zeilenanfang übereinstimmt) die jeweilige ganze Zeilen nachladen.
Delphi-Quellcode:
Var TextList = Array of Record
      Start: Int64;
      Length: Integer;
      TextStart: String[11]; // 11+1 = 12 Byte ... insgesammt 24 Byte pro Zeile
    End;
// 1.000.000 Zeilen = 24 MB
bei sowas wäre dann nur die Zeilenanzahl ausschlaggebend und nicht die Dateigröße.

das Sortieren nur des Arrays (der Indexliste) und dann das sortierte Speichern in einer neuen Datei scheint optimaler zu sein, als alles direkt in der Datei zu sortieren, zumindestens wenn die Zeilen unterschiedlich lang sind.
siehe Hier im Forum suchenTPartialTextFile dort kann man ja Zeilen zwischendrin ändern, aber dann müssen alle Zeilen danach womöglich verschoben werden ... (fast) jedesmal, wenn was geändert wird.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014
  Mit Zitat antworten Zitat
Benutzerbild von p80286
p80286

Registriert seit: 28. Apr 2008
Ort: Stolberg (Rhl)
6.658 Beiträge
 
Delphi 7 Personal
 
#25

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

  Alt 13. Mär 2009, 12:28
Zitat von blauweiss:
Meine naive Frage:
Wäre es nicht deutlich geschickter, diese "sehr große" Textdatei in eine Datenbank einzulesen, dort zu sortieren und ggfs. am Ende wieder in eine Textdatei zurückzuschreiben ?

Blauweiss
und woher soll k6n die Datenbank nehmen? Nur um eine Textdatei zu sortieren eine Datenbank zu benutzen ist ungefähr so wie mit der LKW-Zugmaschine zum Bäcker fahren.

Gruß
k-h
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

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

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

  Alt 13. Mär 2009, 14:22
nicht schön, aber einfach
Delphi-Quellcode:
Type TTextListRec = Record
    Start: Int64;
    Length: Integer;
    TextStart: String[11]; // 11+1 = 12 Byte ... insgesammt 24 Byte pro Zeile
  End;
  TTextList = Array of TTextListRec;

Function FilePos(Var InFile: TextFile): Int64;
  Begin
    LARGE_INTEGER(Result).HighPart := 0;
    LARGE_INTEGER(Result).LowPart := SetFilePointer(TTextRec(InFile).Handle,
      0, @LARGE_INTEGER(Result).HighPart, FILE_CURRENT) - (TTextRec(InFile).BufEnd - TTextRec(InFile).BufPos);
  End;

Procedure FileSeek(Var InFile: TextFile; Pos: Int64);
  Begin
    TTextRec(InFile).BufPos := 0;
    TTextRec(InFile).BufEnd := 0;
    SetFilePointer(TTextRec(InFile).Handle,
      LARGE_INTEGER(Pos).LowPart, @LARGE_INTEGER(Pos).HighPart, FILE_BEGIN);
  End;

Function GetFullLine(Var InFile: TextFile; Const List: TTextList; Index: Integer): AnsiString;
  Begin
    If (Index < 0) or (Index >= Length(List)) Then
      Raise Exception.Create('index out of range');
    FileSeek(InFile, List[Index].Start);
    ReadLn(InFile, Result);
  End;


Var InFile, OutFile: TextFile;
  List: TTextList;
  i, i2: Integer;
  S: AnsiString;
  Temp: TTextListRec;

Begin
  AssignFile(InFile, 'Unit1.pas');
  Reset(InFile);

  AssignFile(OutFile, 'Unit1_.pas');
  Rewrite(OutFile);

  // einlesen
  i := 0;
  While not EoF(InFile) do Begin
    ReadLn(InFile, S);
    Inc(i);
  End;
  SetLength(List, i);
  FileSeek(InFile, 0);
  i := 0;
  While not EoF(InFile) do Begin
    List[i].Start := FilePos(InFile);
    ReadLn(InFile, S);
    List[i].Length := Length(S);
    List[i].TextStart := S;
    Inc(i);
  End;

  // sortieren
  For i := 0 to High(List) - 1 do
    For i2 := i + 1 to High(List) do
      If (List[i].TextStart > List[i2].TextStart) or ((List[i].TextStart = List[i2].TextStart)
          and (GetFullLine(InFile, List, i) > GetFullLine(InFile, List, i2))) Then Begin
        Temp := List[i];
        List[i] := List[i2];
        List[i2] := Temp;
      End;

  // sortiertes speichern
  For i := 0 to High(List) do
    WriteLn(OutFile, GetFullLine(InFile, List, i));

  CloseFile(OutFile);
  CloseFile(InFile);
End;
nicht über FilePos und FileSeek wundern ... die alten Delphifunktionen ala ReadLn, Seek undCo. könnten nur bis 2 GB (drum neues FilePos für altes FilePos) und Seek ist bei Textdateien eigentlich nicht möglich (drum neues FileSeek)

ja und das Sortieren könnte man auch noch optimieren, aber das wollte ich dir überlassen
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
 
#27

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

  Alt 13. Mär 2009, 14:33
Das war klar... himitsu wieder schneller, hat sogar den Index mit VorschauString umgesetzt

Ich hatte schon eine erste Version in Arbeit, die noch ohne Vorschau-String (part, TestStart etc.) arbeitet und wollte die danach optimieren. Den Code wegschmeißen will ich jetzt auch nicht, auch wenn er noch Fehler enthalten könnte:
Delphi-Quellcode:
procedure FileQuickSort(SourceFileName, TargetFileName: String);
type
  TIndex = record
    offset,
    size : Integer;
  end;
  TFileIndex = array of TIndex;
var
  FileIndex : TFileIndex;
  aSourceFileStream : TFileStream;

  // Liest eine Stringzeile aus der Quelldatei
  function GetStringLine(Index : TIndex; Upper : Boolean): string;
  var
    CharStr : PAnsiChar;
  begin
    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;

  // QuickSort mit Datei-Zeilen
  procedure QuickSort(LoIndex, HiIndex: Integer);
  var
    LoIdx, HiIdx: Integer;
    Pivot: String;
    Swap : TIndex;
  begin
    // Stelle die Ordnung bzgl. des Pivotelements her.
    LoIdx := LoIndex;
    HiIdx := HiIndex;

    // Ermitteltes Pivot-Element wäre besser, aber erst mal nur
    Pivot := GetStringLine(FileIndex[(LoIndex + HiIndex) div 2], True);

    repeat
      while GetStringLine(FileIndex[LoIdx], True) < Pivot do Inc(LoIdx);
      while Pivot < GetStringLine(FileIndex[HiIdx], True) do Dec(HiIdx);

      if LoIdx <= HiIdx then begin
        if LoIdx < HiIdx then begin

          Swap := FileIndex[LoIdx];
          FileIndex[LoIdx] := FileIndex[HiIdx];
          FileIndex[HiIdx] := Swap;

        end;

        Inc(LoIdx);
        Dec(HiIdx);
      end;

    until LoIdx > HiIdx;

    if LoIndex < HiIdx then QuickSort(LoIndex, HiIdx);
    if LoIdx < HiIndex then QuickSort(LoIdx, HiIndex);
  end;

var
  i, count, lastOffset : Integer;
  aTargetFile : TextFile;
  Chr : AnsiChar;
begin
  try
    // Quelldatei exclusiv öffnen, wir wollen ja keine verfälschten Ergebnisse
    aSourceFileStream := TFileStream.Create(SourceFileName,fmOpenRead or fmShareExclusive);
    try

      // DateiIndex aufbauen
      lastOffset := 0;
      count := aSourceFileStream.Read(Chr, 1);
      while count = 1 do begin
        case Chr of
          #13 : begin
            // Return, aktuelle Zeile ist abgeschlossen
            // Index wird erweitert, Offset und Size gespeichert
            // neuer letzter offset ans Ende setzten
            i := Length(FileIndex);
            SetLength(FileIndex,i+1);
            FileIndex[i].offset := lastOffset;
            FileIndex[i].size := aSourceFileStream.Position - (lastOffset+1);
            lastOffset := aSourceFileStream.Position;
          end;
          #10 : begin
            // LineFeed folgt, dann lastOffset +1
            inc(lastOffset);
          end;
        end;
        count := aSourceFileStream.Read(Chr, 1);
      end;
      // Letzte Zeile, die kein abschließendes #13 hatte, auch noch speichern
      i := Length(FileIndex);
      SetLength(FileIndex,i+1);
      FileIndex[i].offset := lastOffset;
      FileIndex[i].size := aSourceFileStream.Position - (lastOffset);


      // QuickSort des Index anwerfen
      if Length(FileIndex) <> 0 then QuickSort(0, Length(FileIndex)-1);

      // Zieldatei ausgeben
      AssignFile(aTargetFile, TargetFileName);
      {$I-}
      Rewrite(aTargetFile);
      {$I+}
      if IOResult = 0 then begin
        for i := 0 to Length(FileIndex)-1 do
          WriteLN(aTargetFile, GetStringLine(FileIndex[i], False));
      end;
      CloseFile(aTargetFile);

    finally
      aSourceFileStream.Free;
    end;

  // Quelldatei Fehler
  except
    on EFOpenError do ShowMessage('Quell-Datei kann nicht geöffnet werden!');
  end;
end;
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

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

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

  Alt 13. Mär 2009, 14:40
Tschuldschung, hatte wärend des Backups ein paar Minütchen Zeit gefunden

Und du hast immerhin noch 'ne Fehlerbehandlung und eine bessere Sortiervariante drin.


Ich hatte es mir dagegen mit ReadLn leicht gemacht (muß kein Zeilenende suchen, allerdings sind diese alten Funktionen nicht grad schnell/optimal ) ... da frag ich mich natürlich warum man bei TFileStrem sowas nicht mit eingebaut hat -.-°
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
 
#29

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

  Alt 13. Mär 2009, 14:44
Auf jeden Fall hab' ich wieder ettliche Synapsen in meinem Gehirn angeregt... und der Threadstarter hat jetzt viel Material zum umsetzen.

Deine Version hab' ich mir natürlich auch gleich kopiert. Mal sehen, ob ich am Wochenende da QuickSort einbaue.
  Mit Zitat antworten Zitat
Satty67

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

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

  Alt 13. Mär 2009, 20:29
Der Code von himitsu hat mich erst verwirrt...
Delphi-Quellcode:
  i := 0;
  While not EoF(InFile) do Begin
    ReadLn(InFile, S);
    Inc(i);
  End;
  SetLength(List, i);
Er zählt erst nur die Zeilen um danach nochmal die Datei komplett zu lesen...

...bis ich festgestellt hab, dass das...
Delphi-Quellcode:
i := Length(FileIndex);
SetLength(FileIndex,i+1);
innerhalb einer großen Schleife seeehr langsam ist.

SetLength sollte man also in größeren Blöcken reservieren. Um eine Datei nicht 2x lesen zu müssen, kann man auch große Blöcke reservieren und bei Bedarf immer erweitern (am Ende dann halt auf tatsächliche Größe beschneiden).
  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 05:22 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