effiziente Suchalgorithmen gesucht

Hallo,
ich suche einen gute Lösung für das Suchen von einem Schlüssel.

Also, ich will mir die Orte merken, an denen ich gewesen bin, damit ich nur ein einziges mal dort hin gelange. Diese Orte haben IDs. Eine schlechtere ID, die als eine Zahl gespeichert ist.
Eine zweite ID, bei denen mehrere ID-Teile in einem Vector gespeichert sind.

Da es sehr viele Schlüssel werden könnten und noch mehr Abfragen, ob ein Schlüssel bereits vorhanden ist, sollte ich ein möglichst schnellen Algorithmus einbauen.

Eigentlich würde ich gerne auf die Vector-ID zurückgreifen. In kleinen Szenarien geht zwar die einfache ID aber wenn man etwas macht, sollte es gescheit sein.

Aber ihr könnt mir dafür gerne auch Tipps geben, vielleicht implementiere ich erst die einfache ID und verbessere es dann später.

Hier meine Ansätze:
Für die feste ID (also eine Zahl):
Mir einen Binärensuchbaum bauen (oder gibt es bereits einen implementierten? fand keinen). Somit hab ich O(log(n)) fürs Suchen, wenn ich mich nicht irre. Natürlich muss ich aber auch das erstellen hinzuzählen.
Vielleicht gibts da was besseres. Außerdem kann ich nicht einschätzen, wie gut das fürn Speicherplatz ist wenn für jeden Schlüssel ein Objekt angelegt werden muss (aber Speicherplatz ist sekundär).

Bei den genauen IDs im Vektor:
Wieder ein Binärbaum, bei dem die Einträge statisch sind, das heißt nicht nachsortiert werden wie beim Binärensuchbaum. Es wird abwechselnd nach den verschiedenen Schlüsselteilen sortiert.
Das heißt auf Stufe eins mit dem 1. Schlüsselteil (größer rechts, kleiner links) Stufe 2 dann mit dem 2. Schlüsselteil, 3 mit dem 3. (und wenn der Schlüssel n Teile hat dann ab der Höhe n+1 wieder vom 1. Schlüssel ab).
Anders weiß ich grad nicht wie ich mehrere Schlüsselteile in den Griff kriegen soll, allerdings sind diese Bäume mit der Effizients auch nicht mit den Binärbäumen zu vergleichen. Die höhe kann sehr schnell ansteigen...

Würde mich sehr freuen wenn mir wer gute Tipps geben könnte.

padreigh

Über "Schnelligkeit" würde ich mir später Gedanken machen. Nimm eine std::map<int,DeineOrtsRepreasentationsObject> orte; das alle Orte enthält und überlass das Suchen des Schlüssels der orte.value(id); Wenn das irgendwann mal ein Bottleneck wird, optimiere. Ansonsten hilft dir http://stackoverflow.com/questions/471432/in-which-scenario-do-i-use-a-particular-stl-container bei der Wahl des Containers und google mit "c++ <algorithm>" für vorhandene Algos weiter ...

Danke für die Antwort.

Die Zeichnung muss ich mir merken, ist gut!!!

aber damit kann ich mein Hauptproblem, den mehrteiligen Schlüssel, nicht machen (außer ich mache mehrere Maps ineinander).

Würde mich freuen, wenn dafür noch wer Anregungen hat. Danke

Mach eine Klasse für eine Schlüssel. Wenn du für diese die richtigen Vergleichsoperatoren schreibst, kannst du die "Schlüsselklasse" als key für die map verwenden.

9999998 schrieb:

Mach eine Klasse für eine Schlüssel. Wenn du für diese die richtigen Vergleichsoperatoren schreibst, kannst du die "Schlüsselklasse" als key für die map verwenden.

*deine Schlüssel

~Sie können einen Beitrag nicht so schnell nach Ihrem letzten absenden, bitte warten Sie einen Augenblick.~

otze

Anonymus666 schrieb:

Danke für die Antwort.

Die Zeichnung muss ich mir merken, ist gut!!!

Sie vereinfacht viel zu stark. es kommt nicht drauf an, was du mit deinem Conainer alles können möchtest, sondern was du am Meisten tust. Die zweite Antwort in dem Thread ist viel besser: nimm vector, bis dir ein gutes Gegenargument einfällt.

9999998 schrieb:

Mach eine Klasse für eine Schlüssel. Wenn du für diese die richtigen Vergleichsoperatoren schreibst, kannst du die "Schlüsselklasse" als key für die map verwenden.

den Vorschlag versteh ich nicht ganz. kannst du bitte genauer erklären, danke

hustbaer

Ich würde da ne Hash-Map verwenden (boost:: bzw. std::unordered_map).
Kann man noch etwas schneller machen, indem man den Hashwert vorberechnet und mit dem Schlüssel mit abspeichert.

Tachyon

Schau Sie mal die Trie-Datenstruktur und deren Spezialisierungen (PATRIZIA/Radix-Tree) an. Da kommst Du in k-Vergleichen zum Ziel, wobei k nicht von der maximalen Anzahl der Schlüssel-/Werte-Paare abhängt, sondern von der maximalen Schlüssellänge.
Amortisiert hast Du also O(1) Komplexität. Ob das geht, hängt natürlich von Deinen Schlüsseln und deren Aufbau ab.