Probleme mit Template-Bibliothek

[Christian Kruse]

Hallo zusammen,

Ich arbeite gerade fuer einen Kunden an einer Template-Bibliothek (in C). Dazu
haette ich zwei Fragen.

Die erste betrifft das Setzen von Template-Variablen. Ich benutze im Moment
einen Array von Variablen, um alle Variablen zu speichern. Per Insertion Sort
suche ich fuer jede neue Variable den richtigen Platz und fuege sie dort ein.
In der getter-Methode fuer Variablen benutze ich dann ein Binary Search um die
gewuenschte Variable zu suchen.
Das Problem ist jetzt aber, dass ich zum einfuegen neuer Variablen am Anfang
oder am Ende des Arrays ja den kompletten Array umkopieren muss (mache ich mit
memcpy()). Das ist natuerlich, je nach Groesse des Arrays, sehr langsam. Dem
wuerde eine verkettete (ob einfach oder doppelt, ist in dem Fall egal) Liste ja
ziemlich abhelfen. Allerdings weiss ich zum Suchen in Listen keinen sinnvollen
Such-Algorithmus ausser einer linearen Suche, die ueber alle Elemente iteriert.
Meine Frage waere nun, ob es fuer verkettete Listen nicht einen sinnvolleren
Such-Algorithmus gibt, auf den ich nur noch nicht gekommen bin und ob es sich
lohnen wuerde, eine Liste statt eines Arrays zu verwenden.

Die zweite Frage ist etwas komplexer. Ich verwende einen von einem Lex
generierten Tokenizer und speichere den potentiellen Programmablauf in einem
Array von Baeumen. Beispielsweise saehe dieses Programm

<$ set $var = "abc".$var."blahr"; print $var; $>

in einem Syntaxbaum so aus:

Knoten 1 (Typ SET)       ->          Knoten 2 (Typ PRINT)
   /      \                                 /
 $var1  Operator .                        $var
          /   \        "abc" Operator .
              /   \             $var "blahr"

Ich speichere also im Grunde einen Array von Ausdruecken, wobei jeder Ausdruck
aus einem Baum besteht (mit minimal einem Knoten). Ich habe allerdings ein
Problem damit, ifs abzubilden. Kann mich vielleicht mal jemand darauf stossen,
wie ein Baum fuer ein if aussehen kann? Es soll nur if-else-endif moeglich
sein, kein elsif oder so. Das muesste ueber else if abgebildet werden.

Krein Problem bereitet es mir, den true- oder den false-Zweig abzubilden. Das
waeren einfach wieder Arrays von Baeumen, einfach eine Ebene tiefer als das if
selber. Probleme bereitet mir nur das Darstellen des Ausdrucks, der die
Bedingung praesentiert, also z. B. $var == 1 in if($var == 1).

Gruesse,
 CK

[Sven Rautenberg]

Moin, CK!

Das Problem ist jetzt aber, dass ich zum einfuegen neuer Variablen am Anfang
oder am Ende des Arrays ja den kompletten Array umkopieren muss (mache ich mit
memcpy()). Das ist natuerlich, je nach Groesse des Arrays, sehr langsam. Dem
wuerde eine verkettete (ob einfach oder doppelt, ist in dem Fall egal) Liste ja
ziemlich abhelfen. Allerdings weiss ich zum Suchen in Listen keinen sinnvollen
Such-Algorithmus ausser einer linearen Suche, die ueber alle Elemente iteriert.
Meine Frage waere nun, ob es fuer verkettete Listen nicht einen sinnvolleren
Such-Algorithmus gibt, auf den ich nur noch nicht gekommen bin und ob es sich
lohnen wuerde, eine Liste statt eines Arrays zu verwenden.

Wenn du sowohl schnelle Einfügezeiten als auch schnelle Suchzeiten haben willst, dann bieten sich Bäume als Speicherstruktur an.

Ich bin zwar nie in die totalen Tiefen von (wie hießen die Dinger noch gleich?) B-Bäumen abgestiegen, aber simple eher unbalancierte binäre Bäume hab' ich schon (in Turbo Pascal) programmiert. Das schöne an solchen Bäumen: Sie sortieren sich praktisch von selbst nach genau einem Sortierkriterium, und sie sind sehr schnell durchsuchbar.

Listen wären vermutlich die schlechteste aller Varianten.

