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

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

windschief

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

genau deswegen meinte ich nicht ohne weiteres...

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

das war mit std::deque, wie bekomme ich den tatsächlich benötigten Speicher raus?

Nexus

unskilled schrieb:

Imho braucht std::sort nur random access iteratoren?!

Was heisst nur? Von den fünf Iteratorkategorien der Standardbibliothek stellt der Random-Access-Iterator die grössten Anforderungen.

Bei std::queue handelt es sich um einen Containeradapter, dessen Interface sich auf ganz wenige Funktionen beschränkt. Iteratorrückgaben gehören nicht dazu.

Nexus

windschief schrieb:

das war mit std::deque, wie bekomme ich den tatsächlich benötigten Speicher raus?

Nur ungefähr:

my_deque.size() * sizeof(Elementtyp)

Wenn du Zeiger speicherst, musst du natürlich den Speicher der referenzierten Objekte dazu rechnen.

windschief

my_deque.size() * sizeof(Elementtyp)

eine runde vor dem Absturz waren es 10000000 Objekte und die >Größe ist ca. 64.
Ich denke bis zu dem Absturz haben sich die Objekte verdoppelt.. also ca. 20000000*64.

Ich habe jetzt auch endlich verstanden was ihr meint mit new/delete neu erstellen und der pointerproblematik...

Also habe ich es jetzt so:

class foo{ };

int main(){
  foo tmpObj;
  deque<foo> container;

  while(bedingung){

   // mache was mit tmpObj
    container.push_back(tmpObj); //speichern

    // rechne irgendwas
    if(bed2){
      //update tmpObj
     container.push_back(tmpObj);
    } else {
     tmpObj = container.front();
     container.pop_front();
    }
  }
}

Jetzt noch meine Frage: Ist das so in Ordnung?
und gibt es viell irgendwelche tricks wie ich effizent das tmpObj verändern kann.
Ich rechne nicht direkt mit den variablen vom Objekt, sondern diese müssten (falls es gut genug ist) geupdatet werden.

DocShoe

Das Problem an std::deque ist, dass der Container intern aus einzelnen Blöcken zusammengesetzt ist, die untereinander verlinkt sind. Leider sind diese Blöcke relativ klein, sie fassen, je nach Template Typ, zwischen 2 und 16 Elementen (bei der Dinkumware STL, bei der STLport war´s ähnlich). Wenn der Template Typ relativ klein ist stehen Nutzdaten im Vergleich zu Verwaltungsdaten in einem schlechten Verhältnis und daraus resultiert ein enorm hoher Speicherverbrauch durch std::deque.

windschief schrieb:

Ich rechne nicht direkt mit den variablen vom Objekt, sondern diese müssten (falls es gut genug ist) geupdatet werden.

Häh?

windschief

Häh?

ich weiß ich muss noch lernen mich c++-mäßiger auszudrücken...

also wenn das tmpObj upgedatet wird passiert ja sowas:

tmpObj.set_a(/*..*/);

für jede einzelne variable. Jetzt ist meine Frage ob ich set_a() irgendwie noch optimieren kann...

bzw. wenn Objekte in die std::deque eingefügt werden, werden sie ja kopiert (falls ich das richtig verstanden habe, werden ja Kopien gespeichert).

Wäre es sinnvoll denn copy-operator zu überladen? Geht das effektiver als der Standard copy-operator? Sozusagen ähnlich wie beim swap...