Hallo Programmierer und Bastler, ich habe bei einer UART-Übertragung immer 5-Stellige Strings, welche nacher mit einer Liste von Befehlen verglichen werden sollte. Derzeit frage ich alles über eine Switch-Verknüpfung ab. Da es aber jetzt kanpp 100 Befehle sind, weiß ich nicht, ob es auch anderst besser und schneller geht. Also wie programmiert man sowas am besten?! Wär dankbar, wenn mir jemand helfen könnte!
Du machst eine Baumstruktur auf. Wenn du z.B. die Befehle "stop" "start" "save" "read" "reassign" "radix" hast, würde die Baumstruktur z.B. folgendermaßen aussehen:
1 | R |
2 | +E |
3 | +A |
4 | +ssign |
5 | +d |
6 | +adix |
7 | |
8 | S |
9 | +T |
10 | +art |
11 | +op |
12 | +ave |
d.h. bis zu einem bestimmten Zeichen gleiche Zeichenfolgen werden zusammengefasst. Das spart dir unnötiges Vergleichen ganzer Strings. Irgendwo gab es auch mal einen Parser, der irgendwas xml-ähnliches gefressen und mit ein bisschen "GCC Magic" ausführbaren Code erzeugt hat. Gibt vielleicht auch einen Artikel dazu. mfg mf
Prerequisits: Eine Hashfunktion aussuchen die bei Deinem Wertevorrat nicht kollidiert. Zur Laufzeit: - Hashwert ausrechnen - mit bsearch nach Hash in Tabelle suchen
Der Schlüssel hierzu heißt "hash". Du wandelst den String in einen Zahlenwert (den Hash). Der Hash wird dann zur ersten Auswahl verwendet. Wichtig ist: Mehrere String können unter Umständen den gleichen Hash haben - das nennt man dann Kollisionen. Bei guten Hashalgorithmen ist die Wahrscheinlichkeit von Kollisionen gering. Den endgültigen Vergleich musst Du dann hinterher durchführen. Siehe: http://www.cse.yorku.ca/~oz/hash.html http://www.javamex.com/tutorials/collections/hash_function_technical.shtml (Java, ist aber hier egal) fchk
Okay, danke schonmal! Ist es nicht platzsprender, wenn ich auf dem ATmega2560 einfach alles in eine Switch reinhau?! Da nehmen die einen Unsigned Long. Der braucht ja richtig platz auf dem Controller. Und wie genau mach ich dann die Abfrage mit der Hash-Zahl und meinen anderen Strings?!
Wie geht denn ein "switch" über eine liste von strings? In C zumindest muss der ausdruck eine zahl sein. Der compiler optimiert die suche nach dem treffenden case dann selbst (log(n)). Die schnellste implementierung dürfte ein scanner / zustandsautomat sein. Sowas wie zur umsetzung von regulären ausdrücken verwendet wird. C code dafür kann man mit (f)lex erzeugen. Platzsparend (quellcode als auch zielcode) dürfte die verwendung eines arrays mit jeweils zwei einträgen pro index sein: (string,aktion). Über eine schleife sucht man den passenden string, und hat dann auch gleich die aktion dazu (command, address, whatever). Ein Hash oder ein (B-)Tree sind vllt. etwas aufwändig hier, es sei denn du hast bereits entsprechende libs. Sind die strings wirklich bloss 5 zeichen (buchstaben und ziffern) lang, dann kannst du dir einen eindeutigen 32 bit integer für jeden string berechnen (wertevorrat pro zeichen bspw. 0..35 für [A-Z0-9]) und dann tatsächlich einen "switch" machen. Das wäre dann fix und platz sparend.
Also nach allem was ich nun gelesen habe habe ich mich dazu entschieden den empfangenen Befehl in ein Array zu laden. Nun vergleiche ich den ersten Buchstaben mit eienr Reihe von Anfangsbuchstaben aller meiner Befehle. Ist der richtige dabei geht es mit dem Zweiten weiter. Passt auch dieser wird das ganze Wort mit einem String verglichen.
Also strcmp :-) http://www.mikrocontroller.net/articles/FAQ#Wie_funktioniert_String-Verarbeitung_in_C.3F
Also str(n)cmp vergelicht doch nur bis zum ersten Unterschied. Damit macht es also auch nix anderes, als wenn man das von Hand vergleicht. Ich weiß nicht, ob es für ein paar Befehler via USART sehr viel Sinn macht dem ATmega eine komplexe Hash-Funktion aufzubrummen, oder sich selbst es an zu tun, diese Hashes vorab alle zu berechnen und dann in einer Liste zu pflegen. Ich mache das im Groben einfach so:
1 | const char sBefehl1[] = "BEF1"; |
2 | const char sBefehl2[] = "JUMP"; |
3 | const char sHelp[] = "Help"; |
4 | |
5 | int fBefehl1( void *arg) |
6 | {...}
|
7 | |
8 | int fBefehl2( void *arg) |
9 | {...}
|
10 | |
11 | int fHelp( void *arg) |
12 | {...}
|
13 | |
14 | typedef struct { |
15 | const char *cmds; |
16 | int (*fkt)(void*); |
17 | } befTab; |
18 | |
19 | const befTab[] = { |
20 | { sBefehl1, fBefehl1 }, |
21 | { sBefehl2, fBefehl2 }, |
22 | { sHelp, fHelp }, |
23 | { NULL, NULL }, |
24 | };
|
25 | |
26 | int Kommando( const char *cmd) |
27 | {
|
28 | int ret = -1; /* Nimm an, unbekanntes Kommando */ |
29 | befTab *b = &befTab[0]; |
30 | |
31 | while (b->cmds) { |
32 | /* Suche Kommando */
|
33 | if (!strncmp(b->cmds, cmd)) { |
34 | /* rufe funktion für gefundenen string auf */
|
35 | ret = (b->fkt)(cmd); |
36 | break; |
37 | }
|
38 | /* gehe zu nächstem Kommando*/
|
39 | b++; |
40 | }
|
41 | return ret; |
42 | }
|
Ist nur ein kurzer Ausschnitt, man kann das noch verfeinern, in dem man für alle Funktionen standartisierte Return-Codes ausmacht, die z.b. bei einem Kommando-Interpreter sagen, ob falsche Parameter oder fehlende Parameter übergeben wurden. Im Grunde macht es so eine Konstruktion aber sehr einfach, auch später noch Kommandos hinzu zu fügen. Fügt man noch weitere Spalten in die Tabelle ein, so kann man z.B. Berechtigungen oder Min- und Max-Werte einsetzen. Habe schon ganze Geräte rund um eine einzige solche Tabelle entwickelt und das auf deutlich kleineren AVRs als dem oben genannten. Statt void* arg kann man auch definierte Typen übergeben oder mehrere Parameter. Der Phantasie sind da keine Grenzen gesetzt. Gruß, Ulrich
Ein bsearch für 100 Kommandos über einen Hash wäre nach 7 Iterationen schon fertig. Aber macht ruhig so langweilig weiter.
... schrieb: > Ein bsearch für 100 Kommandos über einen Hash > wäre nach 7 Iterationen schon fertig. > > Aber macht ruhig so langweilig weiter. :-) Vielleicht irre ich mich, aber ich denke es wäre schon ein Gewinn, wenn er erst mal mit Strings generell umgehen kann. Sein Eröffnungsposting macht mir nicht so den Eindruck. Ich denke allerdings auch, dass da noch mehr dahintersteckt. Wo gibt es schon 100 Kommandos, die absolut nichts miteinander zu tun haben? Irgendeine Systematik gibt es doch meistens. Meistens hat man doch eine Handvoll Hauptkommandos (SET, GET, ...) mit jeweils einigen Subkommandos (UART, PORT, ...) also eine Art Verb/Noun System.
Karl Heinz Buchegger schrieb: > Irgendeine Systematik gibt es doch meistens. Wenn man eine Datenstrom aus Token parsen will, ja. Für die Token selber hat man nichts von der Systematik. > Vielleicht irre ich mich, aber ich denke es wäre schon ein Gewinn, wenn > er erst mal mit Strings generell umgehen kann. Sein Eröffnungsposting > macht mir nicht so den Eindruck. Den Eindruck teile ich mit Dir. :-)
Das war ja auch der Grund, warum ich auf den Hash nicht eingegangen bin. Ich hoffte, dass mein Beispiel zeigt, wie man es einfach, flexibel, portierbar und verstehbar machen kann. Schauen wir mal was kommt :) Das mit dem Hash ist eigentlich eine coole Sache. Spart im Vergleich zu den sonst notwendigen Strings eine Menge Flash und BitShift ist für meine Cortexe nur ein müdes Lächeln, da im Thumb2 ISet viele Befehle mit einem Shift N kombiniert werden können. Auf einem AVR hingegen ist das eine Hand voll Arbeit, da er leidlich ein Shift 1 beherrscht. Bei einem ARM/Cortex kann man auch sehr einfach mit 32 Bit umgehen, aber bei einem AVR multipliziert sich der notwendige Code recht deutlich. Man müsste beides mal gegeneinander stellen und die LST files vergleichen. Bin mir aus dem Bauch heraus jetzt nicht sicher, was da beim AVR besser abschneidet, sowohl in Code-Size, als auch in der Performance. Ich nehme mal an, dass es beim Code-Size einen Schnittpunkt gibt, bei dem irgendwann der strcmp größer als der hash wird. Gruß, Ulrich
Hashfunktionen können sehr simpel sein.
Nichts mit viel Schieben und 32-bit...
char cmds[4][5]="mama","holt","papa","bier";
int hashfun(cmd)
char *cmd;
{
int i,hash;
for(i=hash=0;i<strlen(cmd);i++)
hash+=(cmd[i]^0x38);
return hash&0xFF;
}
cmd hash
mama 0x5C
holt 0x47
papa 0x42
bier 0x52
Also so einen Baum müsste man rekursiv durchsuchen, oder? Jedenfalls erinnert mich das an die Zeiten, in denen ich im Informatik-Unterricht die Schüler-Daten der Schule per Pascal Programm in den PC bringen sollte, natürlich mit Suchfunktion und allem anderen. Per Bubblesort hat das ewig gedauert. Mit Bäumen war das ein Kinderspiel. Allerdings habe ich da volle Rekursion von Pascal Prozeduren verwendet. Naja, damals war ein XT auch nicht schneller als ein AVR heute, nur (etwas) mehr RAM hat er gehabt. daher frage ich mich, ob ein AVR genug Stack aufwarten kann, wenn sich die Suchfunktion rekursiv durch den Baum hangelt. Nö, eigentlich muss man das nicht mal rekursiv programmieren... Gruß, Ulrich
Ulrich P. schrieb: > Per Bubblesort hat das ewig gedauert. Mit Bäumen war das ein > Kinderspiel. Das ist aber auch keine Kunst. Bubble Sort ist für solche Dinge so ziemlich das ungeeignetste Sortierverfahren überhaupt. Das ist ungefähr so, wie wenn du beim Hausbau den Sand vom LKW mit dem Sandkastenschäufelchen des Junior abladen willst. Hättest du ein anständiges Sortierverfahren genommen, hättest du dir eine Menge Arbeit erspart. > Naja, damals war ein XT auch nicht schneller als ein AVR heute, nur > (etwas) mehr RAM hat er gehabt. daher frage ich mich, ob ein AVR genug > Stack aufwarten kann, wenn sich die Suchfunktion rekursiv durch den Baum > hangelt. > > Nö, eigentlich muss man das nicht mal rekursiv programmieren... Baumfunktionen? Macht man sinniger weise rekursiv. Die maximale Rekursionstiefe ist gleich der Baumtiefe. und du steigt mit dem Logarithmus Dualis. Also sehr langsam. Bei 1024 Knoten ist die Rekursionstiefe grade mal 10. Bei 4096 Knoten ist sie erst auf 12, bei 10000 sind wir bei 14. etc etc. Also alles kein Drama. Da kosten dich die Verpointerungen um den Baum aufzubauen viel mehr Speicherplatz als du für die rekursiven Aufrufe Stack brauchst.
Hi Karl Heinz! War mir damals auch schon klar. Aber im Informatik-Unterricht wurde einem nur das Bubble-Sort beigebracht, den Baum habe ich mir selbst erarbeitet. Pointer in der 10. Klasse? Wenn unsere Lehrer mal soweit gewesen wären :) Beim Zeitvergleich ( Einlesen der Schülerzahlen von Floppy und suchen nach einem Datensatz) war das Baum-Verfahren jedenfalls haushoch überlegen. --- Ich sagte ja, dass man das rekursiv machen kann, aber ich habe mir keine Gedanken über das gemacht, was ein Compiler daraus veranstaltet und wie viel Stack das dann jedes mal benötigt. Normal würde ein Funktionsaufruf wenigstens mal die Rücksprungadresse und die Arbeitsregister auf den Stack werfen. Nehmen wir mal an, dass das 6 Worte sind, dann wären das nach Deiner nachvollziehbaren Rechnung lediglich 120 Bytes. Kann auch ein AVR verdauen. Bei einem AVR müsste man für die Daten jeweils den string zusammen mit zwei pointern a 2 bytes einrechnen. Bei einem nicht voll ausbalancierten Baum könnte man aber statt des vollen Strings auch nur die der aktuellen Suchtiefe übereinstimmenden Teilstrings angeben. Das würde den Platzbedarf reduzieren. Ein voll ausbalancierter Baum müsste für lediglich 4 zeichen aus a..z schon 429981696 Blätter / Knoten anlegen. Das würde den Platz im Flash sprengen :) Jedenfalls wäre das eine effektive Methode nach beliebigen strings in einem Datenstrom zu suchen. Vor allem dann, wenn man den Baum von Hand im Flash aufbaut. Dann spart man dem Controller einige Arbeit und etliches an RAM. Andererseits kann man die Strings auch im Flash ablegen und der Baum pointet nur auf die Strings, dann kann man den auch beim Start kurz mal initialisieren. Kostet aber denn 3x2 bytes :) Gruß, Ulrich
Thread beobachten
Seitenaufteilung abschaltenBitte 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.