Du kannst natürlich auch das Array dadurch beschleunigen, dass du im Array selbst nur lauter Zeiger speicherst und so die Datenmenge reduzierst, die bei Erweiterungen zu kopieren ist. Oder du implementierst gleich einen ordentlichen Hash (der seinerseits wohl nichts anderes als eine komfortable Anwendung von Bäumen ist und nur in Hochsprachen direkt zur Verfügung steht - das ist eben das Schicksal von Bitschubser-Sprachen ;) ).

Deine andere Frage habe ich nicht so ganz verstanden, aber vermutlich kann sowas rauskommen:

Typisches IF-Konstrukt:
IF (ausdruck) THEN (then-anweisung) ELSE (else-anweisung)

Ein "passender" Baum:
  Knoten 3 (Typ IF)
     /         \   (ausdruck)  THEN
              /   \  (then-anweisung) (else-anweisung)

Hm, wenn selbst ich auf eine Idee komme - warum dann nicht du? Wenn dein System (und davon gehe ich aus) gut ist, dann hast du gewisse Knoten-Typen, die du bei diesem IF-Baum andocken kannst. Also z.B. einen Knoten-Typ für Ausdrücke, und eben einen für Anweisungen. Verschachtelte IFs werden möglich, indem du als then- oder else-Anweisung wieder einen IF-Knoten andockst.

- Sven Rautenberg

[Christian Kruse]

Hallo Sven,

Wenn du sowohl schnelle Einfügezeiten als auch schnelle Suchzeiten haben
willst, dann bieten sich Bäume als Speicherstruktur an.

*seufz* Danke.
Da sieht man mal wieder, wie Betriebsblindheit sich auswirken kann... vor
allem, weil sortierte Felder im Grunde nichts anderes als Baeume sind (darauf
basiert Binary Search ja), ich also im Grunde diese Idee schon verfolgt habe
und nur eine andere Darstellungsform waehlen muss...

Listen wären vermutlich die schlechteste aller Varianten.

Das habe ich mir auch gedacht. Deshalb habe ich davon ja auch Abstand
genommen :)

Du kannst natürlich auch das Array dadurch beschleunigen, dass du im Array
selbst nur lauter Zeiger speicherst und so die Datenmenge reduzierst, die
bei Erweiterungen zu kopieren ist.

Das tue ich ja eh schon.

Oder du implementierst gleich einen ordentlichen Hash

Ich kann keinen Hash implementieren :) Dazu fehlen mir Grundlagen.

(der seinerseits wohl
nichts anderes als eine komfortable Anwendung von Bäumen ist

Nee, die Theorie von Hashes ist eine andere: aus dem Key wird eine Nummer
erstellt, die den nummerischen Index des Elementes darstellt. Zumindest habe
ich das mal so gelesen.

und nur in
Hochsprachen direkt zur Verfügung steht - das ist eben das Schicksal von
Bitschubser-Sprachen ;) ).

Das stimmt wahrscheinlich wohl :/

Typisches IF-Konstrukt:
IF (ausdruck) THEN (then-anweisung) ELSE (else-anweisung)

Ein "passender" Baum:
  Knoten 3 (Typ IF)
     /         \   (ausdruck)  THEN
              /   \ (then-anweisung) (else-anweisung)

Wie gesagt, es ging mir nicht um die Darstellung des True- bzw. False-Zweiges,
sondern um die Darstellung von 'ausdruck'. Wie stelle ich AND, OR, XOR dar,
wie werte ich die komplette Bedingung aus?

Hm, wenn selbst ich auf eine Idee komme - warum dann nicht du?

Nun, so einfach ist das nicht. Ich wuesste einfach nicht, wie ich 'ausdruck'
implementieren sollte.

Gruesse,
 CK

[Sven Rautenberg]

Hallo Sven,

Wenn du sowohl schnelle Einfügezeiten als auch schnelle Suchzeiten haben
willst, dann bieten sich Bäume als Speicherstruktur an.

*seufz* Danke.
Da sieht man mal wieder, wie Betriebsblindheit sich auswirken kann... vor
allem, weil sortierte Felder im Grunde nichts anderes als Baeume sind (darauf
basiert Binary Search ja), ich also im Grunde diese Idee schon verfolgt habe
und nur eine andere Darstellungsform waehlen muss...

Tja, im Bretter vom Kopf abreißen bin ich ganz groß - bei anderen. ;)

Typisches IF-Konstrukt:
IF (ausdruck) THEN (then-anweisung) ELSE (else-anweisung)

Ein "passender" Baum:
  Knoten 3 (Typ IF)
     /         \   (ausdruck)  THEN
              /   \ (then-anweisung) (else-anweisung)

