std::vector Performance



  • std::set und std::map sind IMMER sortiert.

    Aber nach welchen Kriterien. Wenn sie IMMER sortiert wären, hätte ich ja beim Konstruktor irgendwie ne Art Sortierfunktion angeben müssen. Da das aber nicht der Fall ist...



  • It0101 schrieb:

    std::set und std::map sind IMMER sortiert.

    Aber nach welchen Kriterien. Wenn sie IMMER sortiert wären, hätte ich ja beim Konstruktor irgendwie ne Art Sortierfunktion angeben müssen. Da das aber nicht der Fall ist...

    Schau dir mal den dritten Template-Parameter an. http://www.sgi.com/tech/stl/Map.html



  • Habs jetzt so gemacht:

    struct ltstr
    {
      bool operator()( Csystem *ts1, Csystem *ts2  ) const
      {
    	  return ( ts1->GetFitness() < ts2->GetFitness() );
      }
    };
    
    std::set<Csystem*, ltstr> Menge;
    

    Ich füge 100.000 Objekte in die Menge ein,

    for ( int i = 0; i < 100000; ++i )
    {
       ....
       Menge.insert( bla );
    }
    

    aber danach gibt mir

    cout << "Laenge " << Menge.size() << endl;
    

    nur noch irgendwas zwischen 10 und 20 an...

    Gibts da noch interne Funktionen die ich evtl. deaktivieren muss ?



  • It0101 schrieb:

    Aber nach welchen Kriterien. Wenn sie IMMER sortiert wären, hätte ich ja beim Konstruktor irgendwie ne Art Sortierfunktion angeben müssen. Da das aber nicht der Fall ist...

    Doch, das ist der Fall. Zumindest wenn du eine Funktion wählst (und keinen Funktor).

    It0101 schrieb:

    Gibts da noch interne Funktionen die ich evtl. deaktivieren muss ?

    Nein, aber du solltest mal die Dokumentation lesen, beispielsweise auf www.cplusplus.com.

    Dort steht zum Beispiel:

    Because set containers do not allow for duplicate values, the insertion operation checks for each element inserted whether another element exists already in the container with the same value, if so, the element is not inserted and -if the function returns a value- an iterator to it is returned.

    Also: Erkundigen, bevor du die nächste Frage stellst! 🙂


  • Mod

    Set enthält jeweils nur ein Element zu jedem Wert, du hast wahrscheinlich viele gleich Elemente. Wenn die Anzahl erhalten bleiben soll, nimm std::multiset.



  • Ok, dann geht std::set nicht. Ich kann nämlich nicht garantieren, dass die Vergleichswerte immer unterschiedlich sind.
    Die Werte können durchaus mal zufällig gleich sein, was aber kein Auschlusskriterium für eines der Objekte sein soll.

    Edit: danke SeppJ, ich probier mal multiset.



  • ...oder einfach nochmal meinen ersten Beitrag lesen, in dem ein Vektor "vernünftig" sortiert wird.



  • Nur rein der Interesse halber: Was für einen evolutionären Algorithmus implementierst du denn da?

    CMA-ES?
    NEAT?
    CoSyne?

    //edit ich gehe einfach mal davon aus, dass du sowas implementierst :). Habe mich da durch "Fitness" inspirieren lassen 😉



  • Das geht in Richtung genetische Programmierung...

    Aber aktuell bin ich noch damit beschäftigt, die Fitness der Objekte/Genome/whatever performant zu berechnen 😉

    Mir ist nur noch nicht ganz klar, wie die Menge merkt, dass sich die Fitness ( der Vergleichswert ) meines Objekts verändert...
    Etwa dadurch, dass ich über den Iterator auf das Objekt zugreife ( was ich zwangsläufig muss 😉 ) ??

    Die Sortierung haut noch nicht ganz hin. Jedenfalls ist das "beste" Element nicht auf Menge.begin().

    Ich muss mir wohl noch etwas Wissen anlesen 😉

    Edit:

    Die zehn Elemente und ihre Fitness ( und ihre Adresse 😉 ):

    0xefed90 -18045.6
    0xefe810 -7203.81
    0xefd510 -144.109
    0xefd230 -8069.77
    0xefc1b0 -15442.9
    0xedeea0 -22978.7
    0xede960 -26723
    0xede420 -16040.8
    0xeddef0 -13854
    0xedf6b0 0

    und das erste element .begin()
    0xefed90

    Kurz gesagt: die Sortierung funzt nich 😉
    Warum das so ist, muss ich jetzt erstmal herausfinden 😉



  • Die Sortierung haut noch nicht ganz hin. Jedenfalls ist das "beste" Element nicht auf Menge.begin().

    brauchst du nur das beste? oder die besten n? oder wirklich alle?

    struct ltstr
    {
      bool operator()( Csystem *ts1, Csystem *ts2  ) const
      {
          return ( ts1->GetFitness() < ts2->GetFitness() );
      }
    };
    

    verändert GetFitness das Objekt? Oo
    wenn du das zeugs wirklich nur geordnet haben möchtest, wäre Sebastian Pizers Lösung vermutlich die beste...

    bb



  • ich will es nur sortiert haben. Nein, GetFitness ist wirklich nur ein Getter 😉
    Das wichtigste ist mir die Performance.

    Ich guck mir mal Sebastians Lösung an.



  • It0101 schrieb:

    ich will es nur sortiert haben. Nein, GetFitness ist wirklich nur ein Getter 😉

    Wozu also Zeiger auf Non-Const?

    It0101 schrieb:

    Das wichtigste ist mir die Performance.

    Dann probier am besten viele Möglichkeiten aus. Bedenke, dass std::multiset eine Baumstruktur besitzt und dementsprechend für viele Operationen O(log(n)) impliziert. Dagegen kann ein einzelnes std::sort() beim std::vector schneller sein. Kommt immer drauf an, welche Operationen du wie oft brauchst.



  • It0101 schrieb:

    Ich guck mir mal Sebastians Lösung an.

    das for_each sollte bei dir vrmtl entfallen - falls dich das irritiert

    bb



  • std::for_each( DatenVector.begin(), DatenVector.end(), std::mem_fun( &(Csystem::CalculateFitness )) );
    

    ../src/Cpopulation.cpp:174: error: invalid use of non-static member function 'double Csystem::CalculateFitness(bool)'

    Die Funktion muss doch static sein, oder etwa nicht?



  • It0101 schrieb:

    std::for_each( DatenVector.begin(), DatenVector.end(), std::mem_fun( &(Csystem::CalculateFitness )) );
    

    ../src/Cpopulation.cpp:174: error: invalid use of non-static member function 'double Csystem::CalculateFitness(bool)'

    Die Funktion muss doch static sein, oder etwa nicht?

    Nein - mem_fun -> member_function...
    hättest du dir aber auch selbst beantworten können:
    http://www.cplusplus.com/reference/std/functional/mem_fun/

    Und wie ich schon gesagt hab: brauchst du vermutlich nicht, weil die Fitness schon berechnet ist?!

    bb



  • funzt jetzt. Performance is top 🙂

    Danke euch 😉


Anmelden zum Antworten