Nachdem eine Suche nach "Suchfunktion" immer nur Beiträge findet, dass man doch die Suchfunktion verwenden soll (auch bei Google nicht besser), muss ich doch einen neuen Beitrag anfangen. Also: ich habe nach einem 1W-ROM-Search eine Liste von IDs (DS18B20 Temperatursensoren, 8 Byte pro Eintrag) im SRAM eines ATmega8. Einer der Sensoren ist wichtig und deswegen merke ich mir dessen ID im EEPROM, sodass man auch nach einem Reset noch weiß, welcher es war. Allerdings muss ich nach einem Neustart überhaupt erst einmal herausfinden, ob er noch da ist bzw. ob sich seine Position in der Liste geändert hat (kann ja sein, dass was ausgetauscht wurde). Jede Idee, das zu implementieren, die ich habe, kommt mir extrem ineffizient vor. Hat jemand schonmal sowas in AVRASM2 gemacht?
Wo kommt denn die Liste her? Wer baut die auf und wie? Wenn es eine lineare Liste ist, wird nur lineare Suche helfen. Wenn das zu langsam ist (bei wie vielen Einträgen eigentlich), muß man keine lineare Liste aufbauen, sondern halt was anderes (Binärbaum, Hashtabelle). Falls du das Aufbauen der Liste in der Hand hast, kannst du doch gleich nebenbei den interessanten Eintrag merken, anstatt zum Schluß nochmal die Liste durch zu ackern.
Chris O. schrieb: > Nachdem eine Suche nach "Suchfunktion" immer nur Beiträge findet, dass > man doch die Suchfunktion verwenden soll (auch bei Google nicht besser), > muss ich doch einen neuen Beitrag anfangen. "Suchalgorithmus" wäre der bessere Begriff.
Da die Liste auf einem AVR ja nicht allzu lang sein kann, wahrscheinlich in einem statischen Array, wuerd ich jeden Eintrag vergleichen. Auf einem PC hingegen, mit tausenden bis Millione Eintraegen wuerd ich einen balancierten Binaerbau nehmen.
Ich weiß ja nicht, wie lang Deine Liste ist, aber z.B. 20*7Byte zu vergleichen, kostet kaum Zeit. Da lohnt sich ein aufwendigerer Algorithmus nicht. Du kannst auch zuerst nur die CRC vergleichen und dann den Rest. Peter
An dem Tag bin ich wohl einfach schon zu lange davor gesessen und hatte eine Blockade. Alles was ich hingeschrieben habe, war immer voll von JMPs und breaks und ich habe jede Menge Register gebraucht. Jetzt wo ich wieder etwas länger Zeit gehabt habe, habe ich's nochmal versucht und bin mit dem Ergebnis eigentlich ganz zufrieden. Dass die IDs genau 8 Byte lang sind, macht das ganze natürlich um einiges praktischer (bei kürzeren könnte man natürlich ein padding machen). So nebenbei hat sich bei dem Algorithmus auch noch ergeben, dass ich die IDs jeweils vom niedrigsten Byte an vergleiche, wo die Chance am größten ist, dass sie sich unterscheiden (die ersten Bytes geben ja Gerätetyp u.ä. an und sind bei allen gleich) und ich so schneller zum nächsten springe, falls ein Byte nicht passt. spärlich kommentiert das Ergebnis:
1 | lds counter, ow_devices ; Anzahl der Geräte |
2 | lsl counter ; x8 Byte pro ID |
3 | lsl counter |
4 | lsl counter |
5 | |
6 | load_settings_core_sensor_search: |
7 | ldi XH, HIGH(ow_device_id_temp+8) ; zu suchender Sensor |
8 | ldi XL, LOW(ow_device_id_temp+8) |
9 | ldi YH, HIGH(ow_device_ids) ; Sensor-Liste |
10 | ldi YL, LOW(ow_device_ids) |
11 | add YL, counter ; Speicher-Position hinter letzter ID |
12 | clr data |
13 | adc YH, data |
14 | |
15 | load_settings_core_sensor_search_next_byte: |
16 | dec counter |
17 | ld data, -X |
18 | ld temp3, -Y |
19 | cp data, temp3 |
20 | brne load_settings_core_sensor_search_next_sensor ; ID unterschiedlich -> nächster Sensor |
21 | |
22 | mov temp3, counter |
23 | andi temp3, 0b00000111 |
24 | brne load_settings_core_sensor_search_next_byte ; noch nicht beim letzten Byte der ID |
25 | |
26 | lsr counter ; 8 Bytes gleich, Sensor gefunden |
27 | lsr counter ; /8 |
28 | lsr counter |
29 | inc counter ; counter enthält nun Position des Geräts |
30 | rjmp load_settings_core_sensor_search_done |
31 | |
32 | load_settings_core_sensor_search_next_sensor: |
33 | andi counter, 0b11111000 ; restliche Bytes des Sensors überspringen |
34 | brne load_settings_core_sensor_search ; Zähler noch nicht null |
35 | |
36 | load_settings_core_sensor_search_done: |
37 | sts core_sensor, counter |
Für Anmerkungen bin ich immer noch dankbar. Sonst für die Suchfunktion ;-) : Suchroutine, Suchalgorithmus, Search-Funktion
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.