Wie gesagt, es ging mir nicht um die Darstellung des True- bzw. False-Zweiges,
sondern um die Darstellung von 'ausdruck'. Wie stelle ich AND, OR, XOR dar,
wie werte ich die komplette Bedingung aus?

Du brauchst (und hast hoffentlich schon) einen Knoten-Typ zum Rechnen. Wie sonst sollte dein Beispiel SET sonst gehen?

Ein ganz altes Beispiel in Turbo-Pascal für einen Funktionsplotter (um beliebige Funktionen wie z.B. f(x)=x^2+sin(x/3)+e^x aufgrund Usereingabe zu plotten) hat mal ein heftiges Baumkonstrukt mit varianten Records gebastelt - je nach Funktion. Und der Ausdruck wurde dann geparst und als Baum aufgebaut, wodurch dann gleich die Berechnungsvorschrift entstand: Erst den einen Teilbaum berechnen, dann den anderen Teilbaum berechnen, und dann die Berechnungsvorschrift des aktuellen Knotens auf beide Subergebnisse anwenden.

Die Formel von oben würde sich ungefähr so "aufbäumen":

f(x)
                   |
         -------(  +  )-------
         |                   |
   ---(  ^  )---       ---(  +  )---
   |           |       |           |
  (x)         (2)  --(sin)--   --( ^ )--
                   |           |       |
               --( / )--      (e)     (x)
               |       |
              (x)     (3)

Die Klammern zeigen immer ein Knotenelement - entweder eine Konstante, eine Variable, oder eine Rechenoperation. Gemäß irgendwelcher Gesetzmäßigkeiten arbeiten mathematische Funktionen in der Regel mit maximal zwei Operanden (alles andere läßt sich als Verkettung von jeweils zwei Operationen darstellen). Das zu Evaluieren funktioniert, wie oben dargestellt.

Es ist jetzt "nur noch" deine Aufgabe, die Knoten entsprechend zu behandeln und z.B. Knotentypen und Knotenauswertelogik für AND, OR, XOR, ==, !=, <, > etc. herzustellen.

Ist doch "ganz einfach"[tm]. ;)

- Sven Rautenberg

[Christian Kruse]

Huhu Sven,

Typisches IF-Konstrukt:
IF (ausdruck) THEN (then-anweisung) ELSE (else-anweisung)

Ein "passender" Baum:
  Knoten 3 (Typ IF)
     /         \   (ausdruck)  THEN
              /   \ (then-anweisung) (else-anweisung)

Wie gesagt, es ging mir nicht um die Darstellung des True- bzw.
False-Zweiges, sondern um die Darstellung von 'ausdruck'. Wie stelle ich
AND, OR, XOR dar, wie werte ich die komplette Bedingung aus?

Du brauchst (und hast hoffentlich schon) einen Knoten-Typ zum Rechnen.

Nunja, "rechnen" ist so ein Wort. Ich habe Operatoren, die etwas machen :)
Was, das weiss die Engine eigentlich gar nicht, sondern nur der Operator
selber.

[... beispiel fuer Funktionsplotter ...]

Es ist jetzt "nur noch" deine Aufgabe, die Knoten entsprechend zu behandeln
und z.B. Knotentypen und Knotenauswertelogik für AND, OR, XOR, ==, !=, <, >
etc. herzustellen.

Dann zeichne mir doch mal so einen Baum auf. Das ist naemlich gar nicht so
einfach, wie bei einer Funktion. Mal ein Beispiel:

if($var == 5 AND $var1 < 3 OR $var2 == 3)

Gut. Fangen wir mal an. Der erste Teilbaum ist ja recht einfach:

==
   / \   5  $var

So. Und wo wird jetzt das AND eingefuegt?

Hm, obwohl... mir faellt da gerade etwas ein... wie waere es mit so:

AND
   /           \   ==           OR
 / \        /       \ 5  $var    <         ==
         /    \     /   \        $var1   3  $var2  3

So muesste es eigentlich gehen... jetzt nur noch umsetzen *g*

Ist doch "ganz einfach"[tm]. ;)

Ja, nur nicht, wenn man kaum (ca. 1h) geschlafen hat und schon seit Tagen daran
sitzt :( Diese Baum-Strukturen sind mir neu, sowas habe ich vorher noch nie
gemacht -- lediglich einmal Daniela ueber die Schulter geschaut.

Gruesse,
 CK

[Sven Rautenberg]

Moin, CK!

Hm, obwohl... mir faellt da gerade etwas ein... wie waere es mit so:

AND
   /           \   ==           OR
/ \        /       \ 5  $var    <         ==
         /    \     /   \        $var1   3  $var2  3

So muesste es eigentlich gehen... jetzt nur noch umsetzen *g*

Genau so würde ich das auch sehen und machen. Und dieser Ausdruck hat dann ein Ergebnis, welches zu wahr oder falsch evaluiert und entsprechend die IF-Bestandteile aktiviert.

Ist doch "ganz einfach"[tm]. ;)

