Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
Autor |
Nachricht |
lpd2
Anmeldungsdatum: 26.03.2007 Beiträge: 5
|
Verfasst am: 27.03.2007, 15:07 Titel: Sortieren innerhalb einer Datei |
|
|
Hallo wie würdet ihr eine Routine schreiben die über 500000 Datensätze sortieren soll. Eine Sortierroutine auf Arraybasis bekomme ich ja noch hin. Aber wenn´s soviele Datensätze sind kommen die Array an ihre Grenze. Das Programm muss also irgendwie auf Festplattenebene sortieren. Wie gehe ich das an? sollte ich array zum zwischenpuffern nutzen? oder einfach von der orginaldatei in eine Tempdatei schreiben und wieder zurück? Welchen Ansatz würdet ihr verfolgen. Oder kennt ihr ein Programm das sowas leistet (Quellcode)? |
|
Nach oben |
|
 |
ThePuppetMaster

Anmeldungsdatum: 18.02.2007 Beiträge: 1839 Wohnort: [JN58JR]
|
Verfasst am: 27.03.2007, 15:37 Titel: |
|
|
Ich würde dir empfehlen das Ganez über eine Temp-Datei zu regeln, wenns schnell gehen soll.
Zusätzlich (UNBEDINGT ERFORDERLICH!!!) mit GROSSEN Datensatz Puffern arbeiten! ... Wenn du schnelle Schreib / Lese operationen auf der Platte durch führst, rennt der Kopf von A nach B udn wieder zurück, und das ziemlich offt. Auf dauer macht das Deien Platte kaput (macht es so oder so, aber so beschleunigst du das ganze)
Auserdem hast du den Vorteil, das du schneller Daten lesen udn Schreiben kannst, wenn er nicht immer die neue Position von B bzw. A suchen muss.
Ich würde vorschlagen so ca. 10 bis 50 MB zwischen zu puffern. .. oder noch mehr .. je nachdem, wie gross das Ram ist.
MfG
TPM _________________ [ WebFBC ][ OPS ][ ToOFlo ][ Wiemann.TV ] |
|
Nach oben |
|
 |
Mao
Anmeldungsdatum: 25.09.2005 Beiträge: 4409 Wohnort: /dev/hda1
|
Verfasst am: 27.03.2007, 17:31 Titel: |
|
|
50MB halte ich eindeutig für zuviel.
Kommt dann aber auch wieder auf die Dateigröße an. Geschwindigkeitsgewinn bringt ein zu großer Puffer aber auch nicht.
Der goldene Mittelweg hängt immer von der Datei ab. _________________ Eine handvoll Glück reicht nie für zwei.
--
 |
|
Nach oben |
|
 |
ThePuppetMaster

Anmeldungsdatum: 18.02.2007 Beiträge: 1839 Wohnort: [JN58JR]
|
Verfasst am: 27.03.2007, 17:33 Titel: |
|
|
Es geht janicht prinzipel um die Geschwindigkeit, sondern eher um die schadensbegrenzung der Festplatte ... deren Lebensdauer dadurch enorm abnehmen würde, wenn man ständig daten von A nach B schreibt, ohne zu puffern .. je grösser der Puffer im Speicher ist, desto mehr kann man direkter auf der Platte lesen / schreiben, ohne den Kopf zu gross belasten.
MfG
TPM _________________ [ WebFBC ][ OPS ][ ToOFlo ][ Wiemann.TV ] |
|
Nach oben |
|
 |
Mao
Anmeldungsdatum: 25.09.2005 Beiträge: 4409 Wohnort: /dev/hda1
|
Verfasst am: 27.03.2007, 17:41 Titel: |
|
|
Gut, da ist dann die Frage, wie oft das gemacht werden muss.
Soll die Sortierung täglich erfolgen oder wöchentlich, wird das vllt. 'ne höhere Belastung.
Aber ist das vllt. einmal im Jahr, dann würd ich maximal einen Puffer von 10MB nehmen. _________________ Eine handvoll Glück reicht nie für zwei.
--
 |
|
Nach oben |
|
 |
