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

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

windschief

Du HAST keine Zeiger drin

*lach* aber ich will

wenn ich sowas habe:

typedef std::deque<foo*> foo_container;

habe ich dann welceh?

unskilled

dein c++ - code zeigt mal wieder, dass du kein c++ kannst - oder du hast ausversehen 100 fehler reingemacht... ><
in c++ progrmmiert man nicht mittels try and error - und wenn du schon in nem forum postest, könnte man ja wenigsten davon ausgehen, dass du zumindest ein ganz klein wenig eigeninitiative zeigst...
du nimmst hier jedes mal wieder fremden code und änderst ihn dann so lang um, bis du so viele fehler drin hast, dass man nicht mal mehr erraten kann, was jetzt ausversehen war und was du vll doch schon weist und nur vergessen hast, zu ändern...
also gib dir jz mal ein wenig mühe, sonst wird hier bald gar keiner mehr lust haben, was zu erklären...

bb

edit: hast du mal nen swap spezialisiert und zählen lassen, wie oft es aufgerufen wird und kannst du uns mal sagen, wie lang dein gesamtes programm ungefährt rechnet - etc....
das sind alles angaben, ohne die es total sinnlos ist, optimieren zu wollen - wie schon öfter gesagt, kann man nur mit nem profiler sinnvoll optimieren...

windschief

dein c++ - code zeigt mal wieder, dass du kein c++ kannst - oder du hast ausversehen 100 fehler reingemacht... ><

von beidem wahrscheinlich etwas..

wo habe ich denn schon wieder fehler reingemacht?
hier:

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??
  ..;
}

oder

typedef std::deque<foo*> foo_container;

ich wollte jetzt ausprobieren und messen, wieviel unterschied es macht objekte oder einfach nur deren adressen zu speichern. Wenn es keinen macht, ist es auch gut ausgetestet zu haben und definitiv zu wissen!

Dabei habe ich jetzt aber das Problem das ich nicht weiß, wie ich das Objekt dahinter löschen kann bzw. ich dachte was ich eben gepostet habe wäre richtig.
Danach machen ich natürlich noch Auswertungen mit gprof.

Was genau meinst du mit swap spezialisiert und zählen lassen?
Ich habe eine Funktion für die sortierung der Objekte, soll ich da einen Zähler einbauen und schauen wie oft er aufgerufen wird um die Liste zu sortieren?

Ich mache gerne noch ganz viele Angaben bzgl Zeit usw. Nur wollte ich erstmal diese Sache mit den Adressen probieren..

drakon

unskilled schrieb:

also gib dir jz mal ein wenig mühe, sonst wird hier bald gar keiner mehr lust haben, was zu erklären...

Schon passiert..

Ohne Selbstinitiative zu sehen habe ich keine Lust zu helfen.. n8

windschief

Schon passiert..

Ohne Selbstinitiative zu sehen habe ich keine Lust zu helfen.. n8

hmmm.. Ich verstehe nicht ganz warum ihr denkt, ich mache nichts bzw denke nicht nach..

ihr habt doch gesagt: ohne new kein delete.
Daraufhin habe ich das struct in eine klasse umgewandelt und mit new erstellt.
also new und delete..
welche selbstinitative wollt ihr denn genau??
Wie gesagt ich wollte das jetzt austesten und danach weiter optimieren..

unskilled

class foo{
};

int main()
{
  to_add = new foo(); //1. was ist to_add? allem anschein nach ein Zeiger
  foo_container.push_back(&to_add); //wieso also die adresse eines zeigers?
  foo* ptr = foo_container[0]; //besser: foo_container.front() - nicht alle container haben einen op[]
  foo_container.pop_front();
  delete *ptr;
  ..;
}

das hier wird aber zu 90% langsamer sein als foo_container<foo>
das wurde hier aber auch schon mal geschrieben...

"Was genau meinst du mit swap spezialisiert und zählen lassen?"
boar...

struct xyz
{
  explicit xyz(int a) : a(a) /*b, c, d, e, f*/ {}

  void swap(xyz& other)
  {
    using std::swap;
    swap(a, other.a);
    swap(b, other.b);
    swap(c, other.c);
    swap(d, other.d);
    swap(e, other.e);
  }