Ja, nur nicht, wenn man kaum (ca. 1h) geschlafen hat und schon seit Tagen daran
sitzt :(

Mit anderen Worten: Du bist "etwas müde"[tm].

Diese Baum-Strukturen sind mir neu, sowas habe ich vorher noch nie
gemacht -- lediglich einmal Daniela ueber die Schulter geschaut.

Aber du scheinst das Prinzip gerade verstanden zu haben. :)

Hey, ich hab' schätzungsweise zwei oder drei Jahre immer um das Kapitel "Zeiger-Datenstrukturen" im Turbo-Pascal-Buch drumrumgelesen (und es teilweise auch durchgelesen), ohne was verstanden zu haben - bis irgendwann der Durchblick kam (naja, ist aber auch schon gut 10 Jahre her, damals in der Schule...). Man kann tolle Sachen mit Zeigern machen und sich im Prinzip komplett von den starren mehrdimensionalen Arrays lösen, wenn man beispielsweise Spielfelder generieren will. Dinge wie Wurmlöcher und andere krasse Ideen sind so leicht möglich - für ein Templatesystem aber wahrscheinlich eher unnötig. ;)

- Sven Rautenberg

[Christian Kruse]

Taegelchen Sven,

Genau so würde ich das auch sehen und machen. Und dieser Ausdruck hat dann
ein Ergebnis, welches zu wahr oder falsch evaluiert und entsprechend die
IF-Bestandteile aktiviert.

Richtig.

Mit anderen Worten: Du bist "etwas müde"[tm].

Koennte man so ausdruecken :)

Diese Baum-Strukturen sind mir neu, sowas habe ich vorher noch nie
gemacht -- lediglich einmal Daniela ueber die Schulter geschaut.

Aber du scheinst das Prinzip gerade verstanden zu haben. :)

Naja, das Prinzip der Syntax-Baeume hatte ich vorher ja auch verstanden, sonst
haette ich den Ansatz fuer 'normale' Anweisungen ja nicht machen koennen. Die
Denkblockade lag bei mir woanders: ich habe den Fehler gemacht, AND, OR und
XOR nicht als Operatoren zu sehen, sondern als etwas aehnliches wie das ';':
die AND-, OR- und XOR-Teile habe ich als eigene Ausdruecke gesehen und nicht
als Teilausdruecke.

Ein sehr genialer Ansatz :) Macht das evaluieren schoen einfach.

Hey, ich hab' schätzungsweise zwei oder drei Jahre immer um das Kapitel
"Zeiger-Datenstrukturen" im Turbo-Pascal-Buch drumrumgelesen (und es
teilweise auch durchgelesen), ohne was verstanden zu haben

Ja, bis ich Baeume verstanden hatte, hat es auch eine Zeit bei mir gedauert...
keine zwei oder drei Jahre, aber mit Sicherheit eines :) 'klick' hatt es in
einer Informatik-Stunde gemacht, als wir binary search besprochen haben.

• bis irgendwann der Durchblick kam (naja, ist aber auch schon gut 10 Jahre
  her, damals in der Schule...).

Jups, in der 9 haben wir das gemacht.

Man kann tolle Sachen mit Zeigern machen und sich im Prinzip komplett von
den starren mehrdimensionalen Arrays lösen, wenn man beispielsweise
Spielfelder generieren will.

Jups :)
Deshalb finde ich es auch idiotisch, immer mehr davon weg zu gehen, Zeiger in
einer Sprache zu implementieren.

Dinge wie Wurmlöcher und andere krasse Ideen sind so leicht möglich

Na gut, damit habe ich dann noch nix getan ;)

• für ein Templatesystem aber wahrscheinlich eher unnötig. ;)

Wahrscheinlich, ja *g*

Mein naechstens grosses Projekt wird dann 'DK-Script', eine Huldigung an
Michael, der ein PASCAL mit Hashes und Regular Expressions moechte *gg*

Herjemine, Compiler- und Interpreterbau ist ein verdammt interessantes Thema.

Gruesse,
 CK

[Christoph Zurnieden]

Hallo,

Ich arbeite gerade fuer einen Kunden an einer Template-Bibliothek (in C).

Ach, Jung, mach Dir doch nicht selber das Leben so schwer, nimm 'was Fertiges:

