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 2 von 7     12 34     Letzte » 
alzaimar
(Moderator)

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

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

  Alt 12. Mär 2009, 19:19
Ich habe das mal folgendermaßen gemacht:
1.Textdatei in ein temporäre Datei kopieren. Dabei alle Zeilen auf gleiche Länge bringen (mit #0 auffüllen). Hauptsache ich kann per Seek auf eine Zeile direkt zugreifen.
2.Quicksort auf die Textdatei loslassen. Bei Blöcken < 20000 habe ich die Zeilen eingelesen, in-Memory-Quicksort drübergebraten und den sortieren Block wieder abgespeichert.
3. Abschließend die temporäre Datei wieder in eine Textdatei zurückschreiben.

Dauer bei einer 75MB großen Datei (vor 8 Jahren, auf einer oberlahmen Krücke) nur ca. 2 Minuten. Sollte heutzutage also schnell genug sein.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
ThomasNds

Registriert seit: 16. Sep 2008
4 Beiträge
 
Delphi 5 Standard
 
#12

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

  Alt 12. Mär 2009, 19:41
Hallo,

die Google-Stichworte, die du suchst, lauten "externes sortieren"
und "Mischsortieren direktes Mischen". Eine sehr schöne Beschreibung des
Sortierens von DAteien, die nicht in den Hauptspeicher passen,
findet sich in Wirth: Algorithmen und Datenstrukturen. Die englische
Version des Buches gibt es hier (ab Seite 67):
http://www-old.oberon.ethz.ch/WirthPubl/AD.pdf
Einen groben Überblick (ohne Code) liefert z.B.
http://www.inf.fu-berlin.de/lehre/SS...ipt/ALP2K2.pdf

Eine Alternative wäre das Einlesen der Strings in einen B-Baum
oder eine Datenbank, um sie dann sortiert herauszulesen.

Andere Alternative, wenn der Hauptspeicher nur geringfügig
zu klein ist: Ein Array mit Verweisen in die Datei anlegen, etwa
Code:
  Index: Array of Record
                   Stringstart: Fileoffset
                    Stringlänge: Integer
                  end
Ein Arrayelement benötigt 8 Byte, also kann man in z.B. 20 MB
gut 2 Millionen Feldelemente anlegen. Das Array wird gefüllt,
indem man einmal durch die ganze Datei durchliest. Dann sortiert
man das Array (hepasort o.ä). Anschließend kann man die
Strings sortiert aus der Datei auslesen und in eine neue
schreiben.

Gruß

T.
  Mit Zitat antworten Zitat
ub60

Registriert seit: 14. Nov 2004
17 Beiträge
 
#13

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

  Alt 12. Mär 2009, 20:56
Um halbwegs abschätzen zu können, was Du brauchst, konkretisiere doch mal Deine Anforderung:
  • Wie viele Zeilen maximal (Größenordnung)?
  • Welche Zeileninhalte (gut verteilt, Häufungen, ...)?
  • Maximale Zeilenlänge?
ub60
  Mit Zitat antworten Zitat
Benutzerbild von SirThornberry
SirThornberry
(Moderator)

Registriert seit: 23. Sep 2003
Ort: Bockwen
12.235 Beiträge
 
Delphi 2006 Professional
 
#14

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

  Alt 12. Mär 2009, 21:58
Ich muss mal etwas OT werden
Zitat von k6n:
...Es gibt einige Tools, die das können, z.B die sort.exe, die auf jeden Unix basierten System gibt.
Was passt da nicht? Richtig - das bei einer Unixdistribution ein ausführbare Datei beiliegt die als .exe benannt ist. Das ist höchstens der Fall wenn ein Windowsnutzer unter Linux wütet oder wenn jemand Wine installiert hat...
Jens
Mit Source ist es wie mit Kunst - Hauptsache der Künstler versteht's
  Mit Zitat antworten Zitat
k6n

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

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

  Alt 12. Mär 2009, 22:45
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.

Mein kläglicher Versuch:
Delphi-Quellcode:
const
  BUFSIZE = 20; //kleiner Wert zum Testen
var
  sBuf : Ansistring;
  iRead: Integer;
begin
  with TFileStream.Create('c:\test.txt', fmOpenRead) do
    try
      SetLength(sBuf, BUFSIZE);
      iRead := Read(sBuf[1], BUFSIZE);
      while iRead = BUFSIZE do
      begin
        ShowMessage(sBuf); //Testausgabe
        iRead := Read(sBuf[1], BUFSIZE);
      end;
      if iRead > 0 then //Rest
      begin
        SetLength(sBuf, iRead);
        ShowMessage(sBuf); //Testausgabe
      end;
    finally
      Free;
    end;
end;
Bitte um Berichtigung

Zitat von ub60:
Um halbwegs abschätzen zu können, was Du brauchst, konkretisiere doch mal Deine Anforderung:
  • Wie viele Zeilen maximal (Größenordnung)?
  • Welche Zeileninhalte (gut verteilt, Häufungen, ...)?
  • Maximale Zeilenlänge?
ub60
Also die Dateien können schon sehr groß sein (bis zu 300MB) und die Zeilenlängen variieren sehr stark.

@SirThornberry: Die sort.exe kam von cygwin...
  Mit Zitat antworten Zitat
Satty67

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

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

  Alt 13. Mär 2009, 00:06
Die Blöcke müsste natürlich größer sein, aber Du hast recht... da die Records (Zeilen) eine variable Größe haben, wird das ziemlich aufwändig. Zwar kann man innerhalb eines Blockes problemlos sortieren, weil die Gesamt-Blockgröße gleich bleibt, aber sobald zwischen Blöcken ausgetauscht werden muss wird es kompliziert.

Die Idee mit dem angelegten Index (ein paar Post vorher) finde ich da dann doch die bessere Variante. Wobei man die Dateizugriffe minimieren kann, indem man dem Index einen Teil der Zeile spendiert:
Delphi-Quellcode:
TIndexEntry = record
  offset,
  size : Integer; // size könnte man auch lassen, wenn man immer auf Zeilenseperator prüft
  part : array[0..2] of Char // Bsp. die ersten 3 Zeichen als Muster
end;
1) Man liest den Haupt-Index ein, muss also einmal die ganze Datei durcharbeiten.
2) Sortiert den Haupt-Index Anhand des Teilstring "part"
3) Arbeitet den fertig sortierten Haupt-Index chronologisch ab
- Index(n) <> Index(n+1) dann Zeile gleich in Zieldatei schreiben
- Index(n) = Index(n+1) dann ganze Quell-Zeile in einer neuen Teil-Liste zum nachsortieren puffern, solange bis wieder Index(n) <> Index(n+1). Dann sortiert man diese Teilliste und speichert sie in der Zieldatei.

