1. Home
  2. Electronics (German)
  3. Sortieralgorithmus für EEPROM an uC gesucht

Sortieralgorithmus für EEPROM an uC gesucht

Hallo,

m=F6glicherweise nicht ganz die richtige NG, aber hier gibt's ja auch reichlich Embedded-Spezialisten.

Die Fakten: ATtiny44 mit externem I2C-EEPROM 24C512 In dem EEPROM befindet sich eine Liste (nicht verkettet) je mit 48 Byte gro=DFen Elementen (also insgesamt max. 1365 St=FCck). Die Liste kann "l=F6chrig" sein, d.h. einige Elemente in der Liste sind ggf. leer.

Die Elemente werden prinzipiell erstmal unsortiert belegt. Das Problem besteht darin, die Elemente der Liste nach M=F6glichkeit sortiert auszulesen.

1=2E Hat jemand eine gute Idee, wie die Sortierung beim Auslesen durchgef=FChrt werden k=F6nnte (zur Erinnerung: der ATtiny44 hat 256 Byte RAM, von dem noch ein Teil f=FCr andere Zwecke ben=F6tigt wird)? Mir f=E4llt dazu nichts ein. Erschwerend kommt noch hinzu, da=DF das ganze so organisiert sein soll, da=DF von einem gegebenen Element aus nach Wunsch des Benutzers jeweils das n=E4chstgr=F6=DFere bzw. n=E4chstkleinere gefunden werden kann. Das Durchfl=F6hen des gesamten EEPROMs nach jeder Benutzeraktion, um das n=E4chste Element zu finden, wirkt selbst bei einigen 100 kHz I2C-Takt schon etwas z=E4h...

