K
Karlos M.
Gast
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.
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.