Intrusive vs non-intrusive

Hallo,

sagen wir ich habe Objekte vom Typ Foo und einen Algorithmus, der auf Foos arbeitet. Der Algorithmus wird mehrfach auf das selbe Foo treffen und ich könnte den Algorithmus beschleunigen, wenn ich jedes Foo nur EINMAL bearbeiten würde. Dazu könnte ich in die Klasse Foo ein Flag einfügen (hasBeenVisited oder so), dann wüsste der Algo genau, ob das Foo schon abgearbeiet ist.
Ist natürlich auch unschön, da Foo (das eigentlich nichts mit dem Algo zu tun hat) Infos für den Algo mitschleppt.

Wäre das dennoch ok, wenn der Algo schneller läuft? Oder sollte ich eine Hilfsstruktur einrichten, die sich merkt, was schon bearbeitet wurde?

cooky451

Warum könnte der Algorithmus denn mehrmals auf das selbe Foo treffen? Hier würde ich als erstes ansetzen.

Ich denke nicht, dass ich das ändern kann.

Ich habe ein 2D Gitter (wie ein Schachbrett), in dem sich geometrische Objekte befinden. Jede Zelle hat eine Liste mit Zeigern auf die Objekte, die in der Zelle stehen. Ein Objekt kann auch mehrere Zellen berühren, dann wird es von mehreren Zellen referenziert.

Ich gehe jetzt durch alle Zellen und für jede Zelle durch alle referenzierten Objekte dieser Zelle und schaue, ob das Objekt sichtbar ist. Beispiel: Sagen wir wir haben Zelle 1 und 2 und Zelle 1 referenziert Objekte A und B und Zelle 2 referenziert Objekte B, C, D.
Ich starte bei Zelle 1:
+ Ermittle ob A sichtbar ist => wenn ja, kommt es in einen Vektor
+ Ermittle ob B sichtbar ist => wenn ja, in Liste
Gehe zu Zelle 2:
+ Jetzt treffe ich wieder auf B, aber seit Zelle 1 weiß ich ja bereits, dass es sichtbar und brauche es nicht noch mal testen.

Gäbe es da vielleicht eine gute STL Struktur, mit der man mehrfach Tests verhindern kann?

SeppJ

Kannst du nicht alle Objekte durchgehen und gucken, in welchen Zellen sie sind?

edit: Und eine Liste? Meinst du damit std::list? Wenn du nicht sehr spezielle Anforderungen hast, ist eine doppelt verkettete Liste eher ein akademischer Container, in der Realität aber viel zu langsam.

*Rewind*

Was er braucht, ist eher std::set (schnell bei der Suche und erlaubt keine Duplikate).

SeppJ schrieb:

Kannst du nicht alle Objekte durchgehen und gucken, in welchen Zellen sie sind?

Nein. Das Gitter ist recht groß und in einem Vorverfahren ermittle ich die potentiell sichtbaren Zellen. Nur DIESE bearbeite ich jetzt.

SeppJ schrieb:

edit: Und eine Liste? Meinst du damit std::list? Wenn du nicht sehr spezielle Anforderungen hast, ist eine doppelt verkettete Liste eher ein akademischer Container, in der Realität aber viel zu langsam.

Mit Liste meinte ich nur einen Container. Ich benutze einen vector.

Im Grunde habe ich ja wirklich nur diesen Fall:
Object* o = ...
if(o noch nicht behandelt)
...
Dachte schon an einen std::set, aber brachte mich auch nicht weiter...

Eisflamme

Wieso brachte es Dich nicht weiter? Wenn es um die Sicherung von bereits bearbeiteten Objekten geht, kannst Du Objekte in ein Set reinsetzen. War die Einfügeoperation erfolglos (= schon drin), so kannst Du Dir weiteres sparen.

Objekt * o = ...
if(!niceSet.insert(o).second)
// schon bearbeitet

Klingt doch super.

cooky451

@Eisflamme Das dürfte aber langsamer laufen, als ein einfaches bool als Membervariable.
@sooja Kannst du denn nicht die Sichbarkeit der Zellen selbst erfassen?

cooky451 schrieb:

@Eisflamme Das dürfte aber langsamer laufen, als ein einfaches bool als Membervariable.
@sooja Kannst du denn nicht die Sichbarkeit der Zellen selbst erfassen?

Richtig. NICHTS is so schnell wie ein Flag in den Objekten. Nur es ist halt konzeptionell nicht sooo schön.

Die ermittelten Zellen sind nur potentiell sichtbar. Einzelne Objekte können dennoch unsichtbar sein.

Habs jetzt so gemacht: Ich hau ALLE Objekte der Zellen in ein set<> und iteriere dann über das set.

dot

Ich vermute mal es geht darum, nur Objekte zu rendern, die sichtbar sind!? Warum gehst du alle Zellen durch? Wäre der Sinn von so einem Grid nicht eigentlich, dass man nur die Zellen anfasst, die sichtbar sind? Inwiefern werden doppelte Tests zu einem signifikanten Performancefaktor? Heißt das nicht vielleicht einfach, dass deine Zellen zu klein sind?

dot

sooja schrieb:

Habs jetzt so gemacht: Ich hau ALLE Objekte der Zellen in ein set<> und iteriere dann über das set.

Hört sich sinnvoll an

SeppJ

sooja schrieb:

Habs jetzt so gemacht: Ich hau ALLE Objekte der Zellen in ein set<> und iteriere dann über das set.

Das klingt aber viel langsamer, als die Objekte zu markieren und dafür einen vector zu haben. Ging es nur um Eleganz? Ich dachte, es ginge um Geschwindigkeit.

Was übrigens noch eine Überlegung wert ist: Brauchst du überhaupt den Zwischenschritt? Kannst du nicht gleich mit den Objekten machen, was du später mit den Objekten in deiner Liste machen würdest?

dot

SeppJ schrieb:

sooja schrieb:

Habs jetzt so gemacht: Ich hau ALLE Objekte der Zellen in ein set<> und iteriere dann über das set.

Das klingt aber viel langsamer, als die Objekte zu markieren und dafür einen vector zu haben. Ging es nur um Eleganz? Ich dachte, es ginge um Geschwindigkeit.?

stimmt, aber wenn es schnell genug is...

hustbaer

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.

SeppJ

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.

dot

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...

SeppJ

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)

dot

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.

Bashar

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.

SeppJ

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.