Schnelles set<foo*>

Hallo,

ich suche eine Datenstruktur, wo ich Pointer reinlegen und schnell anfragen kann, ob ein Pointer enthalten ist. Standard für sowas ist ein STL-Set, aber der Teil ist zeitkritisch und ich möchte fragen, ob Ihr eine schnellere Methode kennt. Vielleicht was mit Hashes oder eine sehr effiziente Set-Implementierung?

Benötigt wird nur Einfügen und Abfragen. Es gibt kein Größenlimit bei dem Problem, aber typischerweise erwarte ich 20 bis 50 Pointer im Set.

Danke / lg

Dravere

Muss denn das reinlegen auch schnell sein? Wenn nicht, dann würde ich einen std::vector<foo*> nehmen und diesen sortieren. Beim Abfragen einen std::binary_search darauf anwenden.

Grüssli

Und du hast jetzt gemessen, dass deine set-Implementierung bei lächerlichen 20 bis 50 Werten langsam ist? Dann würde ich mal eine Releaseversion bauen.

Dravere schrieb:

Muss denn das reinlegen auch schnell sein? Wenn nicht, dann würde ich einen std::vector<foo*> nehmen und diesen sortieren. Beim Abfragen einen std::binary_search darauf anwenden.

Grüssli

Vector - sort - Binärsuche ist eine gute Idee. Leider muß ich die Abfragen schon machen, während das Set noch aufgebaut wird. Es handelt sich um einen Breitensuche-Algorithmus, der wissen muß, wo er bereits war. In den besuchten Elementen (auf die die Pointer zeigen) soll das aus Platzgründen nicht hinterlegt werden.

lg

Wenn der Speicherverbrauch ein Problem ist, wieso verwendest du dann nicht eine iterative Tiefensuche?

manni66 schrieb:

Und du hast jetzt gemessen, dass deine set-Implementierung bei lächerlichen 20 bis 50 Werten langsam ist? Dann würde ich mal eine Releaseversion bauen.

Das Argument mit den 'lächerlichen 20 bis 50 Werten' ist falsch, denn durch die logarithmische Tiefe des Suchbaums ist es unerheblich, ob nun 50 Werte drinliegen oder 1000. ld(50)~6, ld(1000)~10, und daher hast Du bei 50 Werten noch immer 60 Prozent der Laufzeit, die Du mit 1000 Werten hättest. STL-Sets sind einfach und allgemein, das ist ein großer Vorteil. Aber Datenstrukturen 'von der Stange' sind nicht für jedes Problem optimal. Ich baue bis zu 10 Mio. solcher Sets auf.

lg

tressa schrieb:

Wenn der Speicherverbrauch ein Problem ist, wieso verwendest du dann nicht eine iterative Tiefensuche?

Das Problem ist nicht kreisfrei. Gesucht wird in einem Tetraedernetz, wobei von Nachbar zu Nachbar gesprungen wird.

lg

assert schrieb:

manni66 schrieb:

Und du hast jetzt gemessen, dass deine set-Implementierung bei lächerlichen 20 bis 50 Werten langsam ist? Dann würde ich mal eine Releaseversion bauen.

Das Argument mit den 'lächerlichen 20 bis 50 Werten' ist falsch, denn durch die logarithmische Tiefe des Suchbaums ist es unerheblich, ob nun 50 Werte drinliegen oder 1000. ld(50)~6, ld(1000)~10, und daher hast Du bei 50 Werten noch immer 60 Prozent der Laufzeit, die Du mit 1000 Werten hättest. STL-Sets sind einfach und allgemein, das ist ein großer Vorteil. Aber Datenstrukturen 'von der Stange' sind nicht für jedes Problem optimal. Ich baue bis zu 10 Mio. solcher Sets auf.

lg

Der Kern der Frage war: was erwartest du für eine Verbesserung mit einer anderen Datenstruktur? Auch eine binäres Suche in einem Vector verhält sich logarithmisch. Der wesentliche Vorteil dürfte sein, dass alle Werte im Prozessorcache liegen. Eine Hashtabelle muss aus dem Wert die Position in der Tabelle errechnen. Auch hier ist die Frage: ist der theoretische Laufzeitvorteil O(1) bei deinen kleinen Sets praktisch relevant?

manni66 schrieb:

Der Kern der Frage war: was erwartest du für eine Verbesserung mit einer anderen Datenstruktur? Auch eine binäres Suche in einem Vector verhält sich logarithmisch. Der wesentliche Vorteil dürfte sein, dass alle Werte im Prozessorcache liegen. Eine Hashtabelle muss aus dem Wert die Position in der Tabelle errechnen. Auch hier ist die Frage: ist der theoretische Laufzeitvorteil O(1) bei deinen kleinen Sets praktisch relevant?

Ein Vektor mit Binärsuche (wäre er für das Problem einsetzbar) hätte Vorteile beim Aufbau: Du kannst z.B. vector.reserve(n) sagen, um den Speicherplatz auf einmal zu reservieren. Beim STL-Set muß der Speicher Element für Element reserviert werden, und wenn das mit dem einfachen 'new' passiert, ist es langsam.

