Fragment C-Code geschickter gestalten

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 .....

1

enum COMMAND {

2

  A, B, C;

3

};

4

5

COMMAND getCommand(char* buffer) {

6

 if (strncmp(buffer, "request:ssid:all\n", 17 ) == 0 )  {

7

  return A;

8

 }

9

 if(strncmp(buffer, "request:ssid:1\n", 15 ) == 0 ) {

10

  return B;

11

 }

12

 if(strncmp((char*)buffer_, "config:end\n"), 11 == 0)  {

13

  return C;

14

 }

15

}

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:

1

#include <stdlib.h>

2

3

typedef unsigned char   u8;

4

5

#define comm_data       u8 idata

6

7

u8 remote();

8

u8 local();

9

u8 status();

10

11

12

typedef struct{

13

  u8 code *name;

14

  u8 (code *func)(void);

15

}comm_struct;

16

17

18

comm_struct code comm_tab[] = {                 // command table

19

        "REM", remote,

20

        "LOC", local,

21

        "STAT", status,

22

        "", NULL                                // end of table

23

};

24

25

26

u8 execute( comm_data *buf )                    // command interpreter

27

{

28

  u8 i, j;                                      // up to 256 commands

29

  for( i = 0;; ){

30

    for( j = 0;; ){

31

      if( comm_tab[i].name[j] != 0 ){

32

        if( ((comm_tab[i].name[j] ^ buf[j]) & 0x5F) == 0 ){

33

          j++;

34

          continue;                             // next character

35

        }

36

        i++;

37

        break;                                  // next command

38

      }

39

      if( j == 0 )

40

        return 255;                             // error: command not found

41

      return comm_tab[i].func();                // execute command

42

    }

43

  }

44

}

Peter

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.

Läubi .. schrieb:
> Warteschleife

An dir ist ein echter Pädagoge verloren gegangen :-)

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 :-)

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.

Mit vorberechneten Hashwerten geht wiederum dann auch ein switch.

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.

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.

code, idata sind die verschiedenen Speicherbereiche des 8051.
Laß sie einfach weg oder:

1

#define code

2

#define idata

Peter

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