größtmögliche Effizienz / vector? / boost

windschief

Das Object das ich speichere speichere besteht aus ca. 5 verschiedenen Werten und einem Array.

Ich habe das jetzt mit einem struct gelöst, bringt das Vorteile gegenüber einer eigenen Klasse? Bei ca. 50.000 Objekten, kann das einen Unterschied machen?

Habe momentan folgendes: (wenn ein ptr eines Obj der liste/enqueue/vector hinzugefügt wird)

struct foo{ // 5 Werte + Array
};
foo* ptrFoo = NULL;

// hinzufügen
foo tmp = {bla blub};
ptrFoo = &tmp;
foo_container.push_back(prtFoo);

Gehts noch besser/schlauer?

Thanks!!!!!

windschief

noch eine zusätzliche Frage:
wenn ich ptrFoo lösche, muss ich dann auch das struct löschen bzw. wie kann ich das machen?

Bei einer klasse geht es ja mit

delete *ptrFoo

...

unskilled

struct = class - macht also keinen unterschied

das hinzufügen an sich ist schon doof, weil es definitiv was anderes macht, als du denkst...

mach es doch einfach erst mal so, wie man es normalerweise machen würde... danach kannst du es noch immer kaputt-optimieren...

bb

windschief

Oh was meinst du jetzt..?
So wird es nicht funktionieren?
Ich dachte so kann ich meine Objekte als Pointer speichern... wie denn dann?
Hatte sie vorher als Kopie, wollte das jetzt ändern - bzw bin gerade dabei.
Muss ich sie als Kopien lassen?

struct foo{ // 5 Werte + Array
};
foo* ptrFoo = NULL;

// hinzufügen
foo tmp = {bla blub};
ptrFoo = &tmp;
foo_container.push_back(prtFoo);

unskilled

struct foo
{
 /*...*/
};

int main()
{
  foo to_add;
  foo_container.push_back(&to_add);

  ;
}

so würde das aussehen - aber da musst du halt vor allem gucken, dass du to_add nicht vorher irgendwie zerstörst...

bsp., wie man es _nciht_ macht:

void add(Tfoo_container &foo_container)
{
  foo to_add;
  foo_container.push_back(&to_add);
}

int main()
{
  Tfoo_container foo_container;
  add(foo_container);
}

bb

DocShoe

Überleg dir mal, wie lange das Objekt lebt, dessen Adresse du speicherst. Und was passiert beim Zugriff auf diese Adresse, wenn das Objekt nicht mehr existiert?

windschief

Ja das verstehe ich, dass in dem Beispiel das Objekt nicht mehr existiert, ich glaube das dürfte bei mir auch nicht passieren...

Ich habe gerade mal vector und deque gegeneinander getestet, der Unterschied ist ziemlich groß!!!! Vielen vielen Dank für den Tipp Ich probiere später nochmal std::list.

Aber wenn ich nur Zeiger anstatt Objekte speichere müßte das auch nochmal sehr viel ausmachen oder was denkt ihr?

Nexus

windschief schrieb:

Aber wenn ich nur Zeiger anstatt Objekte speichere müßte das auch nochmal sehr viel ausmachen oder was denkt ihr?

Was ausmachen? Was erhoffst du dir davon?

Blue-Tiger

windschief schrieb:

Ja das verstehe ich, dass in dem Beispiel das Objekt nicht mehr existiert, ich glaube das dürfte bei mir auch nicht passieren...

Ich habe gerade mal vector und deque gegeneinander getestet, der Unterschied ist ziemlich groß!!!! Vielen vielen Dank für den Tipp Ich probiere später nochmal std::list.

Aber wenn ich nur Zeiger anstatt Objekte speichere müßte das auch nochmal sehr viel ausmachen oder was denkt ihr?

Kommt drauf an. Wenn du die Zeiger jedesmal mit new erstellst und mit delete loescht, dann: ja, wird viel ausmachen, wird naemlich viel langsamer sein. Wenn du die Pointer vorher schon alle hast und erst am Ende loescht: ja, wird vermutlich schneller sein, als dauerndes hin/her kopieren.

windschief

hmm, ich glaube ich habe nicht ganz verstanden was du meinst..

ich habe folgendes:
ich erstelle ein objekt, das muss in eine "liste" hinten dran gespeichert werden (momentan deque), dann nehme ich ein neues objekt aus der "liste" von vorne (und lösche es aus der liste) verändere es und stecke es vielleicht wieder rein, bzw vielleicht auch mehrere veränderungen von dem objekt oder es wird ganz verworfen.

Jetzt ist meine Frage, ob es schneller gehen würde von der performance, wenn ich statt dem objekt selbst nur den pointer auf das objekt speichere.. das objekt muss ich ja so oder so erstellen.