Den Teilstring "part" müsste man dann anpassen, das es ausgewogen ist zw. Größe Haupt-Index und zu erwartende Teilisten. Je ähnlicher alle Zeilen, desto schlechter wird die Methode. Vorteil wäre halt, das die Datei nur zweimal komplett gelesen wird. Sortieren direkt in der Datei würde etwa die 20fache Menge bedeuten.

Evtl. könnte man sogar für beide Indexlisten TStringList verwenden, wenn man den Offset im Objekt speichert und auf size verzichtet.
  Mit Zitat antworten Zitat
Reinhard Kern

Registriert seit: 22. Okt 2006
772 Beiträge
 
#17

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

  Alt 13. Mär 2009, 00:39
Zitat von SirThornberry:
Ich muss mal etwas OT werden :duck:
Zitat von k6n:
...Es gibt einige Tools, die das können, z.B die sort.exe, die auf jeden Unix basierten System gibt.
Was passt da nicht? Richtig - das bei einer Unixdistribution ein ausführbare Datei beiliegt die als .exe benannt ist. Das ist höchstens der Fall wenn ein Windowsnutzer unter Linux wütet oder wenn jemand Wine installiert hat...
Hallo,

du willst uns also damit sagen, dass es hier verboten ist, auch nur auf die Existenz einer Lösung hinzuweisen, wenn sie nicht Bestandteil von Delphi ist? Ich habe ja sowieso nicht mehr viel Hoffnung für die Zukunft der Sprache Pascal/Delphi, aber wenn schon hier im Forum Sektierer mit Tunnelblick und geiferndem Hass auf alles anderssprachliche dominieren, brauche ich mir keine Sorgen mehr machen, dann ist es längst vorbei. So ein Ende unter Fanatikern hat die schöne Sprache Pascal nicht verdient.

Gruss Reinhard
  Mit Zitat antworten Zitat
Satty67

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

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

  Alt 13. Mär 2009, 00:53
Also ich glaube er wollte nur sagen, dass sort.exe so garnicht nach unix klingt.

"Geifernder Hass" lese ich in dem Thread nur in einem Post
  Mit Zitat antworten Zitat
k6n

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

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

  Alt 13. Mär 2009, 01:29
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.
  Mit Zitat antworten Zitat
Benutzerbild von stoxx
stoxx

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

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

  Alt 13. Mär 2009, 02:54
guck Dir nochmal die Antwort von alzaimar an .. die hast Du glaub ich etwas überlesen ..

Ein IndexFile kannst Du auch aufbauen .. sinnvoller wäre aber sowas ...

eine Liste mit folgenden Records ..

TRow = record
FileStartPos, RowLenght : Integer;
end;

Du machst von jeder Zeile ein Element dieses Records (incl des Zeilenumbruches)
Dann nimmst Du einen universellen Sortieralgorithmus, welcher die Verwendung einer SortComparefunktion erlaubt.
Das einzige, was Du nun implementieren musst ist eine Vergleichsfunktion zweier Elemente, die Du vergleichen willst, in Deinem Fall "Zeilen"

Der Sortieralgorithmus vergleicht immer 2 beliebige Elemente, er ruft dazu Deine eigene definierte Vergleichsfunktion auf.
(Den Pointer übergibst Du vorher dem Sortieralgorithmus)
Da Du das File nicht im Speicher hast, musst Du beim Vergleichen zweier Elemente einfach immer die 2 Zeilen vom File einlesen. Das kannst Du deswegen machen, weil Du ja die StartPos und die Länge der entsprechenden Zeile hast .. die 2 eingelesenen Zeilen vergleichst Du, und gibst als Result dem Sortieralgorithmus zurück, welche der beiden Elemente (Zeilen) kleiner ist.
Danach hast Du eine sortierte Index liste, und kannst ein neues File durch umkopieren sortiert erstellen.

so ist das ....
Phantasie ist etwas, was sich manche Leute gar nicht vorstellen können.
  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:39 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