  int get_a() const
  {
    return a;
  }
private:
  int a, b;
  double c, d;

  std::vector<float> e;
};

bool operator< (const xyz& lhs, const xyz& rhs)
{ //...
  return lhs.get_a() < rhs.get_a();
}

void std::swap(xyz& lhs, xyz& rhs)
{
  lhs.swap(rhs);
}

swap ist also jetzt spezialisiert...

int main()
{
  std::vector<xyz> bla;

  bla.push_back(xyz(6));
  bla.push_back(xyz(4));
  bla.push_back(xyz(5));
  bla.push_back(xyz(7));
  bla.push_back(xyz(3));
  bla.push_back(xyz(1));
  bla.push_back(xyz(2));

  std::sort(bla.begin(), bla.end());
}

so würden wir also sortieren...
wenn wir jetzt noch wissen wollen, wie oft getauscht wurde, lassen wir also in der swap-funktion einen zähler mitlaufen...
das geht eigtl relativ einfach, in dem wir dort ne static-variable reinmachen und die bei jedem fkt-aufruf incrementieren - nur wollen wir die noch ausgeben, also nehmen wir einfach ne globale variable:

unsigned int swap_counter = 0;

void std::swap(xyz& lhs, xyz& rhs)
{
  ++swap_counter;
  lhs.swap(rhs);
}

int main()
{
/*...*/

  std::sort(bla.begin(), bla.end());

  std::cout << swap_counter << std::endl;
}

ihr habt doch gesagt: ohne new kein delete.
Daraufhin habe ich das struct in eine klasse umgewandelt und mit new erstellt.
also new und delete..

kannst du lesen?
ich hab jetzt schon mindestens zweimal geschrieben, dass es _keinen_ unterschied zwischen struct und class gibt(zumindest keinen, der hier eine rolle spielen würde - also war es mal wieder völlig sinnlos das "struct in eine klasse umzuwandeln" - das zeigt mir recht deutlich, wie du die hier gegebenen antworten liest)

bb

PS: Mit deinen Pointern hast du 3 Zuweisungen, das richtige swap hat vermutlich irgendetwas um die 21Zuweisungen - du sparst also pro swap 18Takte(kannst ja mal googlen, wie viel Takte dein Prozessor pro Sekunde schafft - dann wirst du auch sehen, dass sich das ganze nicht lohnt... :P) - dafür verlierst du aber beim erstellen und zerstören des Objekts deutlich mehr Takte - außerdem wird die Lesbarkeit nicht unbedingt erhöht werden und nicht zu letzt verzichtest du (völlig grundlos) auf RAII... Ich könnte noch ne ganze Weile weitermachen, Nachteile aufzuzählen, aber das sollte selbst dir inzwischen reichen, um es einzusehen...

windschief

Vielen dank für deine ausführliche Antwort. Ich baue den swap counter mit ein und berichte wieviele swap's, viele Objekte insgesamt und wie lange!

Möchte nur noch ganz kurz meine wirren Gedanken dazu erklären...

ich hab jetzt schon mindestens zweimal geschrieben, dass es _keinen_ unterschied zwischen struct und class gibt(zumindest keinen, der hier eine rolle spielen würde - also war es mal wieder völlig sinnlos das "struct in eine klasse umzuwandeln" - das zeigt mir recht deutlich, wie du die hier gegebenen antworten liest)