volta
Anmeldungsdatum: 04.05.2005 Beiträge: 1876 Wohnort: D59192
|
Verfasst am: 27.03.2007, 18:24 Titel: |
|
|
Hi,
einfach mal ausprobieren.
Vor ca. 2 Jahren habe ich mal mit so großen Arrays gespielt, bis 160MB (bei 256MB RAM) war es wirklich sehr schnell (keine Auslagerung auf die HD).
http://forum.qbasic.at/viewtopic.php?p=9165#9165
Verschiedene Sortieralgorithmen habe ich hier mal ausprobiert:
http://freebasic.de/fbnp/?view=357
Übrigens hat FB eine 'interne Sortierroutine' FB_qsort. _________________ Warnung an Choleriker:
Dieser Beitrag kann Spuren von Ironie & Sarkasmus enthalten.
Zu Risiken & Nebenwirkungen fragen Sie Ihren Therapeuten oder Psychiater. |
|
Nach oben |
|
 |
Anistasius
Anmeldungsdatum: 18.01.2006 Beiträge: 37
|
Verfasst am: 28.03.2007, 13:44 Titel: |
|
|
Mach es mit BTrees.
Eleganter und schneller geht´s kaum.
Egal ob du 10 oder 10.000.000 Datensätze hast, im Prinzip dauert jeder Zugriff gleich schnell und benötigt nur ein Minimum an RAM und Zugriffen
Einen Quelltext für FB kann ich dir zwar geben, aber da ist eine spezialisierte Datenbank drumrum (s.u.) . Sinnvoller ist eine eigene Lösung, die man sich selbst erarbeitet hat und nachvollziehen kann.
Im Prinzip funktioniert es so:
Du legst eine Binär- oder Randomdatei an. Jeder Satz kann 20 Keys (nur mal so als Zahl)plus Adresse für den nächsten Satz aufnehmen. Innerhalb dieses Satzes sind die Keys sortiert und die dazugehörigen Adressen verweisen auf einen Satz in der nächsten Stufe, wo dieser Key der höchste ist. In der letzten Stufe wird dann auf eine Adresse in der eigentlichen Datendatei verwiesen.
Bei 2 solcher Stufen, kannst mit zwei Zugriffen einen von 100 Datensätzen finden, bei fünf Stufen/Zugriffen sind es schon 100.000 und so weiter.
Wenn Du einen neuen Satz einsortierst. Sagen wir "Peter" dann gehst du zur ersten Stufe, wo die Keys "Anton","Egon","Rudolf" drin stehen.
Peter ist größer als Egon, aber kleiner als Rudolf, also wird als nächste Stufe die Satzadresse von Rudolf gelesen. Dort wiederholt sich das Spiel, bis "Peter" die letzte Stufe erreicht hat. Dort wird er dann mit seiner Adresse vom Datensatz einsortiert. Falls dabei die Zahl der möglichen 20 Keys im Satz überschritten wird, wird mit den ersten 10 Keys ein neuer Sortiersatz angelegt und der größte Key eine Stufe höher einsortiert. Ein Problem tritt noch beim löschen auf. Im Prinzip wird die Indexdatei immer größer. Hier hilft eine Lückenverwaltung.
Im Kopfsatz der Indexdatei steht die Adresse vom nächsten freien Satz bzw, das Ende der Datei. Wenn nun ein weiterer Satz frei wird, trägst Du diese Zahl dort ein und die Adresse von dem freien Satz in den Kopf. So werden, bevor er sich neuen Platz reserviert erst alte freigegebene Sätze wieder beschrieben.
Ich habe Dir mal den Quelltext unter http://anistasius.de/btdb.bas
hinterlegt. Das wirst Du so zwar nicht kompiliert bekommen, weil es ein Teil von einem großen Programmpaket ist, was ich von Xbasic nach FreeBasic (bei mir noch Version FB 0.15+Teile von 0.16) konvertiere und noch sehr provesorisch ist. Z.B. mußte ich vorläufig, damit´s erstmal funktioniert einige Gotos u. Gosubs nehmen, da FB keine Unterfunktionen in Funktionen kennt.
Für Dich nützlich sind die Funktionen: "btDBindexCreate" und "btDBindexVerw" da steckt im Grunde alles drin was Du für eine eigene Lösung brauchst.
Viele Grüße
Anistasius |
|
Nach oben |
|
 |
croco97

