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 1 von 7  1 23     Letzte » 
k6n

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

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

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

Ich suche eine Möglichkeit in Delphi eine relativ große (Text-)Datei möglichst schnell alphanumerisch zu sortieren, ohne diese komplett in den Speicher zu laden. Es gibt einige Tools, die das können, z.B die sort.exe, die auf jeden Unix basierten System gibt. Diese Datei ist zwar nicht die schnellste, aber sie schafft es beliebig große Dateien zu sortieren, ohne dabei (zu)viel Speicher zu verbrauchen.

Eine Möglichkeit wäre, die Datei blockweise zu lesen, aber wie kann man diese dann noch komplett sortieren, wenn man keinen Zugriff auf jede Zeile hat?

Kann mir jemand einen Tipp geben, wie man sowas machen könnte?

Gruß
  Mit Zitat antworten Zitat
Satty67

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

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

  Alt 12. Mär 2009, 16:32
Die meisten Sortierverfahren vergleichen benachbarte Blöcke. Das sollte also per Buffer lösbar sein.
  Mit Zitat antworten Zitat
k6n

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

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

  Alt 12. Mär 2009, 16:39
Zitat von Satty67:
Die meisten Sortierverfahren vergleichen benachbarte Blöcke. Das sollte also per Buffer lösbar sein.
Verstehe aber trotzdem nicht ganz, wie man damit eine große Datei sortieren kann.

Kann mir vielleicht jemand ein ganz kleines Beispiel oder so dazu schreiben, damit mir das Prinzip klar wird?

Danke!
  Mit Zitat antworten Zitat
nahpets
(Gast)

n/a Beiträge
 
#4

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

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

schau mal bitte dort: http://www.stefan-baur.de/cs.algo.sort.html. Auf der Seite werden diverse Sortieralgorithmen beschrieben, zum Teil auch mit Quelltexten zu unterschiedlichen Programmiersprachen. Es geht dort quasi um Theorie und Praxis. Eventuell hilft Dir das ja weiter.
  Mit Zitat antworten Zitat
k6n

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

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

  Alt 12. Mär 2009, 17:00
Zitat von nahpets:
Hallo,

schau mal bitte dort: http://www.stefan-baur.de/cs.algo.sort.html. Auf der Seite werden diverse Sortieralgorithmen beschrieben, zum Teil auch mit Quelltexten zu unterschiedlichen Programmiersprachen. Es geht dort quasi um Theorie und Praxis. Eventuell hilft Dir das ja weiter.
Die gängigen Sortierverfahren sind mir bekannt, aber die benötigen immer ein komplettes Array mit den Werten und um das zu bekommen, muss man die Datei komplett in den Speicher laden und genau das möchte ich ja nicht.
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

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

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

  Alt 12. Mär 2009, 17:02
wenn es nicht unbedingt schnell sein muß, dann z.B. per TPartialTextfile

oder wenn die datei z.B. aufsteigend sortiert werden soll:
man könnte auch die Datei durchgehn
sich einen Index aller Zeilen anlegen (also wie diese beginnen)

loop:
dann die Datei nochmals duchgehn
sich ein array mit den "kleinsten" Zeilen anlegen (also mit deren Index + Inhalt)
dann zeile für zeile weitergehn (anhand dr Indexe) und jeweils in dem array "größere" durch "kleinere" Zeilen ersetzen
hat am Ende der Datei eine Hand voll der "kleinsten" Zeilen
schreibt diese Zeilen in eine neue Datei
und löscht deren Indexe aus der Liste

und noch geht man wieder zu loop und macht mit den restlichen Zeilen weiter


[add]
oder halt ala RadixSort einen Index (mit den Zeilenanfängen) anlegen, dann diesen sortieren und am ende eine neue Datei anhand der sortierten Indexliste erstellen.
Garbage Collector ... Delphianer erzeugen keinen Müll, also brauchen sie auch keinen Müllsucher.
Delphi-Tage 2005-2014
  Mit Zitat antworten Zitat
Dax
(Gast)

n/a Beiträge
 
#7

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

  Alt 12. Mär 2009, 17:04
Du kannst die Datei zerteilen, die Teile sortieren und dann wieder mergen
  Mit Zitat antworten Zitat
nahpets
(Gast)

n/a Beiträge
 
#8

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

  Alt 12. Mär 2009, 17:27
Hallo,
Zitat von k6n:
Die gängigen Sortierverfahren sind mir bekannt, aber die benötigen immer ein komplettes Array mit den Werten und um das zu bekommen, muss man die Datei komplett in den Speicher laden und genau das möchte ich ja nicht.
na schön, der MergeSort, der dort beschrieben ist, dürfte (ggfls. nach Aufarbeitung) ja genau Dein Problem lösen. Der MergeSort im Beispielquelltext arbeitet halt mit zwei Teilen, das sieht aber so aus, als könne man mit etwas Aufwand da auch 4 oder 8 oder mehr Teile draus machen. Für das Sortieren der einzelnen Teile musst Du dann immer nur eines der Teile im Speicher haben und sortieren. Das schreibst Du dann temporär weg. Beim Zusammenfügen nimmst Du zuerst Teil 1 und 2, dann Teil 1 und 3 ...
Na, zum Mergen könnte man dann auch die einzelnen Teile parallel von der Platte lesen und in eine neue Datei schreiben, man liest die einzelnen Teile solange, bis der aktuelle Satz einer anderen Datei kleiner als der eigene ist. Das kann man über (fast) beliebig viele Dateien machen. Der Programmieraufwand dürfte nicht mal übermäßig groß sein.

Wie groß sind die zu sortierenden Dateien den überhaupt?
  Mit Zitat antworten Zitat
Benutzerbild von p80286
p80286

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

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

  Alt 12. Mär 2009, 17:30
hallo K6n,

da gibt es was für Dich, ich glaube es heißt mergesort. Ggf. müßtest Du unter externe Sortierverfahren suchen.
Das Prinzip stammt noch aus der Großrechnerzeit.

Im Prinzip funktioniert das in zwei Schritten:
A) lese Eingabedatei
solange Datensatze sortiert vorliegen in Ausgabedatei schreiben.
wenn nicht mehr sortiert dann neue Ausgabedatei anlegen.
B) lies den ersten Datensatz aus allen Ausgabedateien
vergleiche alle Sätze und schreibe den kleinsten in die Pufferdatei
bis alle Ausgabedateien gelesen sind
verarbeite die Pufferdatei mit A)
wenn nur noch eine Ausgabedatei vorliegt ist alles sortiert.

Wenn Dein Verfahren stabil sein soll dann mußt Du beim Wegschreiben der "kleinsten Sätze" den mit dem kleineren Index bevorzugen.
Du kannst das Verfahren beschleunigen indem Du möglichst große Happen vorsortierst. Dann solltest Du allerdings auch hier ein stabiles Verfahren nutzen, also Finger weg von QuickSort.

In der ursprünglichen Version wird nur mit 2 Ausgabedateien gearbeitet. Dann wird immer hin und her geschaltet wenn die Sortierung unterbrochen wird. Das fördert allerdings die Schreib/Lesetätigkeit auf der Platte.

Ich hoffe das hilft Dir weiter

K-H

(ich bin zu langsam!)
  Mit Zitat antworten Zitat
k6n

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

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

  Alt 12. Mär 2009, 17:53
Vielen Dank erstmal an alle! Ich probiere mal ein bisschen rum, auch wenn ich befürchte, dass es nichts wird.
  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 12:03 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