Ich hoffe man kann ungefähr verstehen was der algo macht, wie gesagt, eine art A*..

Nexus

Das kommt wohl auf das Objekt an. Ist es eher klein, lohnen sich Zeiger wahrscheinlich nicht. Wenn du hingegen viel Kopieraufwand sparen kannst, wäre der Ansatz schon eine Überlegung wert. Jedoch müsstest du selbst Speicher verwalten, und das kann (abgesehen von der Mühseligkeit) z.B. bei std::deque wie erwähnt auch langsamer sein. Ich würde am besten weiterhin std::deque oder std::list benutzen, es sei denn, du hast wirklich ein Performance-Problem. In diesem Fall misst du am besten die Zeit in beiden Fällen. Aber nur aufgrund vager Vermutungen würde ich mir keine zusätzliche Mühe machen.

windschief

wie schon gesagt, mein objekt (struct) besteht aus 5 elementen und einem array/vector. Ist das eher klein?

Mein du mit Speicher selbst verwalten new and delete?

Hierzu habe ich noch meine Frage:

wie kann ich wenn ich den pointer habe das struct dahinter löschen?
bsp:

struct foo
{
 /*...*/
};

int main()
{
  foo to_add;
  foo_container.push_back(&to_add);
  foo* ptr = foo_container[0];
  foo_container.pop_front();
  delete *ptr; // so? funktioniert das auch bei einem struct?
  ..;
}

Die Performance ist wie gesagt alles, muss schneller als anderes Programm (anderer algo) sein und muss noch ein bisschen was rausholen...

Nexus

Bevor du dich an solche Optimierungen machst, solltest du vielleicht schon die Grundkonzepte der Sprache verstehen. Manuelle Speicherverwaltung und Zeiger gehören definitiv dazu. Hast du kein C++-Buch, in dem diese Dinge erklärt werden?

Könnte der Compiler deinen Code kompilieren, dann würdest du undefiniertes Verhalten hervorrufen, weil du delete auf ein Objekt anwendest, das nicht mit new angefordert wurde.

drakon

Was verstehst du unter löschen? - delete braucht man um dynamischen Speicher wieder frei zu geben. Mir schwebt was vor, dass du aber ganz was anderes willst. Wenn du das Element aus dem Container entfernst, dann wird das schon beseitigt. Keine Angst.

Und alleine aufrgrund von Code performance auslesen zu wollen ist völliger schwachsinn. Das ist in 99% der Fälle nutzlos. Benutz einen Profiler, wenn dei Programm fertig ist und dann bessere da nach, wo Engpässe sind. Das ist die korrekte Mehtode Code zu optimieren.

windschief

Könnte der Compiler deinen Code kompilieren, dann würdest du undefiniertes Verhalten hervorrufen, weil du delete auf ein Objekt anwendest, das nicht mit new angefordert wurde.

Genau das war ja meine Frage: Das struct wurde nicht mit new erstellt... wie lösche ich es nun.. ich habe in meiner liste nur die adressen, wenn ich jetzt nur den ersten knoten aus der liste lösche, lösche ich doch nur die adresse... wir kann ich das struct dahinter löschen? Od geht das automatisch?

Und alleine aufrgrund von Code performance auslesen zu wollen ist völliger schwachsinn. Das ist in 99% der Fälle nutzlos. Benutz einen Profiler, wenn dei Programm fertig ist und dann bessere da nach, wo Engpässe sind. Das ist die korrekte Mehtode Code zu optimieren.

Ich verstehe was du meinst. Nur mein Programm ist fertig und ich habe um Hilfe für Verbesserung gefragt, eine deque anstatt vector zu benutzen war schonmal sehr sehr nützlich.
Die Engstelle liegt darin das ich z.b. bis zu 40.000 Objekte speichern muss. Meine Frage ist nun wie ich die Operationen speichern, löschen, sortieren am effiziesten einsetzen kann.
Deshalb meine Frage auch am Anfang: lieber vorne oder hinten einfügen bzw löschen...

Ich benutze ja gerne einen Profiler, nur leider habe ich nicht verschiedene Methoden die aufgerufen werden, sondern eher eine große schleife mit vielen vielen Objekten..
Ich hoffe mein Problem ist ein wenig klarer geworden.

drakon

windschief schrieb:

Könnte der Compiler deinen Code kompilieren, dann würdest du undefiniertes Verhalten hervorrufen, weil du delete auf ein Objekt anwendest, das nicht mit new angefordert wurde.

