Der Titel mag anfangs etwas komisch klingen, beschreibt aber vom Prinzip her ziemlich genau das, was ich suche. Bzw versuche zu finden
Ich versuche mir ein Konzept zu überlegen, mit dessen Hilfe ich mehrere (viele) Objekte speichern kann und sie effizient ansprechen (und suchen) kann.
Dabei soll folgendes gelten:
Ein Element hat immer zwei "Grundeigenschaften":
Das ist zum einen der "Startwert" und zum anderen die "Reichweite"
Beide Werte sind natürlich voneinander unabhängig.
Nun möchte ich diese "Liste" (ich nenne es mal so) durchsuchen, und zwar hab ich einen Startwert und eine Reichweite gegeben.
Finden möchte ich dadurch alle Elemente, die, ausgehend von ihrem Startwert unter Berücksichtigung ihrer eigenen Reichweite im Bereich liegen, den ich als "Suchfeld" angegeben habe.
Das ganze mal etwas grafisch dargestellt:
Die Elemente:
..|............|...................................................... Element 1
...........|...................................................|...... Element 2
.|.................................................................|.. Element 3
...................................|..|............................... Element 4
Die Suchparameter:
....................................|..............|.................. Suche 1
..........|...........|............................................... Suche 2
....................................................................|| Suche 3
Suche 1 müsste in diesem Beispiel dann die Elemente 2,3 und 4 zurückgeben.
Suche 2 würde 1,2 und 3 als Rückgabe haben.
Suche 3 würde kein Element zurückgeben.
Eine einfache (direkte) Implementierung von so einem Konzept ist ja kein Problem. Ich überprüfe einfach alle Elemente der Reihe nach, ob sie irgendwie in den Suchbereich fallen.
Das ist aber blöd, wenn ich dann z.B. 200.000 Elemente habe und einen sehr kleinen Suchbereich (in den vllcht 20 Elemente fallen), dann dauert meine Suche ganz schön lange.
Klar, man könnte das Verfahren von oben optimieren und nur die Elemente überprüfen, deren Startwert kleiner ist als Startwert + Reichweite des Suchfeldes.
Das würde im Mittel wohl eine Halbierung der zu überprüfenden Elemente nach sich ziehen.
Das reicht aber nicht (100.000 sind immer noch sehr viele)
Deshalb versuche ich nun, die Elemente in einer Datenstruktur möglichst so anzuordnen, dass eine Suche in möglichst schneller Zeit durchgeführt werden kann.
Dabei spielen der Aufwand für das Einfügen und das Entfernen von Elementen sowie der Speicherplatzverbrauch erstmal keine Rolle.
Nur die Laufzeit ist interessant.
Ideen dazu habe ich natürlich schon. Eine "Standardisierung" der Startwerte in Verbindung mit den Reichweiten (die beide Werte sozusagen zu einem zusammenfasst) wäre wohl gut.
Dann könnte man das über eine "normale" Suche lösen.
Ich dachte auch schon an den Einsatz eines Min-Max-Octtrees, weiß aber nicht, ob mir das weiterhelfen könnte.
Habt ihr dazu irgendwelche Ideen?