2=2E Alternativ k=F6nnte der Inhalt des EEPROMs bei Bedarf von Zeit zu Zeit sortiert werden. Nun ist es aber so, da=DF Schreibzugriffe auf das EEPROM im sprichw=F6rtlichen Sinne "teuer" sind. Die =FCblichen effizienten Sortieralgorithmen ala Quicksort & Co. verursachen durch die h=E4ufigen Element- und Teilfeldvertauschungen ein hohes wear out der EEPROM-Speicherzellen. Eine vorher ggf. notwendige Garbage Collection - um eine zusammenh=E4ngende Liste zu haben - t=E4te ein =DCbriges. Welches Sortierverfahren bietet sich f=FCr den Fall "teurer" Speicher- Schreibzugriffe an (unter Beachtung der sehr limiterten RAM-Ressourcen und der "l=F6chrigen" Liste)? Ich habe derzeit eine Variante des "Selectsort" implementiert, erreiche bei 8 MHz Prozessortakt aber Laufzeiten von gut 11 Minuten f=FCr 1365 Elemente :-(

Gru=DF Horst

Reply to
Horst Meier
Loading thread data ...

"Horst Meier" schrieb im Newsbeitrag news: snipped-for-privacy@h2g2000hsg.googlegroups.com...

Ebenso, wie du bei einem Durchlauf das naechstkleinste Element finden kannst, kannst du dir gleich die Adressen der n kleinsten Elemente merken (je nach uebrigem RAM, maximal also 128, dann merkst du dir nur die Adresse und nicht den Schluessel), und diese dann direkt und gezielt nacheinander ausgeben, bevor du einen erneuten Durchlauf brauchst.

--
Manfred Winterhoff, reply-to invalid, use mawin at gmx dot net
homepage: http://www.geocities.com/mwinterhoff/
de.sci.electronics FAQ: http://dse-faq.elektronik-kompendium.de/
Read 'Art of Electronics' Horowitz/Hill before you ask.
Lese 'Hohe Schule der Elektronik 1+2' bevor du fragst.
Reply to
MaWin

Passt zwar nicht direkt aber eventuell lässt sich das Problem biegen:

"Hashing für RFIDs" S. 12

formatting link
( Kann man auch kostenpflichtig, aber etwas flüssiger layouted, auf
formatting link
in Heft 9 haben ).

D.h. man empfängt vom RFID/Transponder einen 64 Bit Schlüssel und muß nun das EEPROM absuchen ob man für den die Tür aufmachen soll. Elegant ist Hashing, weil man damit lange Liste in viele kurze zerlegt. ( Die dort beschriebene Krücke wegen kurzer CRCs ist nichtmehr nötig, inzwischen bei Phil Koopman kurze gefunden. )

Und wenn ich schon bei der Werbung bin: alle Jahrgänge der Zeitschrift der FORTH e.V. bis zurück zu 1984 sind als pdf kostenlos direkt als download verfügbar:

formatting link
Nicht alle enthalten was für embedded aber aktuelle Ausgaben sind ein AVR-Sonderheft:
formatting link
und Ausgabe 1/2007 mit Beitrag über CSD-Zahlendarstellung welche bei Multiplikation von Konstanten per Shift&Add auf Controllern nützlich ist.

MfG JRD

Reply to
Rafael Deliano

Ein sortierter Index im EEPROM mit pointern auf die Daten. Umsortieren und neuschreiben ins EEPROM sollte dann (bei 1-Byte-Index) um den Faktor 44 schneller sein.

Nick

Reply to
Nick Mueller

Ein unsinniges Prinzip, da Du die Daten sortiert brauchst.

...verkette die Liste und halte den Speicher lückenlos. Das kostet ein paar Byte Header für Anfang&Ende sowie 2 Byte Pointer auf den Nachfolger je Datenlement

Für 1300 verkettete Elemente kommst Du auf 1 Sekunde.

--
Gruß, Raimund
Mein Pfotoalbum 
Mail ohne Anhang an  wird gelesen. Im Impressum der Homepage
findet sich immer eine länger gültige Adresse.
Reply to
Raimund Nisius

Würde man den Index jedesmal sortieren, wenn ein Element in die Tabelle eingefügt oder geändert wird, bedeutet dies eine Menge Schreibzugriffe auf den Index.

Wenn du in den Index einen Pointer einfügst, musst du auf jeden Fall alle folgenden Pointer im EEProm verschieben. Im Schnitt also die Hälfte der bereits belegten Zellen. Wenn die Tabelle mit ca. 1000 Elementen aufgebaut wird, kommt da schon einiges zusammen (?? 250.000 ??).

Das macht also nur Sinn, wenn man wirklich nur von Zeit zu Zeit den Index sortiert.

Die Idee mit der verketteten Liste erscheint mir daher besser. Oder man baut den Index als verkettete Liste auf. Das macht aber vermutlich keinen Sinn, oder?

Gruß

Stefan DF9BI

Reply to
Stefan Brröring

Letztendlich besteht hier das gleiche Problem wie bei einem Dateisystem auf einem PC-Laufwerk. Also gibt es genug Literatur zu finden. Eine gesunde Mischung aus Vorsortierung und chronologischer Aufzeichnung sollte praktikabel sein. Und wenn dann das Dateisystem halbwegs absturzsicher wird, freut sich der Anwender!

Gruß - Henry

--

formatting link

"Stefan Brröring" schrieb im Newsbeitrag news:f2e8b8$o23$ snipped-for-privacy@news1.ewetel.de... | Nick Mueller wrote: | > Horst Meier wrote: | >

| >

| >>Die Elemente werden prinzipiell erstmal unsortiert belegt. | >>Das Problem besteht darin, die Elemente der Liste nach Möglichkeit | >>sortiert auszulesen. | >

| >

| > Ein sortierter Index im EEPROM mit pointern auf die Daten. Umsortieren und | > neuschreiben ins EEPROM sollte dann (bei 1-Byte-Index) um den Faktor 44 | > schneller sein. | >

| >

| > Nick | | Würde man den Index jedesmal sortieren, wenn ein Element in die Tabelle | eingefügt oder geändert wird, bedeutet dies eine Menge Schreibzugriffe | auf den Index. | | Wenn du in den Index einen Pointer einfügst, musst du auf jeden Fall | alle folgenden Pointer im EEProm verschieben. Im Schnitt also die Hälfte | der bereits belegten Zellen. Wenn die Tabelle mit ca. 1000 Elementen | aufgebaut wird, kommt da schon einiges zusammen (?? 250.000 ??). | | Das macht also nur Sinn, wenn man wirklich nur von Zeit zu Zeit den | Index sortiert. | | Die Idee mit der verketteten Liste erscheint mir daher besser. | Oder man baut den Index als verkettete Liste auf. Das macht aber | vermutlich keinen Sinn, oder? | | Gruß | | Stefan DF9BI

Reply to
Henry

uf einem PC-Laufwerk. Dies scheint nur auf einen ganz schnellen Blick so... Das Problem liegt in den begrenzten Ressourcen des uC. Niemand wird auf einem PC nach jedem Sortierschritt den entsprechenden Laufwerkssektor sofort wieder zur=FCckschreiben, sondern den gesamten Index ins RAM laden, dort sortieren und erst am Ende auf einen Schlag auf die Platte schreiben. Genau dieses Verfahren funktioniert aber mit dem uC nicht, sobald der Index die Gr=F6=DFe des freien RAM =FCberschreitet (im =DCbrigen kommt man mit einem Byte Index auch nicht weit, wenn =FCber

1000 Datens=E4tze zu verwalten sind). Desweiteren sollte es einer Festplatte auch nichts ausmachen, wenn ein Sektor eine Million Mal neu beschrieben wird; g=E4ngige EEPROM-Speicherzellen sind da u.U. bereits an ihrem Lebensende. BTW: Ein Directory wird direkt auf einer Festplatte eher selten sortiert, von daher ist der Vergleich mit einem Filesystem nicht so richtig naheliegend...

Anyway, vielen Dank f=FCr Eure Tips. Ich werde mich mal mit der verketteten Liste besch=E4ftigen und daf=FCr halt 3 oder 4 Byte f=FCr die zwei Pointer pro Element (soll ja vorw=E4rts und r=FCckw=E4rts durch die Liste gehen) vom EEPROM-Speicher opfern.

Gru=DF Horst

Reply to
Horst Meier

Hm Horst -

Du darfst das Rad natürlich gerne neu erfinden. Zum einen gibt es genug Infos über solche Systeme, wenn du dich mal bei den PC-Dateisystemen über deren theoretischen Grundlangen informierst und nicht "PIC EEPROM file system" in Google eingibst - weil da kommt viel weniger high-value Info. Zum anderen gibt es auch recht günstige Alternativen zu EEPROMs, die kein wear-out kennen, z.B. ferromagnetische, sogar pin- und weitgehend protokollkompatibel. Da hier meist kleine Stückzahlen gefahren werden, ist es oft sinnvoller technisch teurere Lösungen zu verwenden als zig Mannstunden in Algorithmenentwurf zu investieren. So ein Dateisystem ist performant eine Herausforderung!

Eine vorwärts und rückwärts verkettete Liste wäre erstmal die direkte Lösung im Sinne des Schulunterrichts.

Wie gesagt, denke nochmal über meinen Vorschlag über ein teilsortiertes, halbchronologisches System nach. Oder suche dir einen wirklich kompetenten "Informatiker". Manche Leute denken da einfach weit effektiver und man muß es einfach akzeptieren. Wenn die dann noch kostengünstig sind ...

War ja nur gut gemeint - Henry

--

formatting link

"Horst Meier" schrieb im Newsbeitrag news: snipped-for-privacy@o5g2000hsb.googlegroups.com... > Letztendlich besteht hier das gleiche Problem wie bei einem Dateisystem auf

einem PC-Laufwerk. Dies scheint nur auf einen ganz schnellen Blick so... Das Problem liegt in den begrenzten Ressourcen des uC. Niemand wird auf einem PC nach jedem Sortierschritt den entsprechenden Laufwerkssektor sofort wieder zurückschreiben, sondern den gesamten Index ins RAM laden, dort sortieren und erst am Ende auf einen Schlag auf die Platte schreiben. Genau dieses Verfahren funktioniert aber mit dem uC nicht, sobald der Index die Größe des freien RAM überschreitet (im Übrigen kommt man mit einem Byte Index auch nicht weit, wenn über

1000 Datensätze zu verwalten sind). Desweiteren sollte es einer Festplatte auch nichts ausmachen, wenn ein Sektor eine Million Mal neu beschrieben wird; gängige EEPROM-Speicherzellen sind da u.U. bereits an ihrem Lebensende. BTW: Ein Directory wird direkt auf einer Festplatte eher selten sortiert, von daher ist der Vergleich mit einem Filesystem nicht so richtig naheliegend...

Anyway, vielen Dank für Eure Tips. Ich werde mich mal mit der verketteten Liste beschäftigen und dafür halt 3 oder 4 Byte für die zwei Pointer pro Element (soll ja vorwärts und rückwärts durch die Liste gehen) vom EEPROM-Speicher opfern.

Gruß Horst

Reply to
Henry

Das ist wahrscheinlich das günstigste. Eventuell kannst du noch 5 bis 10 Datensätze im Ram opfern. Dadurch würde sich die suchzeit fünfteln oder Zehnteln.

--
MFG Gernot
Reply to
Gernot Fink

Henry schrieb:

Bitte lies

formatting link
und verinnerliche=20 das. Auch ein Realname wird hier gerne gesehen.

Guido

Reply to
Guido Grohmann

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.