Probleme mit Template-Bibliothek

[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