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

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

DocShoe

So richtig präzise hast du dich immer noch nicht ausgedrückt. Was passiert den in dem Fall, wo ein Objekt aktualisiert wird? Bleibt´s im Container? Muss es an das Ende verschoben werden? Spielt die Reihenfolge der Objekte im Container eine Rolle?

windschief

Hmm, du hast recht.
Entschuldigt, ihr hattet auch recht, ich hätte gleich versuchen, meinen Code in einem Minimalbeispiel zusammenzufassen. Dann seht ihr am Besten welche Probleme noch vorhanden sind und hättet euch nicht mit Pointerdiskussionen ärgern mussen....

class foo{
private:
 int a1,b1;
 double c,d,e;
public:
 // + get und set methoden für private variablen
 vector<long> f;
 // mit spezialisiertem swap;
};

int main(){
  foo tmpObj;
  deque<foo> container;
  //variabeln zum rechnen zahl ist zwischen 20 und 100
  int a[zahl],b[zahl],
  double c,d,e,
  long f[zahl];
  unsigned int stelle;

  //zuerst mögliche objekte hinzufügen bis ca. 100 stück da sind
  while(bed1){
    // rechne mit a,b,c,d,e, stelle
    if(gut){
      tmpObj.set_a(a[stelle]);
      tmpObj.set_b(b[stelle]);
      tmpObj.set_c(c);
      tmpObj.f.clear();
      for(int i=stelle; i<zahl; i++)
         tmpObj.f.push_back(f[i]);

      container.push_back(tmpObj);
    }
  }

  // jetzt arbeite mit den vorhanden objekten
  while(bed2){
   // hole die daten von dem ersten objekt
   tmpObj = container.begin();
   a = tmpObj.get_a(); // usw für alle variablen
   container.pop_front(); // lösche es aus dem container

   // hier können aus den daten des 1. objektes mehrere neue entstehen
   // oder auch komplett verworfen werden
   while(bed3){

    //rechne was mit a,b,c,d,e, stelle
    // an bestimmten stellen muss sortiert werden
    sort(container.begin(),container.end())
    //rechne was mit a,b,c,d,e, stelle

    if(gut){
      tmpObj.set_a(a[stelle]);
      tmpObj.set_b(b[stelle]);
      tmpObj.set_c(c);
      tmpObj.f.clear();
      for(int i=stelle; i<zahl; i++)
         tmpObj.f.push_back(f[i]);

      container.push_back(tmpObj);
    }
  }
}

Das ist eigentlich der Code.
in der main() ist f ein array, die länge "zahl" ist bekannt und ändert sich nicht.
Speichern muss man eigentlich nur einen Teil dieses arrays (variert zwischen 0 und zahl), deswegen habe ich einen vector gewählt in dem mittels push_back nur die werte reinkommen, die gespeichert werden müssen. Ist das gut oder wäre es vielleicht sinnvoller auch ein long f[zahl] in der class zu speichern (auch wenn 0-stelle nicht gebraucht werden), dann müßte man aber nicht immer clear() machen und neu mit werten befüllen.

ich hoffe das beschreibt es ein wenig besser und ihr könnt mir weiterhelfen.
Viell wäre es schlauer nicht sofort jedes Objekt zu löschen, aber ich weiß nicht genau wie es anders machen könnte. Aus dem einen können ja mehrere werden..
Oder wäre eine ganz andere Klassenstruktur sinnvoller?

Vielen vielen Dank für eure Mühe, ich weiß das wirklich zu schätzen!!!

p.s. oder sollte ich besser einen neuen Beitrag aufmachen?

windschief

hmm, kann mir nicht irgendwie jemand noch einen tipp geben was ich verbessern kann?
auch nur irgendein stichwort...

Blue-Tiger

Mach aus den Code doch mal verschiedene Funktionen (z. B. einen fuer jeden Bedingungs-Abschnitt) und profile es, dann siehst du wo das Problem wirklich liegt.

Ansonsten: vermeide clear()s, die koennen intern Speicher freigeben ==> langsam.