spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Afaik reduziert der einsatz eines binären Suchbaums die Anzahl der Durchläufe von n auf lg(n) und sollte damit schnell genug sein. Viel schneller wirds nicht mehr.

Zitat von »"theNoob"«

Danke für die schnelle Antwort, werde mir gleich mal Informationen darüber beschaffen!

Könnte das Thema "Hashcode in Datenbanken" auch interessant sein, oder sind Suchbäume schneller ?

Wäre sicher auch eine Möglichkeit (mit Hash hab ich mich noch nicht ausgiebig beschäftigt) aber afaik muss dafür immer der exakte Name bekannt sein. Wenn nur der Anfang des Namens bekannt ist sollten Suchbäume die bessere Lösung sein (korrigiert mich wenn ich falsch liege)

Wie groß ist dein Datenbestand denn?

Wenn du nach einem Namen suchen willst, dann is eine Hashmap/table sicherlich eine gute Lösung. Natürlich haben auch Hashmaps/tables ihre Problemchen...

Suchen in einer C++ Map geht generell in logarithmischer Zeit ( O(log n) ) und ist (von der Komplexitätsklasse her) damit laufzeitoptimal. Vergleichsbasiertes Suchen geht nicht schneller als in log n ...

Zitat von »"dot"«

Vergleichsbasiertes Suchen geht nicht schneller als in log n ...

Gibt es denn nicht vergleichsbasiertes Suchen?

sry, vergiss was ich grad gesagt hab. das war natürlich kompletter käse. ich sollte nach 10h uni wohl besser nicht mehr über sowas schreiben...

(ersetzen wir "suchen" durch "sortieren" und "log n" durch "n log n" und dann is meine aussage richtig, aber hat mit der frage nix mehr zu tun)

Naja, std::map ist sicherlich shcon n ziemlich gutes Allroundwerkzeug.

Wenn es extrem wird, kannst du natürlich was eigenes, potentiell besseres schreiben. Ich würde erstmal mit z.B. Testdaten zu gucken, ob das schon reicht.
Es gibt auch eine hashmap in der STL, das wäre wohl auch ein Blick wert.

Dann könnte man natürlich noch sowas machen wie, wenn du z.b. weißt, die ersten 2 Zeichen sind auf jeden Fall Buchstaben ein Array mit 26^2 Elementen machen, oder sogar noch mehr, wo dann jeweils z.B. eine Map zu allen Namen die genau diese 2 Anfangsbuchstaben haben. Verbraucht natürlich bissle speicher, aber du hast in Konstanter Zeit Zugriff auf eine Map mit schonmal x Buchstaben weniger, das ist könnte sich durchaus lohnen.

Wikipedia ist da sehr hilfreich. Eine recht schöne Übersicht über mögliche Techniken und das wichtigste: Links auf verschiedene Algorithmen:
http://de.wikipedia.org/wiki/Suchverfahren