String mit Liste vergleichen

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

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

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

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

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

Ich wuerd mit einem balanciertn Binaerbaum arbeiten.

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