Intrusive vs non-intrusive
-
set ist super-langsam für so eine Anwendung. Jede Node in einem Set (=jeder eingefügte Wert) verursacht üblicherweise eine eigene Speicher-Allokation. D.h. 1x new + 1x delete (zum Aufräumen) pro untersuchtem Objekt. Aua.
Ein sebstgestrickter Hashtable, in dem du Zeiger auf die Objekte speicherst, wäre vermutlich um einiges schneller.
-
Also ich mag immer noch vector + Flag. Irgendwie sehe ich in den anderen Methoden bloß mehr Rechenaufwand mit dem einzigen Vorteil, dass man kein Flag in den Daten hat. Wenn einen das stört, dann lagert man es eben aus. Ein weiterer vector<bool> oder vector<short> nebenbei, in dem nur während des Algorithmus gespeichert wird, welche Objekte schon dran waren (ich nehme mal an, die Objekte sind irgendwie identifizierbar mit einer Nummer, Speicheradresse, o.Ä.. Auf die Weise müllt man sich auch nicht den Datenbereich der Objekte mit einem Flag voll, das man nur einmal braucht, das erhöht Lokalität.
Wenn ich mal meine Erfahrung beim Optimieren von Algorithmen zum besten geben darf:
Ich zitiere erst einmal:
http://users.ece.utexas.edu/~adnan/pike.html
Das gilt heute mehr denn je. Sogar für große N, sofern man nicht in eine ganz andere Komplexitätsklasse fällt. Komplizierte Algorithmen haben oft Cache-Misses und mehr Branches, das will man heutzutage vermeiden wie die Pest. Lieber zigmal unnötig rechnen, anstatt einem Algorithmus, der einem etwas unnötiges abnimmt und dafür aber aus CPU-technischen Gründen öfter Warten muss.
Hier liegt so ein Fall vor. Ein bis zwei vectoren sind optimale Datenstrukturen für den Cache, man hat leider in jedem Durchlauf einen unvorhersehbare Verzweigung.
Führt man ein set ein, dann hat man viele unvorhersehbare Verzweigungen und bettelt um fragmentierten Speicher. Und man ändert die Komplexitätsklasse nicht und auch noch nicht einmal die Anzahl der Elemente, die angeguckt wird. Also nichts gewonnen, sehr viel verloren.
Hash-Map geht in eine ähnliche Richtung, aber bei weitem nicht so schlimm wie ein set. Trotzdem wird der Algorithmus komplizierter gemacht, ohne überhaupt irgendetwas zu gewinnen. Wir haben immer noch exakt die gleiche Zahl Elemente und immer noch mindestens eine Verzweigung, mit der Hash-Map eher mehr.Man müsste sich schon etwas ausdenken, das das Problem ganz anders löst. Irgendwas cleveres, an das keiner gedacht hat. Vielleicht kann man schon vorher Vorarbeit leisten. Oder die Daten ganz anders organisieren. Zuwenig Informationen dafür.
-
Ja, ein
std::vector<std::tuple<bool, T>>oder ein extra bool vector wär theoretisch eine ziemlich ideale Lösung. Das Problem ist nur, dass der ganze Zweck dessen, was der Threadersteller hier zu tun versucht, darin besteht, eben genau nicht alle Objekte zu durchlaufen...
-
Tuste mit dem set und der hash-map aber auch. Dafür langsamer.
Wenn man das Problem mit dem mehrfach Durchlaufen lösen könnte, dann wäre das eine der angesprochenen cleveren Lösungen.
(Und trotzdem vermutlich langsamer, wenn er nicht sehr viele doppelte hat)
-
Ja eben, wenn die doppelten ein Problem sind, dann heißt das doch eigentlich, dass die Zellen zu klein sind. Man könnte auch einfach alle sichtbaren Zellen durchlaufen, alle Objekte davon in einen vector schubsen und dann die Duplikate entfernen.
-
SeppJ schrieb:
Also ich mag immer noch vector + Flag. Irgendwie sehe ich in den anderen Methoden bloß mehr Rechenaufwand mit dem einzigen Vorteil, dass man kein Flag in den Daten hat. Wenn einen das stört, dann lagert man es eben aus. Ein weiterer vector<bool> oder vector<short> nebenbei, in dem nur während des Algorithmus gespeichert wird, welche Objekte schon dran waren (ich nehme mal an, die Objekte sind irgendwie identifizierbar mit einer Nummer, Speicheradresse, o.Ä.. Auf die Weise müllt man sich auch nicht den Datenbereich der Objekte mit einem Flag voll, das man nur einmal braucht, das erhöht Lokalität.
Und wie findest du in dem Vektor das jeweils richtige Flag?
Man braucht sowas übrigens ständig bei Graphenproblemen. Da hat das dann auch nichts mehr mit Geschwindigkeit zu tun, denn wenn du dich beim Markieren der besuchten Knoten vertust, rennst du ungebremst in Endlosschleifen und andere unerfreuliche Dinge.
-
Bashar schrieb:
Und wie findest du in dem Vektor das jeweils richtige Flag?
SeppJ schrieb:
ich nehme mal an, die Objekte sind irgendwie identifizierbar mit einer Nummer, Speicheradresse, o.Ä.
Falls doch nicht, dann eben der Hashtable. Aber bitte kein Set in einer kritischen Schleife füllen.
-
SeppJ schrieb:
Bashar schrieb:
Und wie findest du in dem Vektor das jeweils richtige Flag?
SeppJ schrieb:
ich nehme mal an, die Objekte sind irgendwie identifizierbar mit einer Nummer, Speicheradresse, o.Ä.
Falls doch nicht, dann eben der Hashtable. Aber bitte kein Set in einer kritischen Schleife füllen.
OK, angenommen, die Objekte sind durch ihre Adresse identifizierbar. Wie gehts weiter? Die Adresse als Index zu nehmen ist ja wohl ein Witz.
-
dot schrieb:
Man könnte auch einfach alle sichtbaren Zellen durchlaufen, alle Objekte davon in einen vector schubsen und dann die Duplikate entfernen.
Ehrlich gesagt denk ich, dass das nicht nur sehr einfach sondern auch nicht besonders ineffizient wäre...
-
Bashar schrieb:
OK, angenommen, die Objekte sind durch ihre Adresse identifizierbar. Wie gehts weiter? Die Adresse als Index zu nehmen ist ja wohl ein Witz.
Daraus kann man dann einen Index ausrechnen, wenn die Objekte hintereinander im Speicher liegen.
Und zur Not hat man immer noch die Möglichkeit der Markierung, wie im Originalbeitrag. Wenn die Objekte sowieso nicht hintereinander im Speicher liegen, hat man nämlich ohnehin keine Lokalität, dann ist es egal, wenn die Objekte etwas Ballast haben.
-
SeppJ schrieb:
Bashar schrieb:
OK, angenommen, die Objekte sind durch ihre Adresse identifizierbar. Wie gehts weiter? Die Adresse als Index zu nehmen ist ja wohl ein Witz.
Daraus kann man dann einen Index ausrechnen, wenn die Objekte hintereinander im Speicher liegen.
Anders gesagt, du gehst von parallelen Vektoren aus, einen Vektor mit den Objekten und einen mit den Flags. Kann man machen, wenn die Objekte so vorliegen.
Und zur Not hat man immer noch die Möglichkeit der Markierung, wie im Originalbeitrag.
Ja natürlich, es gibt die beiden im Originalbeitrag angesprochenen Methoden. Du hast aber eine dritte vorgeschlagen, und nur über die spreche ich.
