Binärbäume iterativ speichern

[alzaimar]

Zitat:

Zitat von new32

AVL-Bäume beruhen doch auf dem selben Prinzip.

Auch beim Einfügen wird ausgeglichen.

Zitat:

Zitat von new32

Aber mein Baum fasst auch mehr als 1 Mio. Einträge!

Gerade dann werden Skiplisten Hashmaps viel schneller als Bäume. Bei 1 Mio Einträgen geschätzte 1000 mal schneller (kann auch mehr sein).
Genauergesagt werden sie kaum langsamer, es ist egal, ob die Liste 1000 oder 100.000.000 Einträge umfasst.
Hier habe ich einen Performancevergleich geschrieben...
Verabschiede Dich also vom Irrglauben, Liste=lahm...

[new32]

:shock:

Nich schlecht, diese Liste!
Mal sehen, ob ich das noch ändere.

Zu dem Suchen in meinem Baum:
Da ich mit Zeichenketten arbeite und die (natürlich) in den tieferen Ebenen des Baumes immer änlicher werden und sich z.B. erst ab dem 30. Zeichen unterscheiden, speichere ich beim Erstellen immer die Position des Zeichens, an der der 1. Unterschied zum Vorgänger gefunden wird.
Dadurch vermeide ich, dass immer wieder die gleichen Anfänge verglichen werden müssen.
Beispiel: http://de.wikipedia.org/wiki/...
99% aller Seiten auf deisem Server fangen mit diesem Präfix an.


An der Stelle muss man sehen, ob sich die Skip-listen bewähren:
weil sich der Vorgänger ändert(andern kann), muss man da immer voll vergleichen.

Zu den Hash-Tabellen: da ich nicht weiß, wie groß des ding wird, habe ich mich für einen Baum entschieden.

[alzaimar]

Zitat:

Zitat von new32

Zu den Hash-Tabellen: da ich nicht weiß, wie groß des ding wird, habe ich mich für einen Baum entschieden.

Die von mir implementierte Hashmap wächst dynamisch mit. :zwinker:

Allerdings würde für deinen Fall ein DAWG bzw. Prefix-Trie noch besser sein. Das ist eine Struktur, die sich die von Dir beschriebene Redundanz (identische Stringanfänge) zu Nutze macht. Dadurch wird das Wörterbuch sehr kompakt und zweitens noch schneller. Ich meine, hier in der DP von Hagen (negaH) eine DAWG-Implementierung gefunden zu haben.

[new32]

da muss man mal ausprobieren, was besser ist.

Beide basieren ja auf einer Baumstruktur und beide Verfahren haben ihre Vor und Nachteile.

Allerdings wirds langsam Off-toppic.
Da sollte man besser einen ergenen Thread für auf machen.

Das iterative Speichern funktioniert ja bei beiden Ansätzen :wink:

[alzaimar]

Zitat:

Zitat von new32

da muss man mal ausprobieren, was besser ist.

Nee, muss man nicht.

Zitat:

Zitat von new32

Allerdings wirds langsam Off-toppic.

Stimmt.