Mit einer Lösung ohne STL könnte man sich z.B. auch die Iteratoren ersparen, was nochmal einen kleinen Vorteil brächte.

lg

Vielleicht können wir mit Tricks arbeiten.
Deine Strukturen enthalten mit Sicherheit irgendwelche Zeiger und diese Zeiger sind hoffentlich immer gerade (muss eigentlich so sein).
Dann kann man das letzte Bit abtreten und als already_visited -Bit ansehen.
Wenn du auf den Zeiger zugreifen willst, führst du ein & mit 111..1110 durch.
Sollte das funktionieren, hast du einen 0(1)-Zugriff und weniger Speicherbedarf (du ersparst dir Millionen von std::vectors ).

brotbernd

Wieviel Prozent der Laufzeit des Algorithmus nimmt denn die Suche in einem std::set ein? Hast du das überhaupt schon gemessen?

brotbernd schrieb:

Wieviel Prozent der Laufzeit des Algorithmus nimmt denn die Suche in einem std::set ein? Hast du das überhaupt schon gemessen?

Ich optimiere sicher nach der 80:20-Regel, denn das Set kommt in jenem Teil vor, der die meiste Zeit benötigt. Wie groß der Anteil des Sets innerhalb dieses Teils ist, kann man meines Erachtens nur schätzen, da die Einzelschritte zu kurz für eine Messung sind. Solltest Du aber was in der Art

time(0)
while(something)
{
someCalc..

time.start()
set.find(x)
time.end()

someCalc..
}
cout<<"acc. time for just the set"<<time<<endl;

...kennen, das die Zeit so winziger Schritte messen kann, so bin ich sehr interessiert daran.

lg

tressa schrieb:

Vielleicht können wir mit Tricks arbeiten.
Deine Strukturen enthalten mit Sicherheit irgendwelche Zeiger und diese Zeiger sind hoffentlich immer gerade (muss eigentlich so sein).
Dann kann man das letzte Bit abtreten und als already_visited -Bit ansehen.
Wenn du auf den Zeiger zugreifen willst, führst du ein & mit 111..1110 durch.
Sollte das funktionieren, hast du einen 0(1)-Zugriff und weniger Speicherbedarf (du ersparst dir Millionen von std::vectors ).

Ein schmutziger Trick, aber genial! Das sollte eigentlich funktionieren. Danke!

lg

knivil

Es gibt Optimierungen, die weit vor der Implementation ansetzen. Breitensuche, Tetraedernetz ... in http://video.google.com/videoplay?docid=-4991530385753299192# wird kurz n-Shell vorgestellt. Anwendbar fuer planare Graphen, laesst sich aber auch auf dein Tetraedernetz erweitern. Wichtig ist, dass eine Kante kein Face* durchstoesst.

Knackpunkt: Du brauchst nicht alle besuchten Knoten speichern, sondern nur die (n-1)-shell und die n-shell hast du ja sowieso. Das ist deine "border" bei der Breitensuche.

Das hat mehrere Vorteile: Wenn man sich mit Breitensuche von dem Ausgangspunkt entfernt, dann wachst in deinem Fall die Anzahl der besuchten Knoten genauso wie das Volumen, also kubisch. Die n-shell waechst aber genau wie die Oberflaeche, also quadratisch. D.h. weniger Elemente zu durchsuchen. Im Video ist eine effiziente Implementierung fuer die Verwaltung von Mengen und dem Schnitt von Mengen vorausgesetzt.

Da ich aber nichts genaues zu deinem Problem weiss, kann ich auch nicht sagen, ob diese Idee viel bringt. Vielleicht kann man auch aehnlich wie beim Hypercude einefach eine geschickte Indizierung der Koten vornehmen oder andere hilfreiche Vorverarbeitungsschritte.

* keine Ahnung, wie das im deutschen heisst

assert schrieb:

...kennen, das die Zeit so winziger Schritte messen kann, so bin ich sehr interessiert daran.

Das sollte eigentlich jeder Profiler machen. Mit inline-Funktionen sollte man dabei aber aufpassen. Den Kontextwechsel erkennen nicht alle Profiler, so dass man den Übeltäter leicht an der falschen Stelle vermutet.

Paul Müller schrieb:

assert schrieb:

...kennen, das die Zeit so winziger Schritte messen kann, so bin ich sehr interessiert daran.

Das sollte eigentlich jeder Profiler machen. Mit inline-Funktionen sollte man dabei aber aufpassen. Den Kontextwechsel erkennen nicht alle Profiler, so dass man den Übeltäter leicht an der falschen Stelle vermutet.

Okay, man könnte das Set in eine kleine Funktion auslagern und das Inlining verbieten, um das zu messen. Da bin ich aber nie sicher, ob der Overhead für den Aufruf der Funktion nun dabei ist oder nicht. Jedenfalls scheint (mit gprof) die Summe der Laufzeiten nicht mit der realen Laufzeit überein zu stimmen.

Ich habe mittlerweile das STL-Set aus dem Algorithmus entfernt und testhalber etwas konstantes verwendet. Der Unterschied in der Laufzeit ist 15%.

lg

Das fällt doch bestimmt unter die 80-20-Grenze!

Schnelles set&lt;foo*&gt;

Schnelles set<foo*>