Anmeldungsdatum: 04.11.2005 Beiträge: 260
|
Verfasst am: 29.03.2007, 10:09 Titel: |
|
|
@Anistasius:
Welcher Sortier-Algo, ob Bubble, Quick, BTree, RBTree, ist für den OP vermutlich im Moment sekundär. Aber du hast sozusagen nebenbei auf das Entscheidende hingewiesen: Es dürfen nicht die Inhalte Datensätze sortiert werden, sondern nur die File-Positionszeiger plus Sortierkriterium. Dann ist der Speicheraufwand für einen Puffer (Sortierkriterium = 8 Bytes angesetzt) erade mal bei 500k x 12 = 6 MB. Und das Ganze mal zwei, also 12 MB.
Insofern braucht man m.E. auch keine temp-Dateien oder sowas. Also, zum Mitschreiben:
1.) Die Zeiger aller Datensätze ermitteln und
a. Zeiger
b. Sortierkriterium in ein Array laden.
2.) Array sortieren - mit was auch immer.
3.) Bei Bedarf File nach der Reihenfolge des nun sortierten Arrays umspeichern.
Und wie immer der Hinweis auf das Oma-Tutorial, Teil 2, da steht was zum Umgang mit Filezeigern in QBasic resp. Freebasic.
Tschüss!
Croco |
|
Nach oben |
|
 |
Anistasius
Anmeldungsdatum: 18.01.2006 Beiträge: 37
|
Verfasst am: 29.03.2007, 12:00 Titel: |
|
|
@Croco
Das hatte ich irgendwie vorausgesetzt....
Aber bei Arraysortierungen wäre ich vorsichtig. Das lohnt sich nur bei kleinen Datenmengen. Je nach Rechner fängt es so ab 1000 Sätze an unwirtschaftlich zu werden.
Mal ein Extrembeispiel:
Will ich z.B. eine Einwohnerverwaltung für die Republik schreiben und nach Nachname suchen, lege ich bei meinem System 20 Keys x 8 Stufen an. Das entspricht im ungünstigsten Fall 100.000.000 Namen.
Angenommen ich reserviere 20 Byte pro Name, dann würde ich bei einem Array etwa 2 GB Speicher brauchen, um chronologisch zu suchen. Falls ich ein Sortierverfahren verwende, ein Mehrfaches davon um die Daten umzuschaufeln. Und außerdem muß diese gigantische Datenmenge noch gelesen werden, was wahrscheinlich recht lange dauert.
Tatsächlich habe ich aber nur 8 Zugriffe auf die Platte. Insgesamt werden nur 160 Keys in Arrays durchsucht/verglichen und 400 Byte im Speicher plus diversen Sortierungen, vielleicht unterm Strich 5-10 KB!! gehalten.
D.h. subjektiv geht das Anzeigen der Namen für den Anwender vor der Kiste fast so schnell wie wenn die Daten als Textdatei eingelesen würden.
Ich habe z.B. in meiner Anwendung eine PLZ Hilfe für D,CH und AU. Wenn der Anwender bei Adressenanlage eine PLZ Nummer eintippt, wird ihm der Ort und die Vorwahl gleich mit ausgefüllt. Ist schon länger her, aber ich meine es waren etwa um die 70.000 Datensätze. Das anlegen hatte ca. 20-30 Minuten gedauert und gefunden werden die Daten in Sekundenbruchteilen. Speicherverbrauch und Plattenbelastung sind jedenfalls unwesentlich.
Viele Grüße
Anistasius |
|
Nach oben |
|
 |
PMedia
Anmeldungsdatum: 14.08.2006 Beiträge: 2847
|
Verfasst am: 29.03.2007, 12:58 Titel: |
|
|
MySQL machts doch glaub ich genauso, oder?
Glaub da hab ich mal sowas gelesen... |
|
Nach oben |
|
 |
lpd2
Anmeldungsdatum: 26.03.2007 Beiträge: 5
|
Verfasst am: 30.03.2007, 08:34 Titel: |
|
|
naja habe jetzt erstmal ne Quick und dirty lösung gecodet die funzt. 1 Mio Datensätze dauern da so 5 Minuten. Werde das ganze mit etwas mehr Mühe noch um einiges schneller machen. Habe Arrays gar nicht genutzt das ganze wurde direKt in eine tmp datei geschrieben. |
|
Nach oben |
|
 |
Anistasius
Anmeldungsdatum: 18.01.2006 Beiträge: 37
|
Verfasst am: 30.03.2007, 16:15 Titel: |
|
|
@PMedia
Die meisten Datenbanken arbeiten mit Baumstruktur. Es gibt da auch ziemlich viele Möglichkeiten.
Eine ganz einfache Variante habe ich mal als kleines Beispiel zusammengestellt (läuft unter Windows mit FB 0.16)
http://anistasius.de/minidb.bas
Auf das löschen der Datensätze habe ich allerdings verzichtet, weil man dann auch ein reorg bzw. eine
Lückenverwaltung in die Datendatei einbauen muß.
...falls es aber jemand brauchen sollte...
Viele Grüße
Anistasius |
|
Nach oben |
|
 |
|