Zeit in Millisekunden oder noch kleiner

ichbineinnoob

CStoll schrieb:

Wenn du so oft in den Listen suchen willst, solltest du eine Datenstruktur verwenden, in der das schneller geht, z.B. ein std::set<>.

PS: Außerdem solltest du für die Arbeit mit den Zeigern eigene Vergleichs-Funktionen bereitstellen, der Vergleich zwischen unabhängigen Zeigern (d.h. alles was nicht ins selbe Array reinzeigt) ist nämlich undefiniert.

Was ist ein std::set<> ? Ist das so etwas wie eine Hashtabelle? Ich dachte std::map<> wäre das bereits.

Die Zeiger habe ich gewählt um einfach nur die Adressen zu vergleichen. Zeigen 2 Zustands-Pointer auf die selbe Adresse, so sind diese gleich. Das geht doch schneller, oder?

Zustand a(1,2), b(1,2);
Zustand *z1 = findeZustand(a), *z2 = findeZustand(b); //  bekommen die selbe Adresse
if (z1==z2) cout << "Zustand gleich!" << endl;  // so meinte ich das

CStoll

set<> ist ein recht naher Verwandter von map<>, das keine Schlüssel-Wert-Paare verwaltet, sondern nur Schlüssel - da es genau wie die map als Binärbaum aufgebaut ist, bekommst du die Suche auch in logarithmischer Zeit hin.

Die Zeiger habe ich gewählt um einfach nur die Adressen zu vergleichen. Zeigen 2 Zustands-Pointer auf die selbe Adresse, so sind diese gleich. Das geht doch schneller, oder?

Gleichheit ist ja auch kein Problem. Aber die map<> verwendet eine größer-als-Relation, um die Elemente in eine Reihenfolge zu bringen und die ist laut Standard nicht garantiert bei unabhängig voneinander existierenden Zeigern.

volkard

ichbineinnoob schrieb:

Die Zeiger habe ich gewählt um einfach nur die Adressen zu vergleichen. Zeigen 2 Zustands-Pointer auf die selbe Adresse, so sind diese gleich. Das geht doch schneller, oder?
Zustand a(1,2), b(1,2);
Zustand *z1 = findeZustand(a), *z2 = findeZustand(b); //  bekommen die selbe Adresse
if (z1==z2) cout << "Zustand gleich!" << endl;  // so meinte ich das

Was bedeutet (1,2) beim Erzeugen eines Zustands?

SeppJ

ichbineinnoob schrieb:

Die Zeiger habe ich gewählt um einfach nur die Adressen zu vergleichen. Zeigen 2 Zustands-Pointer auf die selbe Adresse, so sind diese gleich. Das geht doch schneller, oder?

Sei dir da mal nicht so sicher. Du baust dir eine Indirektion ein, um was zu sparen? Den Vergleich zweier Zahlen? Und umständlicher wird der Code dadurch auch noch.

Die Zeiger habe ich genommen um Speicherplatz zu sparen.

Ich glaube dein Programm ist, das muss man einfach mal so sagen, ein Paradebeispiel für den Spruch "Premature optimization is the root of all evil". Anstatt dich gründlich mit den grundlegenden Datenstrukturen zu befassen und damit ein schönes, schnelles, leicht zu schreibendes und (voraussichtlich) auch schnelles Programm zu schreiben, hast du alles unnötig umständlich gemacht. Und die zugrunde liegenden Überlegungen sind noch nicht einmal richtig, was die Sache noch schlimmer macht.

brotbernd

Nochmal kurz die Zwischenfrage zum Vergleich von Adressen.

vector<Foo*> foos(/*...*/);
sort(foos.begin(), foos.end());
Foo* kandidat = /*...*/;
bool kandidatIstDabei = 
    binary_search(foos.begin(), foos.end(), kandidat);

Ist das tatsächlich undefiniert oder in irgendeiner Weise problematisch? Ich mach sowas nämlich auch gelegentlich. Ich möchte dabei auch keine Reihenfolge definieren, sondern die Adresse nur als Identität des Objekts verwenden.

SeppJ

brotbernd schrieb:

Ist das tatsächlich undefiniert oder in irgendeiner Weise problematisch? Ich mach sowas nämlich auch gelegentlich. Ich möchte dabei auch keine Reihenfolge definieren, sondern die Adresse nur als Identität des Objekts verwenden.

Wenn das der Vergleich ist, den du wünscht, dann ist das auch richtig. Die meisten Leute verstehen aber unter Gleichheit eben etwas anderes.

brotbernd

Mich hatte jetzt das hier etwas irritiert

CStoll schrieb:

