Kann ich es geschickter gestalten? Ein switch case entfällt wohl, weil
die Rückgaben von strncmp oder strstr nicht passend sind. Wie umgehe ich
es?
Man könnte die substrings in einen integer umwandeln und dann per switch
case abfragen. Dazu wäre dann ein #define notwendig. Klingt auch
komisch..
evlt. habt ihr tolle Ideen?
Danke schon mal vorab!
Du könntest die Kommandos in eine Stringtabelle ablegen und mit einem
Index solange suchen, bis du das passende gefunden hast. Auf den Index
kannst du dann den switch machen...
Lothar Miller schrieb:> Du könntest die Kommandos in eine Stringtabelle ablegen und mit einem> Index solange suchen, bis du das passende gefunden hast. Auf den Index> kannst du dann den switch machen...
um weiterzuführen:
Oder in einer Struktur und einem Array davon, einen String mit einem
Funktionszeiger kombinieren und so bei einem bestimmten String eine
Funktion aufrufen lassen.
Man könnte auch den String in seine Teilstrings zerlegen und diese Teile
als Vorauswahl für eine oder mehrere Tabellen benutzen. Alle "request"
in einer Tabelle, alle "config" in einer Tabelle.
Man könnte auch mit den Teilstrings eine Art Parsing veranstalten indem
man Techiken aus dem Compilerbau (lexikalische Analyse) darauf anwendet.
Oder .....
Wahrscheinlichere Commandos ganz oben in die Kette reduziert die
Suchzeit, ggf. erst nach dem Prefix suchen:
COMMAND getCommand(char* buffer) {
if (strncmp(buffer, "request:", 8 ) == 0 ) {
if (strncmp(buffer, "ssid:all\n", 8, 17 ) == 0 ) {
return A;
}
if(strncmp(buffer, "ssid:1\n", 8, 15 ) == 0 ) {
return B;
}
}
if(strncmp((char*)buffer_, "config:"), 7 == 0) {
return C;
}
}[/c]
Achtung, Syntax ggf. anpassen...
Eventuell könnte man auch einfach ein Stringarray anlegen was durchsucht
wird und dann den Index zurückgeben, dann müßten Index + Enum
übereinstimmen...
Läubi .. schrieb:> Wahrscheinlichere Commandos ganz oben in die Kette reduziert die> Suchzeit
Wenn die Suchzeit relevant wird, würde ich lieber das Feld mit
bsearch() sortieren und mit qsearch() suchen.
Auch wenn kaum einer die Funktionen nehmen mag, sind sie sehr hilfreich.
Die Frage ist halt ob das
a) die Sortierzeit die verringerte Suchzeit nicht zunichte macht
b) geht das so gut auf einem uC?
Ich hatte eher daran gedacht das ein "exit" eventuell seltener
aufgerufen wird (nämlich nur einmal beim beenden) als ggf. ein "set
value" oder so ;)
imax schrieb:> Kann ich es geschickter gestalten?
Ja.
Für sowas nimmt man ne Tabelle. Diese enthält den String und die
Funktion, die dann aufgerufen werden soll.
Das Ende der Tabelle kennzeichnet ein leerer String.
Nachfolgend ein Codebeispiel für den 8051:
Läubi .. schrieb:> Die Frage ist halt ob das> a) die Sortierzeit die verringerte Suchzeit nicht zunichte macht
Sortiert wird ja nur einmal. Im Idealfall vom Programmierer :-)
> b) geht das so gut auf einem uC?>> Ich hatte eher daran gedacht das ein "exit" eventuell seltener> aufgerufen wird (nämlich nur einmal beim beenden) als ggf. ein "set> value" oder so ;)
Ein O(nlogn) Suchen ist schwer zu schlagen. Ich hab mich mal mit meinem
Compilerbau Praktikumsleiter darüber gestritten. Ich war auf binärem
Suchen, er auf Hashen. Er hatte die Nase ganz knapp vorne.
Läubi .. schrieb:> Die Frage ist halt ob das> a) die Sortierzeit die verringerte Suchzeit nicht zunichte macht
Soertiert werden muß ja nur einmal beim Start (bzw. bei
evtl. Änderungen an der Tabelle, aber die hat man ja eher selten
bis gar nicht).
Das Sortieren kann man sich natürlich ganz sparen, wenn man das
Feld gleich im Quelltext sortiert hält.
> b) geht das so gut auf einem uC?
Warum nicht?
Ich habe das schon gelegentlich gemacht.
Auf einem uC kommt gelegentlich der Einwand, daß Rekursion
an sich und damit bsearch() gaaanz böse ist.
Das ist aber so pauschal wie falsch.
Rekursion ist nur dann gefährlich, wenn man keine Ahnung hat,
wann der Abbruch kommt und folglich mit einem Stackproblem
rechnen muß.
Bei bsearch() dagegen hat man im worst case eine Tiefe von
log2(n), also z.B. bei 1000 Elemente höchstens 10 und bei einer
Million Elemente höchstens 20 etc..
Wenn das aktuelle bsearch() nicht ohnehin iterativ arbeitet...
>> Ich hatte eher daran gedacht das ein "exit" eventuell seltener> aufgerufen wird (nämlich nur einmal beim beenden) als ggf. ein "set> value" oder so ;)
Das ist wahr.
Aber bei den Mengen an Kommandos, wo die Suchzeit relevant wird,
hast du dann immer noch sehr viele im ersten Teil, die regelmäßig
linear durchgeforstet werden.
Daß exit() dann am Schluß steht, hilft etwas, aber nicht
grundlegend.
Bei dem Beispiel mit einer Mio Elementen:
Da wird man mit geschickter Vorsortierung nach Häufigkeit
vielleicht im Schnitt auf etliche Hundert oder ein paar Tausend
Vergleiche kommen bei linearer Suche.
Bei bsearch() im schlimmsten Fall wie gesagt auf 10.
Karl heinz Buchegger schrieb:> Ein O(nlogn) Suchen ist schwer zu schlagen. Ich hab mich mal mit meinem> Compilerbau Praktikumsleiter darüber gestritten. Ich war auf binärem> Suchen, er auf Hashen. Er hatte die Nase ganz knapp vorne.
Da muß man aber nur genug Daten nehmen, daß er die Nase weiter
vorn hat, abgesehen davon daß bsearch nicht O(n*log n)
hat, sondern O(log n) - sonst wäre lineare Suche schneller :-)
Hatten wir das Thema nicht neulich hier schon mal?
Aber es stimmt natürlich:
bsearch ist selbst bei mehr Daten, als in einen MC passen,
ziemlich fix.
Und das bei wenigen Byte Code.
Zudem kann man es ganz gut umfrisieren ("liefere gesuchtes
Element oder das nächstkleinere, falls nicht vorhanden" etc.).
Ist jetzt hier nicht gefragt, aber manchmal nett.
Karl heinz Buchegger schrieb:> Ein O(nlogn) Suchen ist schwer zu schlagen. Ich hab mich mal mit meinem> Compilerbau Praktikumsleiter darüber gestritten. Ich war auf binärem> Suchen, er auf Hashen. Er hatte die Nase ganz knapp vorne.
Das ist wohl wahr, ich hatte nur gedacht es sollte jedesmal sortiert
werden, aber meinst du nicht eher O(log n)? Sonst wäre die lineare Suche
ja schneller ;P
Klaus Wachtler schrieb:> Bei dem Beispiel mit einer Mio Elementen:
Die Problemgröße ist wohl eher < 100...
imax schrieb:> Angefangen mit 4 commands, sind wir mittlerweile bei ca 25 Stk
Das Problem wird sein das das sortieren hier irgenwie bewerten müßte wie
"wichtig" ein Kommando ist, wobei hier fast der GNUPLOT Ansatz
funktionieren könnte das ein Kommando aktzeptiert wird sobald es nicht
mit einem anderem kollidiert, also
e = ec = ech = echo
solange es kein weiteres Kommandogit was mit e anfängt ;)
Klaus Wachtler schrieb:> Bei dem Beispiel mit einer Mio Elementen:> Da wird man mit geschickter Vorsortierung nach Häufigkeit> vielleicht im Schnitt auf etliche Hundert oder ein paar Tausend> Vergleiche kommen bei linearer Suche.> Bei bsearch() im schlimmsten Fall wie gesagt auf 10.
ach so:
Der worst case bei linearer Suche (z.B. Kommando wird gesucht,
das gar nicht enthalten ist) hätte man bei 1 Mio Elemente
dann entsprechend 1 Mio Vergleiche, bis man merkt daß es gar nicht da
ist.
Läubi .. schrieb:> Klaus Wachtler schrieb:>> Bei dem Beispiel mit einer Mio Elementen:> Die Problemgröße ist wohl eher < 100...
Ich glaube auch nicht, daß es hier nötig.
Meine Ausschweifungen bezogen sich auf den Fall, daß die Suchzeit
relevant wird.
Bei 4 oder 10 Kommandos ist es vollkommen wumpe.
Klaus Wachtler schrieb:> bis man merkt daß es gar nicht da> ist.
Für den Fall sollte man außerdem eine mindestens 10 Sekündige
Warteschleife einplanen damit der Nutzer mal sieht was er davon hat und
beim nächastenmal den Kram besser gleich richtig eingibt, außerdem darf
ja nicht der EIndruck entstehen der Controller hätte nicht gründlich
genug gesucht ;P
Hallo,
wenn man selbst bestimmen kann, wie die ankommenden Kommandos aussehen,
dann sende doch nur eine ID.
Wenn es unbedingt leserlich sein soll, versendet man "ID"+"Text" oder
"Text" + "ID".
Dann braucht man nur die passenden Zeichen der ID parsen und in integer
wandeln.
"request:ssid:1\n" würde zum Beispiel zu "request:ssid:1\n01\n"
"01" stände für Einzelanfrage, die 1 aus ssid:1 könnte gesondert
behandelt werden, wenn man flexibel bleiben will.
Klaus Wachtler schrieb:> Läubi .. schrieb:>> Warteschleife
Die Warteschleife ist wirklich unbedingt nötig, weil der Nutzer ja sein
gewohntes Feeling vom 4-Kern 3GHz Windows-PC haben will.
Nicht daß der Nutzer noch nen Herzinfarkt kriegt.
Peter
Klaus Wachtler schrieb:> Da muß man aber nur genug Daten nehmen, daß er die Nase weiter> vorn hat, abgesehen davon daß bsearch nicht O(n*log n)> hat, sondern O(log n)
Nach dem ersten Kaffee seh ich es jetzt auch glasklar.
Genau das hab ich damals auch behauptet: Eine Programmiersprache hat
zuwenig Schlüsselwörter, als das Hashen da noch grossartig was bringt.
Ich denke er hat dann auch lange an der Hashfunktion gefeilt um alle
Kollisionen loszuwerden.
Neuronale Netze fallen mir jetzt noch ein.
Man will ja schliesslich nicht nur PC Feeling sondern auch ein UI mit
Hollywood-Touch :-)
Sind diese funktionen standard C-Funktionen in der avr-lib C?
Ist es sowas wie das bubble-sort oder quick-sort, selection-sort,
welches man in den Grundlagen lernt?
imax schrieb:> Sind diese funktionen standard C-Funktionen in der avr-lib C?
Ja, sind Standard-Funktionen.
> Ist es sowas wie das bubble-sort oder quick-sort, selection-sort,> welches man in den Grundlagen lernt?
qsort - Quick Sort
bsearch - Binäres Suchen
Einfach mal in das File stdlib.h reinschauen.
Karl heinz Buchegger schrieb:> qsort - Quick Sort> bsearch - Binäres Suchen>> Einfach mal in das File stdlib.h reinschauen.
Kann man machen. Aber:
Never, ever optimize prematurley!
Bei 25 Strings, die da verglichen werden müssen, würde ich erst einmal
straightforward stumpf von vorne nach hinten linear suchen. Wenn es dann
später mal nachweislich zu langsam ist, dann lässt sich das immer noch
optimieren.
Oliver
Und wenn schon optimieren, dann über eine State-Machine, die den
Eingangsstring zeichenweise testet/abarbeitet. (Lexer)
So muss kein Buchstabe mehrfach angefast werden.
Sofern du nur statische Strings parsen musst, könntest du sie auch
hashen, und dann mit dem Hash hantieren. Anstatt strcmp() reicht also
eine Tabellensuche mit Vergleich auf den Integer deiner Wahl. Wenn du
die Lookup-Tabelle vorsortierst, ist die Suche auch bei 100+ Elementen
sehr effizient.
Hallo,
sortieren ist wohl auf dem MC nicht notwendig, ausser man kann Befehle
und Funktionen nachträglich übertragen.Aber sortieren von Zeigern auf
die Strings würde recht fix gehen, solange es kein bogo-sort ist ;-)
Binaere Suche sind nur ein paar Zeilen Code.bsearch ist also kompakt und
schnell.
Bei 25 Strings mus man ja nur maximal 5 Stringvergleiche durchführen,
bis man den richtigen gefunden oder als nicht vorhanden ausschliessen
kann.
Meine Vorschlag mit einer zusätzlichen ID macht bei langsamer
Übertragung wenig Sinn.
3 Byte extra brauchen bei 115200 Baud und bei 16 Mhz Takt minimal 4200
oder so Takte, da ist eine binäre Suche längst fertig.
Eine gut Hash-Funktion muss man erst mal finden, bei solchen Daten?
"request:ssid:all\n","request:ssid:1\n"
Wenn der Puffer vor dem beschreiben mit der Kommandozeichenkette immer
genullt ist,
kann man ja Zeichen 0,6,13 addieren && 31 und schauen, ob da keine
Doppelten sind.
Aber jedesmal beim Hinzufügen eines neuen Kommandos testen, was da für
ein hashwert raus kommt, nä, zuviel Aufwand und Fehler trächtig.
Ich würde eine alle n Kommandos sortiert als nullterminierte Strings
hintereinander pappen und anschliessend eine konstante Tabelle mit
Zeigern auf die einzelnen Strings.
http://www.mikrocontroller.net/articles/AVR-GCC-Tutorial#Array_aus_Strings_im_Flash-Speicher
In der Tabelle kann man dann binär suchen und hat als Ergbenis eine
Zahl von 0.. n-1
Dann ist switch optimal einzusetzen.
Hallo nochmal!
Der Code von PeDa gefällt mir schon!
Dort kommt immer das Wort 'code' drin vor. Dort wirft mir der GCC fehler
raus:
typedef struct{
u8 code *name; <---- FEHLER
u8 (code *func)(void);
}comm_struct;
../functions.c:33: error: expected ':', ',', ';', '}' or '__attribute__'
before '*' token
ich kenne auch nur sowas:
u8 *name;
aber kein:
u8 code *name; //hier weiß mein GCC nicht, was er anlegen soll :(
Wo ist mein Fehler?
Anfänger schrieb:> Dort kommt immer das Wort 'code' drin vor.
Das ist irgendeine Spezialität des verwendeten Compilers, die wohl dafür
sorgt, dass die beschriebenen Daten ins Flash kommen.
Wirf fürs erste das 'code' einfach raus.
Also ist es quasi das Schlüsselwort, der Typqualifikator einer Variable.
Sinn macht es auf jeden Fall, die Tabelle in den Flash zu speichern.
Für den GCC mit der AVR-LibC nehme ich dann PROGMEM als Attribut.
Hallo PeDa!(und ihr Anderen)
Ich habe mir den code mal genau zu Gemüte geführt. Mir ist allerdings
nicht klar, was genau die folgende Zeile macht.
if( ((comm_tab[i].name[j] ^ buf[j]) & 0x5F) == 0 )
Verglichen wird hier ein einzelnes Zeichen des commands in der Tabelle
mit den eingehenden daten. Wozu ist denn das exor? 0x5F ist die Bitfolge
0101.1111. Wozu ist diese Maske notwendig?
Ich kann zwar die einzelnen bytes binär verknüpfen, via (x^y)&z wie es
oben steht, aber der Sinn ist mir nicht ganz klar.
Vllt. hilfst du (oder jmd, der sich im stande fühlt) etwas auf die
Sprünge.
Den code möchte ich nutzen, aber nicht stupide per copy paste ans laufen
bringen, sondern verstehen!
Danke für kurze Hilfe!
Timo P schrieb:> Wozu ist denn das exor?
EXOR ist der Vergleich, es ergibt 0 bei Gleichheit.
> 0x5F ist die Bitfolge> 0101.1111. Wozu ist diese Maske notwendig?
Damit ist Groß-/Kleinschreibung egal.
Peter
Das ist ja schlau!
Habe gerade in der ASCII-Tabelle nachgeschaut!
Die Null, die wir erzwingen, ist die 32, die dann vom ASCII-Code
abgezogen wird. (ist genau der Unterschied zwischen einem großen und dem
gleichen Buchstaben in klein)
Darauf soll man erst mal kommen.....
THX!