Ich habe ein struct gemacht (ohne new) also auch kein delete.
(hatte auch schon vorher geschaut, ob man ein struct mit new erstellen kann, nichts gefunden, ausprobiert (soviel zu try and error *g*) hat auch nicht geklappt. Ihr habt gesagt struct = (meistens) class. class geht mit new. Juhuu!
struct in class auch wenns das selbe ist, aber ich habe ein new was ich mit delete löschen kann.

Okay ich sehe ein, dass war mist das letzte code beispiel...
es war wohl eindeutig zu spät und ich zu verzweifelt!!

class foo{ /* ... */
};

int main()
{
    deque<foo*> foo_container;
    foo* ptrFoo = NULL;
    // hinzufügen
    ptrFoo = new foo();
    foo_container.push_back(ptrFoo);
    // löschen
    delete *foo_container.begin(); // objekt löschen
    foo_container.pop_front(); //zeiger im container löschen

}

Aber das könnte doch jetzt wirklich stimmen oder? (falls nicht bitte nicht verzweifeln) Aber ihr meint das ist nicht wirklich effizient.. hmm.. okay... dann mache ich mal an den swap-counter. Bin gespannt!

Nexus

windschief schrieb:

int main()
{
    deque<foo*> foo_container;
    foo* ptrFoo = NULL;
    // hinzufügen
    ptrFoo = new foo();
    foo_container.push_back(ptrFoo);
    // löschen
    delete *foo_container.begin(); // objekt löschen
    foo_container.pop_front(); //zeiger im container löschen
  
}
Aber das könnte doch jetzt wirklich stimmen oder? (falls nicht bitte nicht verzweifeln) Aber ihr meint das ist nicht wirklich effizient.. hmm.. okay...

Nein, so ist das garantiert nicht effizient. Einfügen und löschen kann der Container selber, und wahrscheinlich schneller. Zeigen bringen dir höchstens was, wenn du die Elemente oft gar nicht löschst, sondern gleich wieder ans andere Ende des Containers einfügst.

Wenn du nur diese Operationen benötigst, kann sich der FIFO-Container std::queue auszahlen:

std::queue<foo*> foo_container;

// ein paar Mal einfügen
foo_container.push(new foo());
// ...

// vorderstes Element nehmen und über Löschung entscheiden
foo* ptr = foo_container.front();
foo_container.pop();

if (/* Bedingung, die häufig eintrifft */)
{
    // Element verändern und am Ende wieder einfügen
    modify_foo(ptr);
    foo_container.push(ptr);
}
else
{
    delete ptr;
}

Je nachdem kann es auch sein, dass eine andere Datenstruktur (z.B. Ringpuffer) dafür besser geeignet wäre.

asc

windschief schrieb:

Ich habe ein struct gemacht (ohne new) also auch kein delete.

1. Es gibt keinen Unterschied zwischen struct und class in C++ (Außer: Standardzugriffsmodifikator public bei struct, private bei class - und ggf. noch PODs).

Sowohl das eine als auch andere kann man auf dem Stack oder Heap (mittels new/delete) verwalten.

2. Es kann zwar Unterschiede in der Performance zwischen einem Container mit Objekten oder einen mit Zeigern geben, aber zu wessen Gunsten kann man nicht verallgemeinern (Das hat unter anderem mit der Objektkomplexität, dem verwendeten Container und der Häufigkeit und Art der Zugriffe zu tun).

3. "Premature Optimization Is The Root Of All Evil"
a) Schreibe dein Programm.
b) Ist es schnell genug? Wenn ja, gehe zu g)
c) Verwende ein Programm das dir sagt WAS zu langsam ist, in 95% der Fälle wirst du dich sonst auf die falschen Bereiche stürzen (Und selbst ein solches Programm kann sich nicht in alle Anwender hinein versetzen).
d) Schau dir die Stelle an, die am schwerwiegendsten ist.
e) Wenn eine Optimierung möglich ist, optimiere diese Stelle, sonst mache bei der nächsten Stelle weiter.
f) Teste es anschließend und kehre anschließend zu b) zurück.
g) Vorläufig fertig, wobei es sein kann das du später wieder optimieren musst (Verschiedene Anwender verwenden vielleicht andere Herangehensweisen / Schwerpunkte und stoßen dabei wieder auf neue Problemfälle).

Nicht selten ist ein sauber geschriebenes Programm, wo der Schwerpunkt auf Lesbarkeit und Wartbarkeit liegt, ohne Optimierungen schneller, als ein Programm wo der Programmierer meint alles von vorne herein Optimieren zu müssen.

Das liegt daran, das man in ersteren auch häufig durch die Lesbarkeit Fehler und unnötige Wiederholungen ausschließt und zudem ein Entwickler in der Regel nicht sicher sein kann, welcher Programmteil am Schluss wirklich der Flaschenhals ist.

