Hallo, Der Betreff sagt ja eigentlich schon alles: Ich möchte die Einträge in einer Verzeichnistabelle von einem FAT Dateisystem alphabetisch sortieren. Da der Speicher im AVR nicht ausreicht, kann ich nicht alle Dateinamen in ein Array laden. Die üblichen Sortieralgorithmen wie Bubblesort, Quicksort usw. fallen also flach, da diese ja darauf angewiesen sind die Elemente verschieben zu können. Ich würde es jetzt so machen, dass ich für den ersten Eintrag das kleinste Element suche, und dieses im Speicher halte. Um weitere Einträge zu erhalten, suche ich das kleinste Element das größer ist als das gespeicherte Element, speichere dieses wieder usw. Das ganze dürfte aber sehr schnell sehr langsam werden, gibts da effizientere Algorithmen die nicht darauf angewiesen sind die einzelnen Elemente verschieben zu können und möglichst wenig Speicher brauchen?
An deiner stelle würd ich folgendes versuchen: Du legst in deinem AVR nicht die dateinamen sondenr nur einen index (quasi ein link/pointer) zu dem entsprechenden Eintrag an. So kannst du prinzipiell deinen Quicksort/Bubblesort wieder anwenden. Beispiel: Dateinamen: Dateiname: ADatei.txt BDatei.txt DDatei.txt CDatei.txt Adresse: 1 2 3 4 Speicher AVR: 1 2 3 4 nun der sort-algorythmus; Ergebniss: Speicher AVR: 1 2 4 3 Hab sowas noch nie gemacht, mein beitrag ist nur ein gedankt, daher wär es nett, wenn ich eine rückmeldung ung den code bekommen könnte wenn du diese sache hinbekommst. MfG
Hallo, Im Prinzip würde das gehen denk ich, aber der Pointer auf eine Datei (die Cluster-Adresse) ist bei FAT16 16 Bit und bei FAT32 sogar 32 Bit, bei FAT16 kann das Root-Verzeichnis maximal 512 Einträge besitzen, bei Unterverzeichnissen gibts glaub ich gar keine Beschränkung... Aber selbst wenn man bei FAT16 und 512 Einträgen bleibt, wär das schon 1kB. Mit nem mega128 müsste das schon noch drin sein, aber wenn ich auf Festplatte mit FAT32 umsteige (arbeite momentan noch mit einer MMC) würd das langsam echt unhandlich. Wobei man müsste die Pointer Größe eigentlich auch bei FAT32 auf 16 Bit beschränken können, in dem man nicht die Cluster-Adresse speichert sondern die Nummer in der Verzeichnis-Tabelle... Ich denke ich werds mal auf diese Weise probieren.
dann geb nur einmal einen den pointer auf den ersten eintrag in der liste an. Dann nummerrierst du alle restlichen dateien von eins bis 256. Die Adressen kannst du dann berechnen/ermitteln. aber auf diese art sind auch nur 256 dateien drin. Als Alternative fällt mir nur noch folgendes ein: Du schreibst dir eine funktion namens GetFile(int index); bsp: index = 5; nun durchsucht dein Programm die liste 5x jeweils nach dem Eintrag der an erster stelle der sortierten liste stehen müsste und speichert seinen index ab (sortiert ihn aus). nun bei dem nächsten durchgang (von den 5 stück) wird der eintrag mit dem index, der aussortiert wurde, einfach ignoriert und somit der 2. eintrag in der liste ermittelt. Dies machst du nun so oft, bis du die entsprechende datei gefunden hast.
@Simon >Die Adressen kannst du dann berechnen/ermitteln. Es gibt da natürlich das Problem, daß die Dateien nicht alle schön brav der Reihe nach angeordnet sind. >Als Alternative fällt mir nur noch folgendes ein: >Du schreibst dir eine funktion namens GetFile(int index); Diesen Ansatz hatte ich mal probiert, hat soweit auch funktioniert. Prolem ist nur, daß diese Methode bei SEHR vielen Datein extrem langsam wird.
ich denk daran wird jeder ansatz scheitern. entweder schnell und einiges im speicher (indextabellen, dateinamen...) oder langsam und sparsam (1-2 speicherzugriffe pro vergleich). beides vereinen wird wohl kaum gehen...
Also ich machs jetzt so: Ich habe eine Funktion der ich das zu sortierende Verzeichnis übergebe. Diese sucht dann alle gültigen Dateieinträge und speichert deren Verzeichnistabellenindex in einem Array. Der Index ist ein 16 Bit Wert ich habs jetzt auf maximal 512 Einträge pro Verzeichnis beschränkt, damit ergibt sich eine Array-Größe von 1kB. Mit nem mega128 ist das noch verschmerzbar. Außerdem wird die Start-Cluster-Adresse der Verzeichnistabelle gespeichert. Eine weitere Funktion kann dann jeweils 2 Einträge des Arrays vergleichen. Dafür wird mit Hilfe der Start-Cluster-Adresse und dem Index aus dem Array der Verzeichniseintrag erneut gelesen und der 8.3 Name, sowie die Dateiattribute gespeichert. Die Werte werden dann verglichen und ein entsprechender Wert zurückgegeben. Mit der Vergleichsfunktion und dem Index-Array kann ich dann den in der avr-libc enthaltenen Quick-Sort Algorithmus drauf loslassen. Hinterher stehen dann im Array die Indizes der Verzeichniseinträge in alphabetisch sortierter Reihenfolge mit Verzeichnissen am Anfang. Ich denke das ist ein annehmbarer Kompromis zwischen Geschwindigkeit und Speichernutzung, und mehr als 512 Einträge zu sortieren würde auf dem AVR wahrscheinlich eh zu lange dauern. (Wahrscheinlich sind auch 512 schon viel zu viel) Mit 18,432MHz Takt und einem Verzeichnis mit 25 Einträgen brauch die Funktion zum Lesen und Sortieren jedenfalls ca. 130ms, ich denke das ist ein akzeptabler Wert. Werd jetzt noch ein paar weitere Funktionen hinzufügen, dann gibs das in der Codesammlung.
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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.