Scala Passende Speicherstruktur gesucht

[Karlos M.]

Hallo,
ich setze im Moment aus interesse ein Programm in Scala um. Ich brauche nun für meine Applikation eine passende Datenstruktur.
Die Anforderungen sind:
- Oft Einfügen und Löschen
- Suchen von bestimmten Einträgen
- Finden von Nachbarn (also Nachbarn im Sinne von Wertigkeit. Bei der reihe 1, 5, 8, 11, 19 wären die Nachbarn von 8 -> 5 und 11)
- Performante Umsetzung bei sehr vielen Werten (im Bereich 1000 - 500000 Einträge im Moment)

Habe nun überlegt, dass für häufiges einfügen und löschen eine LinkedList sinnvoll wäre, da die Werte damit nicht verschoben werden müssen.
Dafür ist das Suchen nur in linearer Zeit möglich. Für die Nachbar-Suche ist die sortierte Reihenfolge sinnvoll. Dann benötigt das Einfügen bereits lineare Laufzeit.

Deshalb kam ich auf die Idee, es mit einem Baum zu machen. Binärer Suchbaum vielleicht. Oder ein B-Baum bei der Masse an Werten!?

Nun die Frage an euch:
Welche Datenstruktur würdet ihr empfehlen?
Gibt es eine Scala-Implementierung oder muss ich mir die Klassen selber schreiben (was auch kein Problem wäre, doch meist ist die eigene Implementierung langsamer wie optimierte, bereits geprüfte Klassen).


Danke für eure Hilfe.

 

[ThreadPool]

Ob 500k Objekte viel sind hängt davon ab wie groß eines der Objekte im Speicher ist. Nehmen wir an du möchtest nur 32-Bit ints verarbeiten dann sind 500k Objekte nicht wirklich sehr speicherhungrig.

Zu deinem eigentlichen Problem, du könntest es mit einem balancierten binären Suchbaum versuchen, balanciert, weil sich die obere Grenze der meisten Operationen dann bei O(log n) befindet. Des Weiteren hat ein binärer Suchbaum die Eigenschaft bei einer Inorder-Travesierung die Knoten in sortierter Reihenfolge zu verarbeiten. Diese Eigenschaft bleibt auch bei balancierten Binärbäumen erhalten.
Wenn du den unmittelbaren rechten und linken Nachbarn finden möchtest ist das eine Inorder-Travesierung. Das gibt dir eine Laufzeit von O(1) bis O(log n) je nach Position der Knoten im Baum, das O(log n) lässt sich weiter reduzieren wenn ein "Threaded Tree" [1][2] verwendet wird.
Ein Threaded Tree ist nichts weiter als ein binärer Baum dessen "null"-Kinder auf das rechte und linke Inorder-Element zeigen anstelle auf "null". Damit ist es möglich einen binären Baum in O(n) inorder zu travesieren was bedeutet das du jedes mal von einem bestimmten Knoten aus deine unmittelbaren Nachbarn in O(1) abfragen kannst und das ist ja das was du möchtest.

[1] Threaded binary tree - Wikipedia, the free encyclopedia
[2] The Art of Computer Programming 1. Fundamental Algorithms

 

[Karlos M.]

Hallo ThreadPool,
danke für deine Antwort.

Ja, ich habe auch schon bereits mit dem ausbalancierten Binärbaum angefangen. Da ich über Google keine Info fand, ob es diesen bei Scala gibt, gehe ich davon aus, dass dies nicht der Fall ist.

"Threaded Tree" ist aber was neues für mich. Werde mich damit mal intensiver beschäftigen.
Danke, dass du auch Quellen angegeben hast, das ist sehr hilfreich.

 

[TP@unterwegs]

Wobei ich den wikilink nicht si gut finde, im knuth steht es besser. Jedenfalls kannst du dich von der libavl inspirieren lassen. In der Dokumentation werden die Algorithmen näher erläutert. GNU libavl 2.0.2