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

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.

unskilled

Blue-Tiger schrieb:

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

Ähmm... Nein?

Dravere

unskilled schrieb:

Blue-Tiger schrieb:

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

Ähmm... Nein?

Soweit ich weiss, macht der Standard keine Aussage darüber, also könnte theoretisch Speicher freigegeben werden. Trotzdem empfinde ich die Empfehlung als ein wenig fragwürdig.

Grüssli

Blue-Tiger

In der GNU Implementierung der Standardlib wird bei jedem clear() der Speicher des vector freigegeben. Aber auch in Implementierungen, die den Speicher nicht freigeben muesste das clear() zumindest die Dtors aller gespeicherten Elemente aufrufen ==> potentiell relativ teuer.

Dravere

Blue-Tiger schrieb:

In der GNU Implementierung der Standardlib wird bei jedem clear() der Speicher des vector freigegeben.

Wie kommst du denn darauf? Hast du das schon mal nachgeprüft? Also ich kann nichts dergleichen finden:
http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.4/a01371.html

Blue-Tiger schrieb:

Aber auch in Implementierungen, die den Speicher nicht freigeben muesste das clear() zumindest die Dtors aller gespeicherten Elemente aufrufen ==> potentiell relativ teuer.

Und was willst du machen, wenn du den std::vector leeren möchtest? Darauf verzichten? Den std::vector nochmals wrappen, um diese Verhalten zu verhindern? Ich meine, nichts dagegen, dass man clear nicht aufrufen soll, wenn man den std::vector nicht leeren will, aber wer ruft dann schon clear auf?

Grüssli

Nexus

windschief schrieb:

hmm, kann mir nicht irgendwie jemand noch einen tipp geben was ich verbessern kann?

Wenn du bei std::vector im Voraus die ungefähre Anzahl Elemente kennst, kannst du die Memberfunktion reserve() einsetzen. Übertreibe es aber nicht, sonst verschwendest du Speicher. Genaueres dazu steht auf www.cplusplus.com.

Und noch etwas, das sich nicht auf Optimierungen bezieht: Wenn du die Klasse foo kapselst, dann konsequent. Sprich: Keine öffentlichen Membervariablen.

Blue-Tiger

Dravere schrieb:

Blue-Tiger schrieb:

In der GNU Implementierung der Standardlib wird bei jedem clear() der Speicher des vector freigegeben.

Wie kommst du denn darauf? Hast du das schon mal nachgeprüft? Also ich kann nichts dergleichen finden:
http://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.4/a01371.html

Hmmm..... hoppla, hab nur gesehen dasss ~vector den gleichen Aufruf enthaelt wie clear() und ging davon aus dass das ergo auch den Speicher freigibt. aber vector erbt ja von vector_base Mea culpa

Blue-Tiger schrieb:

Aber auch in Implementierungen, die den Speicher nicht freigeben muesste das clear() zumindest die Dtors aller gespeicherten Elemente aufrufen ==> potentiell relativ teuer.

Und was willst du machen, wenn du den std::vector leeren möchtest? Darauf verzichten? Den std::vector nochmals wrappen, um diese Verhalten zu verhindern? Ich meine, nichts dagegen, dass man clear nicht aufrufen soll, wenn man den std::vector nicht leeren will, aber wer ruft dann schon clear auf?

Grüssli

hmmm.. stimmt, hatte wohl so richtig nicht nachgedacht

windschief

Huhu,

ich habe mir jetzt noch einen eigenen Kopierkonstruktor gemacht.
Er wird ca. 150000000 mal aufgerufen. Leider ist es mit meinem eigenen viel langsamer...

Also einfach:

Foo(const Foo& other){
  a=other.a;
  //usw
}

bringt wohl nix.. gibts nen Trick? Oder braucht man eigentlich keinen wenn man keine Pointer-klassenvariablen hat..

unskilled

trick: initialisierungsliste

nein, man braucht keinen, wenn flache kopien reichen

bb