Einfach mal das Erste, was einem bei Freshmeat zu dem Thema unter die Finger gerät ist diese hier z.B.:
http://libredblack.sourceforge.net
Ist mit Sicherheit nicht die beste Lösung (habe es mir aber nicht angeschaut) aber es ist eine. Und es scheint eine ganze Menge zu geben, es dürfte sich also bestimmt auch ein unter BSD Lizenz finden. (Das Beispiel oben ist allerdings auch schon unter der LGPL, macht im kommerziellem Umfeld also keine Probleme)

Gut, Selberbauen macht natürlich mehr Freude, aber wenn der Termin drückt ...
Deadline ist doch bestimmt wieder "gestern", oder? ;-\

so short

Christoph Zurnieden

[Christian Kruse]

Hoi Christoph,

Ich arbeite gerade fuer einen Kunden an einer Template-Bibliothek (in C).

Ach, Jung, mach Dir doch nicht selber das Leben so schwer, nimm 'was
Fertiges:

Es *gibt* keine fertige vernuenftige C-Template-Bibliothek. Ausserdem muss ich
eine kommerzielle Version davon ja auch verkaufen koennen, ich hab Hunger :)

Einfach mal das Erste, was einem bei Freshmeat zu dem Thema unter die Finger
gerät ist diese hier z.B.:
http://libredblack.sourceforge.net
Ist mit Sicherheit nicht die beste Lösung (habe es mir aber nicht angeschaut)
aber es ist eine.

Oh, fuer Baeume hab ich schon eine Abstraktion geschrieben. Ich hab keine Lust,
den ganzen Mist immer wieder zu machen :) Aber die Syntax-Baeume werde ich
damit nicht behandeln koennen.

Deadline ist doch bestimmt wieder "gestern", oder? ;-\

Natuerlich. Was denkst du denn? :)

Nein, diese Template-Lib ist auch ein kleines Hobby von mir, wenn sie fertig
ist werde ich eine Nicht-kommerzielle Version davon natuerlich als OpenSource
freigeben. Dass ich sie jetzt hier im Job brauche, treibt nur die Entwicklung
vorran.

Gruesse,
 CK

[Christoph Zurnieden]

Hallo,

Ich arbeite gerade fuer einen Kunden an einer Template-Bibliothek (in C).

Ach, Jung, mach Dir doch nicht selber das Leben so schwer, nimm 'was
Fertiges:

Es *gibt* keine fertige vernuenftige C-Template-Bibliothek.

Das stimmt, deshalb meinte ich ja auch nur die verschiedenen fertigen und stabilen Implementationen der diversen B-Tree Methoden.

Ausserdem muss ich
eine kommerzielle Version davon ja auch verkaufen koennen, ich hab Hunger :)

Ja, hättest Du 'mal 'was "Anständiges" gelernt! ;-)

Einfach mal das Erste, was einem bei Freshmeat zu dem Thema unter die Finger
gerät ist diese hier z.B.:
http://libredblack.sourceforge.net
Ist mit Sicherheit nicht die beste Lösung (habe es mir aber nicht angeschaut)
aber es ist eine.

Oh, fuer Baeume hab ich schon eine Abstraktion geschrieben. Ich hab keine Lust,
den ganzen Mist immer wieder zu machen :) Aber die Syntax-Baeume werde ich
damit nicht behandeln koennen.

Das war jetzt nur eine Bibliothek, es gibt jede Menge und auch verschiedene.

Ich habe mir jetzt den Code ein wenig angeschaut. Ist zwar relativ einfach gehalten, aber das ist erstens nichts Schlechtes und zum Zweiten ließe es sich darum ganz gut anpassen.
Aber ich hatte auch mal 'was in der Hand gehabt, das würde Dir genau passen, nur wo ...
Verdammt, wenn man sich auch nicht alles Interessante _sofort_ bookmarked :-(

Deadline ist doch bestimmt wieder "gestern", oder? ;-\

Natuerlich. Was denkst du denn? :)

Nun, hätte auch "Vorgestern" sein können, ist auch sehr beliebt bei den Herren mit dem buntem Stoffstreifen um das untere Ende des Hohlkörpers >;->

Nein, diese Template-Lib ist auch ein kleines Hobby von mir, wenn sie fertig
ist werde ich eine Nicht-kommerzielle Version davon natuerlich als OpenSource
freigeben. Dass ich sie jetzt hier im Job brauche, treibt nur die Entwicklung
vorran.

Na, dann freu' ich mich schon mal darauf!

so short

Christoph Zurnieden