|
|
Forum: Compiler & IDEs Sortieren von structsHallo, ich habe Daten in Form einer struct auf einer SD Karte gespeichert.
davon gibt es jetzt 5000 auf der SD Karte. Wie geht man vor wenn man diese Daten sortiert anzeigen möchte? qsort um z.B. nach Namen zu sortieren. Gibt es einen Lösungsansatz, denn man kann ja nicht alle Daten in den Speicher laden und dann sortieren, dazu reicht der Speicher nicht. Um sie ausgeben zu können: Pro Iteration baust du dir per sequentieller Suche ein Array im RAM aus den kleinsten N Einträgen auf. Dabei werden nur Einträge berücksichtigt, die grösser sind als der grösste vom vorigen Durchlauf. klaus schrieb: > Wie geht man vor wenn man diese Daten sortiert anzeigen möchte? Musst du komplett durchsortieren? > qsort um z.B. nach Namen zu sortieren. qsort hilft dir dabei nicht > Gibt es einen Lösungsansatz, denn man kann ja nicht alle Daten in den > Speicher laden und dann sortieren, dazu reicht der Speicher nicht. Dann musst du auf Methoden zurückgreifen, wie sie in den 60-er Jahren benutzt wurden um Daten zu sortieren, die auf Bändern liegen und nicht alle gemeinsam geladen werden können. zb die Daten in mehrere 'Bänder' aufteilen. Jedes Band für sich sortieren. Danach jeweils 2 Bänder zu einem gemeinsamen neuen Band zusammenmischen. Das ganze wird solange wiederholt bis nur noch 1 einziges sortiertes Band übrig bleibt. Das Mischen funktioniert so. Stell dir vor du hättest 2 bereits sortierte Stapel mit Spielkarten. Du hebts dann von jedem Stapel die erste Karte ab, die kleinere der beiden Karten legst du auf den Ausgangsstapel und hebst von demselben Stapel die nächste Karte ab. Wieder wird mit der Karte vom anderen Stapel verglichen und die kleinere auf den Ausgangsstapel gelegt. usw. usw. Nur dass bei dir das eben keine Kartenstapel sind, sondern Files auf einer SD-Karte. Das halten der Daten im Speicher wird durch Lesen von einer Datei ersetzt. (Und natürlich macht es keinen Sinn erst mal für jede Karte eine eigene Datei zu erzeugen. Daher teilt man die Komplettdaten erst mal in mehrere Haufen auf, sortiert die einzeln mit zb qsort, ehe dann das Zusammenmischen der einzelnen Haufen beginnt). PS: man kann auch mehr als 2 Haufen in einem Durchgang zusammenmischen. Das Prinzip nach dem das funktioniert sollte augenfällig sein. SD Karte aus dem Gerät nehmen. In einen PC einlegen. Alles in den PC-Speicher. Dort sortieren und zurückschreiben. Die Karte wieder in das Gerät. Ansonsten stehen Algorithmen dafür in dem Klassiker "Algorithmen und Datenstrukturen" von Niklaus Wirth (1975) klaus schrieb: > Wie geht man vor wenn man diese Daten sortiert anzeigen möchte? > qsort um z.B. nach Namen zu sortieren. Du kannst evtl. im RAM ein Feld anlegen, in dem Dateipositionen aller structs der Datei hinterlegt sind, also ähnlich wie Zeiger, nur halt auf den Dateianfang bezogen. Mit einer passenden Vergleichsfunktion, die zwei solche Dateipositionen bekommt (bzw. die Zeiger darauf) und zurückliefert, welches der Dateielemente größer ist als das andere, kann man dieses Feld von Dateipositionen sortieren (z.B. mit qsort()). Wenn du dann das sortierte Feld durchiterierst und an den so erhaltenen Positionen in die Datei schaust, hast du die sortierten Datei-structs. Hat natürlich den Nachteil, daß man viel in der Datei lesen muß. Hallo, besten Dank für die guten Tips. Ich habe mal Eure Vorschläge getestet, leider dauert es doch bis zu 60 Sekunden so eine Datei zu sortieren. 50 structs ins RAM und mit qsort geht sehr schnell. Was hast du erwartet? Zaubersprüche? Die Alternative zu anschliessendem aufwendigen Sortieren ist, gleich von Anfang an zusammen mit den sukzessive geschriebenen Daten einen Index aufzubauen. Auch da entsteht Aufwand, aber der verteilt sich. klaus schrieb: > Ich habe mal Eure Vorschläge getestet, Welche? Es gab mehrere, allein Karl Heinz hat mehrere Varianten vorgeschlagen. Am schnellsten wird die PC Variante sein, ok, nicht wenn man die Zeit für das umstecken der Karte mit berechnet :-) Hei eines SD Karte sollte man vieleicht auch den Augenmerk auf möglichst wenig Schreibzugriffe legen, insofern ist ein Quicksort auf Dateiebene garantiert NICHT die schnellste Variante. Wenn du das Problem öfter als einmal hast, solltest du vielleicht darüber nachdenken ob du deine structur nicht geignet, erweitern willst. Spontan denke ich das an eine Art rb-tree, vielleicht auch mehre wenn du nach mehr als ein Kriterium suchen willst/must. Das Prinzip ist nicht neu die btrfs entwickler machen das so, das kann man sicher auch auf wenig wenig speicher und wenig write zugriffe Optimieren. Allerdings wirst du dann sicher deine SD Karte erstmal an den PC stecken und in die neue struct Konvertieren. Ein ganz primitiver Ansatz: *Datei A öffnen *Kleinste(s) Element(e) bestimmen *In Datei B kopieren *Nächst kleinste(s) Element(e) bestimmen *Kopieren ... ... *Datei A löschen *Datei B in A umbennen Kommt mit sehr wenig RAM und relativ wenig Schreibzugriffen aus, skaliert aber nicht gut. Mit der Variante von A.K. ließe sich das kombinieren und beschleunigen. Edit: Nicht ganz das gleiche, aber relativ ähnlich ist Selection Sort. http://en.wikipedia.org/wiki/Selection_sort Gruß Reinhard Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.
|
|
Thread beobachten
Seitenaufteilung abschalten