PS: Außerdem solltest du für die Arbeit mit den Zeigern eigene Vergleichs-Funktionen bereitstellen, der Vergleich zwischen unabhängigen Zeigern (d.h. alles was nicht ins selbe Array reinzeigt) ist nämlich undefiniert.

SeppJ

brotbernd schrieb:

Mich hatte jetzt das hier etwas irritiert

CStoll schrieb:

PS: Außerdem solltest du für die Arbeit mit den Zeigern eigene Vergleichs-Funktionen bereitstellen, der Vergleich zwischen unabhängigen Zeigern (d.h. alles was nicht ins selbe Array reinzeigt) ist nämlich undefiniert.

Ahh, stimmt, da war ja was . Ja, das kann auf manchen Maschinen in die Hose gehen. Aber das ist so exotisch, dass ich da nicht mehr dran denke.
Die Standardbibliotheken machen solche Geschichten intern übrigens auch, das ist es moralisch gerechtfertigt das selber auch so zu machen. Ich sage mal, das ist so ein Fall, wo man die Portabilität wirklich zu weit treibt, wenn man auf so etwas noch achtet. Das ist wie anzunehmen, dass der Zeichensatz nicht ASCII kompatibel wäre oder das Byte nicht 8 Bit hätte. Klar, es ist nicht definiert, aber man muss schon ganz schön suchen für ein reales Gegenbeispiel.

Vielleicht noch interessant dazu ist diese uralte Diskussion:
http://groups.google.com/group/comp.std.c++/browse_thread/thread/604972347050fbd6/2c5509bf63bb3e7d?lnk=gst&q=pointer+less+set#2c5509bf63bb3e7d

ichbineinnoob

SeppJ schrieb:

Ich glaube dein Programm ist, das muss man einfach mal so sagen, ein Paradebeispiel für den Spruch "Premature optimization is the root of all evil". Anstatt dich gründlich mit den grundlegenden Datenstrukturen zu befassen und damit ein schönes, schnelles, leicht zu schreibendes und (voraussichtlich) auch schnelles Programm zu schreiben, hast du alles unnötig umständlich gemacht. Und die zugrunde liegenden Überlegungen sind noch nicht einmal richtig, was die Sache noch schlimmer macht.

Ich stehe unter Zeitdruck und habe leider keine Zeit mich gründlich mit den grundlegenden Datenstrukturen zu befassen (so gern ich das täte!). Ich muss in vorgegebener Zeit ein Lernalgorithmus programmieren. Welche Datenstrukturen ich benutze ist zweitrangig (aber scheinbar auch nicht unwichtig)...
Es mag sein, dass ich einiges versaut habe, aber die zugrunde liegenden Überlegungen sind nicht unbedingt falsch. Nur scheine ich einige Aspekte nicht bedacht zu haben. Ich wollte halt nicht nur auf die Geschwindigkeit achten, sondern auch auf den Speicherverbrauch (weswegen ich dachte Pointer wären sinnvoll) und dazu sollten die Daten auch persistent sein (was diese komische Speicherstruktur erklärt.

Nun ja, ich bin für jede Hilfe mordsmäßig dankbar! Also sag mir doch bitte nicht nur, dass ich falsch gedacht habe, sondern auch inwiefern. Danke!

ichbineinnoob

Um noch einmal mehr oder weniger auf das Thema zurück zu kommen.

Die Suche in der std::list ist schon bei nur 1.500 Objekten 240 mal langsamer als eine Einfügeaktion in der std::map. So krass ist hätte ich den Aufwand nicht erwartet.

Wenn ich die std::list in eine std::set ändere, dann funktioniert das Suchen sicher schneller. Aber ich müsste (nach meinen Überlegungen) auch die Pointer weg lassen, weil sich Hashtabellen ständig ändern. Ich müsste anstatt 3n Objekte + Pointer, n² abspeichern. Ich hoffe das ist nicht so schlimm.

CStoll

set/map verwenden keine Hash-Tabellen, sondern einen binären Suchbaum. Und sie garantieren beide, daß Iteratoren und Zeiger auf ihre Elemente gültig bleiben, solange du nicht das betroffene Element selber löschst.

Ein Problem könnte das set<> mit Default-Sortierung und deiner Such-Methode von dort oben ergeben - wenn du die Adressen vegleichst, wirst du das lokal angelegte Vergleichs-Objekt bestimmt nicht in der Sammlung finden.

(wenn du mit Hash-Tabellen arbeiten willst, gibt es in C++0x die unordered_set<> und Kollegen)

Ansonsten: Wie groß sind deine Zustände und Aktionen überhaupt? Wenn die nur aus zwei Zahlen bestehen, lohnt sich der Aufwand mit den Zeigern nicht wirklich.