Genau das war ja meine Frage: Das struct wurde nicht mit new erstellt... wie lösche ich es nun.. ich habe in meiner liste nur die adressen, wenn ich jetzt nur den ersten knoten aus der liste lösche, lösche ich doch nur die adresse... wir kann ich das struct dahinter löschen? Od geht das automatisch?

Wenn du foo in deinem Container speicherst, dann sind da auch foo Objekte drin. Nicht nur dessen Adressen. (intern wird da wahrscheinlich dynamisch Speicher angefordert und verwaltet, aber die Struktur hält prinzipiell nicht nur Zeiger). Und wenn du automatische Objekte speicherst, dann sind die nach dem entfernen auch wieder weg. (von Optimierungen mal abgesehen, dass der Container nicht wirklich Speicher zurückgibt, aber dein Objekt ist sicher korrekt zerstört). Anderst ist es, wenn du selbst Zeiger drin speicherst. Die werden natürlich nicht mit delete freigegeben, da du ja z.B auch ganzu normale Zeiger drin haben könntest.

Und alleine aufrgrund von Code performance auslesen zu wollen ist völliger schwachsinn. Das ist in 99% der Fälle nutzlos. Benutz einen Profiler, wenn dei Programm fertig ist und dann bessere da nach, wo Engpässe sind. Das ist die korrekte Mehtode Code zu optimieren.

Ich verstehe was du meinst. Nur mein Programm ist fertig und ich habe um Hilfe für Verbesserung gefragt, eine deque anstatt vector zu benutzen war schonmal sehr sehr nützlich.
Die Engstelle liegt darin das ich z.b. bis zu 40.000 Objekte speichern muss. Meine Frage ist nun wie ich die Operationen speichern, löschen, sortieren am effiziesten einsetzen kann.
Deshalb meine Frage auch am Anfang: lieber vorne oder hinten einfügen bzw löschen...

Ich benutze ja gerne einen Profiler, nur leider habe ich nicht verschiedene Methoden die aufgerufen werden, sondern eher eine große schleife mit vielen vielen Objekten..
Ich hoffe mein Problem ist ein wenig klarer geworden.

40'000 klingt nicht nach sehr viel. Hast du sicher mal im Release Mode gebuildet? - Das bringt dir enorm viel. 40'000 Objekte sind üblicherweise kein Problem.

windschief

Die werden natürlich nicht mit delete freigegeben, da du ja z.B auch ganzu normale Zeiger drin haben könntest.

das meinte ich =).
und wie kann ich jetzt mein struct das hinter der adresse ist löschen?

unskilled

windschief schrieb:

wie schon gesagt, mein objekt (struct) besteht aus 5 elementen und einem array/vector. Ist das eher klein?

Hier reicht ein spezialisiertes swap vollkommen aus - vector hat ein O(1) swap und der aufwand um 5 Elemente zu tauschen ist auch eher vernachlässigbar...
Falls dir das zu langsam ist, kannst du dein Objekt noch immer "pimpeln", wenn sie eine relativ lange lebensdauer haben würde sich das denke ich wieder lohnen - ansonsten eher weniger...

noch ein kurzer kommentar zu deinem quellcoden:

int main()
{
  foo to_add;
  foo_container.push_back(&to_add);
  foo* ptr = foo_container[0];
  foo_container.pop_front();
  delete *ptr; // BÄM!
  ..;
} //oder spätestens hier BÄM!

Wie bereits gesagt, gibt es keinen Unterschied zwischen class und struct (außer der default-access-aber der spielt hier keine rolle)...

bb

windschief

also sollte ich mein struct in eine class umwandeln, jedes objekt mit new erstellen und dann kann ich es auch mit delete löschen?

also so:

class foo{
};

int main()
{
  to_add = new foo();
  foo_container.push_back(&to_add);
  foo* ptr = foo_container[0];
  foo_container.pop_front();
  delete *ptr; // kein BÄM! mehr??
  ..;
}

also struct in class, damit ich das objekt hinter der adresse löschen kann?

drakon

windschief schrieb:

Die werden natürlich nicht mit delete freigegeben, da du ja z.B auch ganzu normale Zeiger drin haben könntest.

das meinte ich =).
und wie kann ich jetzt mein struct das hinter der adresse ist löschen?

Du HAST keine Zeiger drin (zumindest habe ich das hier bis jetzt nicht gesehen). Also brauchst du auch nichts freizugeben. Für das Element, was du entfernst wird der Destruktor aufgerufen und aus dem Container entfernt. Fertig.

/EDIT
NEIN! Wenn du Objekte vom Typ foo drin haben willst, dann speichere Objekte vom Typ foo dort drin! Ansonsten führst du den Container ad absurdum. (zu einem gewissen Teil).