std::vector Performance



  • Hi Leute

    ich habe ein std::vector mit Pointern auf Klassenobjekte.
    Dieser wird nun nach bestimmten Kriterien sortiert in einen anderen Vector (TempList) eingefügt.

    TempList.clear();
    for ( int ts = 0; ts < (int)BasisListe.size(); ++ts )
    {
        float Fit = BasisListe[ ts ]->BerechneFitness();
    
        int iPos = -1;
        for ( int j = 0; j < (int)TempList.size(); ++j )
        {
    	  if ( Fit > TempList[j]->GetFitness() )
    	  {
    	       iPos = j;
    	       break;
    	  }
        }
        if ( iPos == -1 )
    	  TempList.push_back( BasisListe[ ts ] );
        else
    	  TempList.insert( TempList.begin() + iPos, BasisListe[ ts ]  );
    }
    

    Nun habe ich gemessen, dass der Zeitaufwand für das Einsortieren linear ansteigt. Sobald ich das Sortieren weglasse und einfach mit push_back anhänge ist der Zeitaufwand konstant.
    ( 1 Mio Klassenobjekte sind in der Basisliste ).

    Ist insert so teuer bei Pointern? (64bit)

    edit: std::list nehmen?

    gruß Tobi



  • Da std::vector intern ein Array benutzt, müssen alle Elemente ab dem eingefügten um eins nach hinten verschoben werden. Das ist natürlich sehr teuer! Vielleicht ist hier eine std::list besser oder ein std::sort am Ende des Algorithmus.



  • std::list wäre hier etwas performanter. Allerdings würde ich etwas anderes als Insertion Sort benutzen, das ist nämlich nicht sehr effizient.

    Spricht etwas gegen std::set ? Falls ja, Container zuerst normal füllen und std::sort() einsetzen.



  • Eigentlich geht fast jeder Container. Die Objekte stehen in keinerlei Beziehung zueinander. Ich brauch nur die Sortierung.

    std::set hab ich noch nie benutzt. Ich gucks mir mal an.
    std::list ebenso...



  • It0101 schrieb:

    ich habe ein std::vector mit Pointern auf Klassenobjekte.
    Dieser wird nun nach bestimmten Kriterien sortiert in einen anderen Vector (TempList) eingefügt.

    ...

    Ganz schön umständlich, nur um einen Vektor zu sortieren!

    Probier mal etwas wie das hier:

    #include <algorithm>
    #include <functional>
    
    // ...
    
    struct Vergleichomat {
      bool operator()(bums const* a, bums const* b) const {
        return a->GetFitness() < b->GetFitness();
      }
    };
    
    void dings(std::vector<bums*> const& BasisListe)
    {
       std::vector<bums*> TempList (BasisListe);
       std::for_each(TempList.begin(),TempList.end(),
          std::mem_fun(&bums::BerechneFitness) );
       std::sort(TempList.begin(),TempList.end(),
          Vergleichomat() );
       // ...
    }
    

    Gruß,
    SP



  • Bin jetzt gerade an std::set dran.

    bool MengeSort( Csystem *ts1, Csystem *ts2 )
    {
       return ( ts1->GetFitness() < ts2->GetFitness() );
    }
    
    void Klasse::Funktion()
    {
       std::set<Csystem*> Menge;
    
       ...
    
       std::sort( Menge.begin(), Menge.end(), MengeSort );
    }
    

    Build funzt aber nur wenn ich std::sort weglasse. Er scheint mit da irgendwie böse zu sein. Liegts an den begin() und end()-Iteratoren, oder an der Sortierfunktion?

    Sowas hier z.B. wirft er mir aus ( die Liste ist lang 😉 ):

    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h: In function 'void std::sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_Rb_tree_const_iterator<Csystem*>, _Compare = bool ()(Csystem, Csystem*)]':
    ../src/Cpopulation.cpp:182: instantiated from here
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h:2749: error: no match for 'operator-' in '__last - __first'
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_bvector.h:182: note: candidates are: ptrdiff_t std::operator-(const std::_Bit_iterator_base&, const std::_Bit_iterator_base&)
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h: In function 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_Rb_tree_const_iterator<Csystem*>, _Compare = bool ()(Csystem, Csystem*)]':
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h:2751: instantiated from 'void std::sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_Rb_tree_const_iterator<Csystem*>, _Compare = bool ()(Csystem, Csystem*)]'
    ../src/Cpopulation.cpp:182: instantiated from here
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h:2376: error: no match for 'operator-' in '__last - __first'
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_bvector.h:182: note: candidates are: ptrdiff_t std::operator-(const std::_Bit_iterator_base&, const std::_Bit_iterator_base&)
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h:2378: error: no match for 'operator+' in '__first + 16'
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_bvector.h:267: note: candidates are: std::_Bit_iterator std::operator+(ptrdiff_t, const std::_Bit_iterator&)
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_bvector.h:353: note: std::_Bit_const_iterator std::operator+(ptrdiff_t, const std::_Bit_const_iterator&)
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h:2379: error: no match for 'operator+' in '__first + 16'
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_bvector.h:267: note: candidates are: std::_Bit_iterator std::operator+(ptrdiff_t, const std::_Bit_iterator&)
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_bvector.h:353: note: std::_Bit_const_iterator std::operator+(ptrdiff_t, const std::_Bit_const_iterator&)
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h: In function 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_Rb_tree_const_iterator<Csystem*>, _Compare = bool ()(Csystem, Csystem*)]':
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h:2383: instantiated from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_Rb_tree_const_iterator<Csystem*>, _Compare = bool ()(Csystem, Csystem*)]'
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h:2751: instantiated from 'void std::sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_Rb_tree_const_iterator<Csystem*>, _Compare = bool ()(Csystem, Csystem*)]'
    ../src/Cpopulation.cpp:182: instantiated from here
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h:2299: error: no match for 'operator+' in '__first + 1'
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_bvector.h:267: note: candidates are: std::_Bit_iterator std::operator+(ptrdiff_t, const std::_Bit_iterator&)
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_bvector.h:353: note: std::_Bit_const_iterator std::operator+(ptrdiff_t, const std::_Bit_const_iterator&)
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h:2383: instantiated from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_Rb_tree_const_iterator<Csystem*>, _Compare = bool ()(Csystem, Csystem*)]'
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h:2751: instantiated from 'void std::sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_Rb_tree_const_iterator<Csystem*>, _Compare = bool ()(Csystem, Csystem*)]'
    ../src/Cpopulation.cpp:182: instantiated from here
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h:2305: error: no match for 'operator+' in '__i + 1'
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_bvector.h:267: note: candidates are: std::_Bit_iterator std::operator+(ptrdiff_t, const std::_Bit_iterator&)
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_bvector.h:353: note: std::_Bit_const_iterator std::operator+(ptrdiff_t, const std::_Bit_const_iterator&)
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h:2306: error: assignment of read-only location
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h: In function 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Tp, _Compare) [with _RandomAccessIterator = std::_Rb_tree_const_iterator<Csystem*>, _Tp = Csystem*, _Compare = bool ()(Csystem, Csystem*)]':
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h:2309: instantiated from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_Rb_tree_const_iterator<Csystem*>, _Compare = bool ()(Csystem, Csystem*)]'
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h:2383: instantiated from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_Rb_tree_const_iterator<Csystem*>, _Compare = bool ()(Csystem, Csystem*)]'
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h:2751: instantiated from 'void std::sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = std::_Rb_tree_const_iterator<Csystem*>, _Compare = bool ()(Csystem, Csystem*)]'
    ../src/Cpopulation.cpp:182: instantiated from here
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h:2253: error: assignment of read-only location
    /usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4/bits/stl_algo.h:2257: error: assignment of read-only location
    make: *** [src/Cpopulation.o] Error 1



  • Die Iteratoren von std::set, std::map, std::list sind keine "RandomAccessIteratoren" -- haben also kein operator[], kein +, kein -, etc.

    Falls Du die Hierarchie von Iterator-Konzepten nicht kennst, wirf mal einen Blick hierauf.

    std::sort braucht aber RandomAccessIteratoren.

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

    std::list bietet eine .sort()-Elementfunktion an.

    Gruß,
    SP



  • 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


Log in to reply