In einem Projekt meinte der Chefentwickler auch, das die Container der Standardbibliothek so schlecht wären, und verlangte die Verwendung seiner auf kryptischen Code basierenden Bastelei (Die tatsächlich nicht mal annähernd so schnell war, keine Dokumentation besaß und zudem unschöne Seiteneffekte hatte [new/free ist nur eine dieser "Nettigkeiten" gewesen]).

Der Grund warum er meinte das seines schneller war, lag daran das er sich nicht mit den Containern auseinander gesetzt hatte (und diese auf die denkbar schlechteste Weise verwendet hatte - von für die Aufgabenstellung mal ungünstig gewählten Containern einmal abgesehen).

Ich gebe dir wirklich den Rat: Programmiere erstmal sauber, und kümmere dich erst anschließend um die Performance.

windschief

Vielen Dank für den Tip mit dem swap!!!!!!!!!!!!
okay hier eine kurze Zusammenfassung:

Problem mit ca. 5000 Objekten gleichzeitig gespeicht: list gegenüber vector 90% Zeitersparnis. deque gegen vector 99% Zeitersparnis.
Danke für den Tip auch nochmal!

Weitere Tests nur mit deque:
Problem getestet mit ca. 550000 Objekten gleichzeitig gespeichtert:
Ohne swap ca. 94 sec mit spezial-swap 70 sec, swaps ingesamt: 43247642.

Kann man sagen wieviele Objekte ca gleichzeit gespeichert werden können?
Beim der nächstgrößeren Problemklasse gab es bei 10000000 Objekte ein

terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc

. Ist der Speicher erschöpft?

Natürlich ist es auch zu überlegen, ob soviele Objekte überhaupt sinnvoll sind... aber ich wollte nachfragen ob das schon "zuviel" ist..

Also nochmal danke für den tipp mit der deque und dem swap!

Wenn du nur diese Operationen benötigst, kann sich der FIFO-Container std::queue auszahlen:

Ich muss zusätzlich noch sortieren, das geht mit einer queue nicht ohne weiteres oder?

unskilled

windschief schrieb:

Problem mit ca. 5000 Objekten gleichzeitig gespeicht: list gegenüber vector 90% Zeitersparnis. deque gegen vector 99% Zeitersparnis.

also nimm die deque

Kann man sagen wieviele Objekte ca gleichzeit gespeichert werden können?
Beim der nächstgrößeren Problemklasse gab es bei 10000000 Objekte ein
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
. Ist der Speicher erschöpft?

Naja - man kann nur eine obere Grenze angeben: foo_container_instanz.max_size() aber so viele wirst du wohl so gut wie nie erstellen können ;o)

Wenn du nur diese Operationen benötigst, kann sich der FIFO-Container std::queue auszahlen:

Ich muss zusätzlich noch sortieren, das geht mit einer queue nicht ohne weiteres oder?

oben steht doch schon, wie einfach das geht...
std::sort(deine_queue.begin(), deine_queue.end());

bb

Nexus

windschief schrieb:

Beim der nächstgrößeren Problemklasse gab es bei 10000000 Objekte ein
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
. Ist der Speicher erschöpft?

Wenn du von std::vector redest, dann konnte wahrscheinlich nur kein genügend grosser Speicherblock am Stück gefunden werden. Die Zahl 10000000 sagt uns lediglich, dass mindestens 10 MByte benötigt werden. Interessanter wäre der tatsächlich benötigte Speicher (natürlich nur ungefähr, von der Container- und Runtime-Implementierung mal abgesehen).

unskilled schrieb:

oben steht doch schon, wie einfach das geht...
std::sort(deine_queue.begin(), deine_queue.end());

Aber nicht bei einer std::queue , die bietet keinen Iteratorzugriff.

unskilled

Nexus schrieb:

unskilled schrieb:

oben steht doch schon, wie einfach das geht...
std::sort(deine_queue.begin(), deine_queue.end());

Aber nicht bei einer std::queue , die bietet keinen Iteratorzugriff.

Imho braucht std::sort nur random access iteratoren?!
Ja - ich war zu faul nachzulesen und/oder zu probieren^^

bb