C++ Wie kann man effizient 10 % aus einer List mit vielen Elementen ziehen?

[kali-hi]

out.clear(); if (in.size() == 0 || n == 0) return; out.reserve(n);

Für mich wäre das schon streitbar.

Wenn keine Elemente gezogen werden sollen, muss dann auch der out-Vektor gecleart werden, oder wäre dies ein Ausnahmefall, wo eigentlich nichts passieren sollte?

Sprich

clear()
if ... return or throw ...
reserve()

vs.

if ... return or throw ...
clear()
reserve()

(oder sogar
clear()
reserve()
if ... return or throw ... )

Wenn ersteres, dann würde ich eigentlich auch ein reserve(0) erwarten (Verringerung der Vektor-Größe). Aber vielleicht sehe ich diese Kleinigkeit auch falsch.

Ansonsten vielen Dank für die Erklärung

 

[simpsonsfan]

Achso, ich dachte ihr habt meinen Ansatz verglichen mit dem von @foofoobar. [...]

Vielleicht etwas spät, aber ich will die Antwort noch bringen. Aber hatte leider zuletzt wenig Zeit und auch nicht komplett alles seither gelesen.
Das waren die verschiedenen Ansätze (gesamte Indizes mischen vs. von vorne durchgehen und samplen, also Code von dir sowie von kali-hi und foofoobar. Der von foofoobar war dabei eben mit einem Pointer Array, die C++ Varianten mit std::vector.
Ein reserve für die Output-Vektoren hatte ich tatsächlich auch getestet, das war aber nicht aussschlaggegebend für die Performance bzw. hatte sich quasi nicht ausgewirkt. (Ich meine, ein std::vector wird vermutlich in den meisten Implementierungen beim Erweitern verdoppelt, so dass nicht zu oft Speicher allokiert werden muss.)
Und seither war ja glaube ich auch ein Profiling da, das besagte, dass in dem Code von foofoobar ein großer Teil der Laufzeit im Zufallsgenerator verbracht wird. In dem damals von mir getetsteten C++ Code wurden die gezogenen Elemente derweil jeweils in den out-Vector geschoben. Das dürfte dort mutmaßlich großen Performanceanteil ausgemacht haben.

[...] muss dann auch der out-Vektor gecleart werden, oder wäre dies ein Ausnahmefall, wo eigentlich nichts passieren sollte?

Wichtig ist nur, dass genau das passiert, was in der Spezifikation dokumentiert ist. Es gibt eben häufig viele verschiedene Arten, etwas zu tun, deshalb muss man es spezifizieren und als User nicht einfach irgend ein Verhalten annehmen. Gerade bei Bibliotheken in C oder C++ sieht man eben häufig, dass eine Funktion auch nur für bestimmte Bereiche an Eingabewerten spezifiziert ist. Man darf da als Nutzer nicht einfach annehmen, dass schon was Sinnvolles rauskommen wird, egal was man reinschmeißt. Deshalb is auch RTFM so wichtiger und hilfreicher Rat. Aber eben nur, wenn TFM auch exisitiert und korrekt ist.

 

[BeBur]

wenn TFM auch exisitiert und korrekt ist.

Das Problem hat C++ bzw. die STL jedenfalls nicht . Eher, dass es so formal und korrekt ist, dass die Verständlichkeit manchmal leidet.

 

[firespot]

Für mich wäre das schon streitbar.

Die Funktion war ja nur gedacht um den Algorithmus zu zeigen. Und mangels einer konkreten Spezifikation ist das Verhalten bzgl. clear()/reserve()/etc. vom vector weder falsch noch richtig.

Für eine ernsthafte Funktion sollte sowieso das Interface komplett geändert werden: mit Iteratoren für die Input-Range, einen Output-Iterator für den Output, und der RNG wird ebenfalls an die Funktion übergeben. Dann ist man frei von jeglichen Container-Annahmen (und dann kann z.B. auch std::ostream_iterator<T>(std::cout) das Output-Ziel sein um direkt auf std::cout auszugeben), frei bzgl. dem vom Nutzer gewünschten RNG, und somit auch extrem flexibel.

Wie kann so ein Interface im Detail aussehen? Einfach std::sample als Referenz nehmen. Ich wüsste nicht was man da verbessern könnte, oder anders gesagt warum man irgendein anderes Interface als das dortige nehmen sollte.
Generell ist die STL für mich eine Referenz wie Interfaces von selber gestrickten Funktionen typischerweise aussehen sollten. Und wenn man was abweichendes bastelt sollte man sich ernsthaft fragen, ob das tatsächlich sinnvoll ist und nicht unnötige Einschränkungen mit sich bringt.

Falls der Nutzer der Funktion dann einen vector als Output-Ziel haben will, liegt es in seiner Verantworung das entsprechende reserve() vorher zu machen wenn er maximale Performance haben will. Wie sehr ein reserve() übrigens wichtig bzgl. der GEsamt-Performance ist hängt nebst der Anzahl an auszugebenen Elementen auch davon ab ob der Copy-Constructor / Move-Constructor dieser Elemente teuer ist oder nicht. Wir haben bisher mit "billig zu kopierenden/move-enden" Elementen gearbeitet, wodurch dieser Faktor nicht auffiel. Bei anderen Klassen kann das aber ganz anders ausschauen. Bastel einfach mal so eine Klasse und teste den Effekt wenn viele Elemente in einen Vektor geschrieben werden und es dabei zu häufigen memory-Neualloziierungen mit entsprechenden move-Operations kommt (wie man eine gesicherte memory-Neualloziierung herbeiführen kann ist wieder ein ganz anderes Thema, denn wenn der bestehende Speicher per realloc() einfach erweitert werden kann gibts auch keine diesbezüglichen Einbußen).

Die Quintessenz bei einem vector ist aber einfach: Wenn die Ziel-Größe a priori bekannt ist, dann sollte sie auch per reserve() alloziiert werden: um allfällige copies/moves zu minimieren und gleichzeitig die memory consumption zu optimieren.

 

[kali-hi]

einer konkreten Spezifikation

Da sind wir doch wieder beim POLS-Prinzip, eine Spezifikation (oder Dokumentation) sollte mich nicht überraschen, das heißt, eine Funktion sollte sich "sinnvoll" verhalten.

Vorschlag in Pseudocode:

wenn n > size: throw error
clear()
reserve(n)
wenn n == 0: return
...

 

[firespot]

Und wer bestimmt was "sinnvoll" ist?

Und wenn wir schon da sind: In C++ ist es überhaupt nicht sinnvoll, dass eine Funktion:
-) auf einem vector als Input-Daten besteht
-) auf einem vector als Output-Ziel besteht
-) ihren ganz eigenen RNG nutzt

Wenn die Funktion ein ordentliches Interface hat, dann stellt sich das Thema mit clear()/reserve() etc. überhaupt nicht mehr, weil es überhaupt keine Einschränkung mehr gibt dass das Output-Ziel ein clear()/reserve()/whatever überhaupt unterstützen muss. Ein Output-Iterator unterstützt nur sehr wenige Operationen und gibt quasi nichts über das Output-Ziel bekannt, dafür ist man wieder sehr flexibel (siehe z.b. das obige std::ostream_iterator<T>(std::cout) als ein Beispiel)!

Im Modularitätsprinzip von C++ / der STL kann sich der Nutzer ja eh alles mögliche zusammenbasteln, indem er den Code um den Funktionsaufruf herum entsprechend gestaltet. Eine Funktion selbst sollte in diesem Kontext aber idealerweise nur eine Aufgabe übernehmen, diese dafür effizient und flexibel.

Für die Frage wie die Funktion mit n > Input-Range vorgehen soll: Kann man unterschiedlich spezifizieren. Eine Möglichkeit wäre undefined behaviour spezifizieren, dann ist ja eh alles erlaubt. Eine andere wäre n auf maximal die Input-Range zu beschränken.
std::sample sagt dazu (https://en.cppreference.com/w/cpp/algorithm/sample.html): "If n is greater than the number of elements in the sequence, selects all elements in the sequence." Also zweiteres. Womit diese Funktion eh relativ "freundlich" spezifiziert ist, denn das gibt deutlich mehr Garantien her als undefined behaviour, was ja oft genug vorkommt.

 

[kali-hi]

-) ihren ganz eigenen RNG nutzt

Wo siehst du denn das gegeben?

Meiner Ansicht nach ist die Funktion, jedoch nicht der Aufrufer dafür zuständig. Und mehr als 3 Parameter wäre nach Uncle Bob auch ein Anti-Pattern.

 

[firespot]

@kali-hi Sorry dem muss ich klar widersprechen. Die Funktion weiß ja gar nicht in welchem Kontext sie genutzt werden soll, und daher auch nicht welcher RNG angemessen ist.

Zwei Anwendungsbeispiele:

1) Performance vs. Güte des RNG bei der Nutzung der Funktion:
Beispiele:
a) Ein Spieleentwickler legt Wert auf maximale Performance bei der Generierung der Sequenz, die Güte ist zweitrangig. Genommen wird daher ein sehr schneller RNG.
2) Für Standardfälle wird Mersenne-Twister als Allrounder genommen.
3) Für kryptographische Anwendungen muss maximale Güte erzielt werden, genommen wird daher ein langsamer aber bzgl. Güte extrem guter RNG.

2) Zustand des RNG kontrollieren zu können:
Beispiel:
In einer MCMC-Application (https://de.wikipedia.org/wiki/MCMC-Verfahren) soll der RNG (nur einer in der ganzen Applikation) am Beginn einen vom Nutzer kontrollierbaren seed bekommen. Dann wird nach jeder chain-Iteration (chain = das zweite "C" in MCMC) der Zustand des RNG gespeichert um die Kette reproduzierbar jederzeit mit demselben RNG-Zustand fortzusetzen zu können (notwendig wenn z.B. nach einer Erstanalyse herauskommt, dass weitere Iterationen als die bisherigen notwendig sind um ein gutes MCMC-mixing zu erzielen).
P.S.: Ich hab so eine Applikation tatsächlich entwickelt. Ohne Kontrolle über den RNG wäre das nicht machbar gewesen, und jegliche Funktion die stur auf ihrem eigenen RNG beharrt hätte wäre im Aus gelandet.

In der C++ Standard-Bib wird der RNG standardmäßig per r-value reference übergeben (das &&), und ist somit unter freier Kontrolle des Nutzers. So gehört sich's auch.

Und bzgl. Anzahl der Parameter: So viele wie notwendig. Nicht mehr, nicht weniger.
std::sample hat 5, und ich sehe da weder was problematisches daran, noch wie man sinnvoll auch nur einen einzigen Parameter einsparen könnte.

 

[kali-hi]

Beispiele:

Für a) b) c) könnte man doch überladene (oder "parallele") Funktionen verwenden, die jeweils einen für den Anwendungsfall passenden RNG verwenden... Oder man "wrappt" sie.

Und bzgl. Anzahl der Parameter: So viele wie notwendig.

Der Ansicht war ich lange auch, aber nach Uncle Bob ist das falsch... Man sollte dann Konfigurationsobjekte oder das Builder/Factory Pattern anwenden. Und das Ganze natürlich immer fluent...

Die Regeln bezüglich Anzahl der Parameter und Anzahl der Zeilen einer Funktion/Methode sind aber auch nicht ganz unumstritten. 1

 

[BeBur]

Für a) b) c) könnte man doch überladene (oder "parallele") Funktionen verwenden, die jeweils einen für den Anwendungsfall passenden RNG verwenden... Oder man "wrappt" sie.

Das läuft doch auf das selbe hinaus.

Klar ist das eine Frage des Scopes und ich denke firespot hat bei diesem Zitat:

In C++ ist es überhaupt nicht sinnvoll, dass eine Funktion:
-) auf einem vector als Input-Daten besteht
-) auf einem vector als Output-Ziel besteht
-) ihren ganz eigenen RNG nutzt

An libraries oder gar die STL gedacht und generell an das Design von Funktionen vergleichbar zu std::*. Wenn ich für mein konkretes Problem einen de-factro wrapper für std::sample habe dann wird dieser womöglich richtigerweise einen RNG vorgeben, weil u.a. deswegen der Wrapper überhaupt erst existiert.

 

[firespot]

Ich beziehe mich darauf, dass als Ausgangspunkt eine flexible, allgemein nutzbare Funktion vorherrschen soll die per se möglichst wenige Einschränkungen haben soll. Auch in rein eigenen Programmen hilft das sehr (z.B. späterer code-reuse unter anderen Anforderungen etc.).

Ob man dann zu dieser auch noch wrapper, Überladungen etc. bereitstellt hängt vom Kontext und Anwendungszweck ab. Flexible Funktionen über wrapper etc. weiter einschränken oder spezialisieren geht ja immer noch. Wenn der umgekehrte Fall auftritt, also Türen mal zu siind, hat man das Problem.

In #95 kommt diese Funktion hier vor:

template <typename E>
void select_n_elements_b(const vector<E> &in, vector<E> &out,
                         const uint32_t n)
{
    static auto gen = default_random_engine{random_device{}()};
    sample(in.begin(), in.end(), back_inserter(out), n, gen);
}

Das ist ja ein wrapper. Spricht ja auch nichts dagegen sowas zu machen (ob ein echter Mehrwert geliefert wird ist eine andere Sache, gegeben dass dieser wrapper ja auch dokumentiert & spezifiziert werden muss; aber wenn man z.B. dem Nutzer die Wahl eines RNG ersparen will, warum nicht). Dieser wrapper funktioniert aber nur und ist so kompakt schreibbar weil eben die Basisfunktion für das eigentliche sampling - std::sample - bereits flexibel ist.

Abgesehen davon finde ich es sinnvoll, wenn sich Interfaces generell an der STL orientieren. Konsistenz hilft.

 

[kali-hi]

Ja, es ist eine Wrapper-Funktion, welche den Aufruf delegiert, und passende Argumente wählt. Und ja, etwas Dynamik/Flexibilität geht dabei auch flöten. Beides finde ich aber in Ordnung.

... Und die genaue Doc. bzw. Spezifikation fehlt auch noch, ja

 

[foofoobar]

Und mehr als 3 Parameter wäre nach Uncle Bob auch ein Anti-Pattern.

Ob man sich solchen holzschnittartigen Regeln unterwerfen will sollte jeder für sich selbst entscheiden.
Sollte man auch SQL auf 80 Zeichen Länge begrenzen?

 

[kali-hi]

Wir wären uns bestimmt einig, dass 50 Parameter (nicht var args...) für eine Funktion ohne eine gute Begründung zu viel wären.

Bezüglich der Länge von Methoden gibt es andere Metriken, die dafür besser wären. Zum Beispiel die zyklomatische Komplexität

 

[foofoobar]

@kali-hi Wenn doch die Realität einfacher wäre .......

 

[firespot]

Man kann auch mit nur einem Parameter immer auskommen :

/* str: A struct which contains it, end, out, n and RNG */
template <class s>
void my_sample(s & str) {
auto it = str.it;
auto end = str.end;
auto out = str.out;
auto n = str.n;
auto & RNG = str.RNG;
...
}

 

[BeBur]

Du lachst zwar, aber wenn man das in Verbindung mit designated initializers verwendet, dann kommt es weniger schnell zu Verwechslungen und man hat im wesentlichen named parameters wie man es aus z.B. Python kennt:

my_sample({
  .it = myout.begin(), 
  .end = myout.end(), 
  .out = myout, 
  .n = mywhatevernmeans, 
  .RNG = my_rng})

Eine moderne IDE macht das allerdings größtenteils überflüssig.

 

[foofoobar]

@BeBur Dann kommt bestimmt gleich irgendein Onkel um die Ecke der Structs mit mehr als 3 Elementen scheiße findet.

BTW: Mein Rekord in C liegt bei 8-9 Sternchen hintereinander :-)

 

[kali-hi]

So, ich habe das jetzt noch einmal glattgezogen (Fehlerbehandlung und so...) und für die Deque eine eigene Klasse definiert (obwohl ich nicht so genau weiß, warum...)

#include <cstdint>
#include <cmath>
#include <chrono>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <random>
#include <deque>
#include <unordered_map>

using namespace std;

class ElementsSelector
{
private:
    static random_device rd;
    static default_random_engine generator;
    static uniform_int_distribution<size_t> yn_distribution;
    template <typename E>
    static void insert_randomly(const vector<E> &in, deque<uint32_t> &dq, const uint32_t start, const uint32_t end)
    {
        if (start > end)
        {
            throw invalid_argument("start index cannot be greater than end index");
        }
        if (start == end)
        {
            const size_t i = yn_distribution(generator);
            switch (i)
            {
            case 0:
                dq.push_front(start);
                break;
            case 1:
                dq.push_back(start);
                break;
            default:
                break;
            }
            return;
        }

        const size_t i = yn_distribution(generator);
        const uint32_t mid = (start + end) / 2;
        switch (i)
        {
        case 0:
            insert_randomly(in, dq, start, mid);
            insert_randomly(in, dq, mid + 1, end);
            break;
        case 1:
            insert_randomly(in, dq, mid + 1, end);
            insert_randomly(in, dq, start, mid);
            break;
        default:
            break;
        }
    }

public:
    ElementsSelector(/* args */);
    ~ElementsSelector();
    template <typename E>
    static void select_n_elements(const vector<E> &in, vector<E> &out, const uint32_t n)
    {
        if (n > in.size())
        {
            throw invalid_argument("n cannot be greater than the size of input vector");
        }
        out.clear();
        out.reserve(n);
        if (n == 0)
        {
            return;
        }

        deque<uint32_t> dq;
        insert_randomly(in, dq, 0, in.size() - 1);
        for (uint32_t i = 0; i < n; i++)
        {
            out.push_back(in[dq.front()]);
            dq.pop_front();
        }
    }
};

random_device ElementsSelector::rd;
default_random_engine ElementsSelector::generator(ElementsSelector::rd());
uniform_int_distribution<size_t> ElementsSelector::yn_distribution(0, 1);

ElementsSelector::ElementsSelector(/* args */)
{
}

ElementsSelector::~ElementsSelector()
{
}

inline constexpr auto select_n_elements_a_1 = []<typename E>(const vector<E> &in, vector<E> &out, const uint32_t n)
{
    if (n > in.size())
    {
        throw invalid_argument("n cannot be greater than the size of input vector");
    }
    out.clear();
    out.reserve(n);
    if (n == 0)
    {
        return;
    }
    static auto gen = default_random_engine{random_device{}()};
    vector<uint32_t> indexes(in.size());
    iota(begin(indexes), end(indexes), 0);
    shuffle(indexes.begin(), indexes.end(), gen);
    sort(indexes.begin(), indexes.begin() + n);
    for (auto it = indexes.begin(); it != indexes.begin() + n; it++)
    {
        out.push_back(in[*it]);
    }
};

inline constexpr auto select_n_elements_a_2 = []<typename E>(const vector<E> &in, vector<E> &out, const uint32_t n)
{
    if (n > in.size())
    {
        throw invalid_argument("n cannot be greater than the size of input vector");
    }
    out.clear();
    out.reserve(n);
    if (n == 0)
    {
        return;
    }
    static auto gen = default_random_engine{random_device{}()};
    uint32_t indexes[in.size()];
    for (uint32_t i = 0; i < in.size(); i++)
    {
        indexes[i] = i;
    }
    const uint32_t limit = in.size() - 1;
    for (uint32_t i = 0; i < in.size(); i++)
    {
        uint32_t j = uniform_int_distribution<uint32_t>{0, limit}(gen);
        swap(indexes[i], indexes[j]);
    }
    sort(indexes, indexes + n);
    for (uint32_t i = 0; i < n; i++)
    {
        out.push_back(in[indexes[i]]);
    }
};

inline constexpr auto select_n_elements_a_3 = []<typename E>(const vector<E> &in, vector<E> &out, const uint32_t n)
{
    ElementsSelector::select_n_elements(in, out, n);
};

inline constexpr auto select_n_elements_b_1 = []<typename E>(const vector<E> &in, vector<E> &out, const uint32_t n)
{
    if (n > in.size())
    {
        throw invalid_argument("n cannot be greater than the size of input vector");
    }
    out.clear();
    out.reserve(n);
    if (n == 0)
    {
        return;
    }
    static auto gen = default_random_engine{random_device{}()};
    sample(in.begin(), in.end(), back_inserter(out), n, gen);
};

template <typename T>
chrono::duration<double> test_runtime(string func_name, T select_n_elements, const uint32_t n1, const uint32_t n2)
{
    vector<uint32_t> in(n1);
    iota(begin(in), end(in), 0);
    vector<uint32_t> out = {};
    auto start = chrono::system_clock::now();
    select_n_elements(in, out, n2);
    auto end = chrono::system_clock::now();
    cout << func_name << ": Selected " << out.size() << " elements from " << in.size() << " elements. Time taken: " << chrono::duration<double>(end - start).count() << " seconds." << endl;
    return end - start;
}

template <typename T>
void test_probabilites(string func_name, T select_n_elements)
{
    static auto gen = default_random_engine{random_device{}()};
    const uint32_t n1 = uniform_int_distribution<uint32_t>(800, 1200)(gen);
    const uint32_t n2 = round(n1 * 0.1);
    unordered_map<uint32_t, uint32_t> counts;
    vector<uint32_t> in(n1);
    iota(begin(in), end(in), 0);
    for (uint32_t i = 0; i < 100000; i++)
    {
        vector<uint32_t> out = {};
        select_n_elements(in, out, n2);
        for (const auto &item : out)
        {
            counts[item]++;
        }
    }

    vector<pair<uint32_t, uint32_t>> pairs;
    for (uint32_t i = 0; i < in.size(); i++)
    {
        pairs.push_back({i, counts[i]});
    }
    sort(pairs.begin(), pairs.end(), [=](std::pair<uint32_t, uint32_t> &a, std::pair<uint32_t, uint32_t> &b)
         { return a.second < b.second; });

    cout << "Testing function:    " << func_name << " with input size: " << n1 << " and selection size: " << n2 << endl;
    cout << "Highest probability: " << pairs.back().first << " with " << pairs.back().second << " occurrences." << endl;
    cout << "Lowest probability:  " << pairs.front().first << " with " << pairs.front().second << " occurrences." << endl;
    uint32_t count = 0;
    for (const auto &pair : counts)
    {
        if (pair.second >= 9900 && pair.second <= 10100)
        {
            count++;
        }
    }
    cout << "Number of elements with occurrences between 9900 and 10100: " << count << endl;
    cout << endl;
}

int main()
{
    test_probabilites("select_n_elements_a_3", select_n_elements_a_3);

    test_runtime("select_n_elements_a_1", select_n_elements_a_1, 1000000, 500000);
    test_runtime("select_n_elements_a_2", select_n_elements_a_2, 1000000, 500000);
    test_runtime("select_n_elements_a_3", select_n_elements_a_3, 1000000, 500000);
    test_runtime("select_n_elements_b_1", select_n_elements_b_1, 1000000, 500000);

    return 0;
}

Compilieren mit: g++ -std=c++17 -Wall -Wextra -Werror Main.cpp -o a.out

Ausgabe:

Testing function:    select_n_elements_a_3 with input size: 935 and selection size: 94
Highest probability: 752 with 10359 occurrences.
Lowest probability:  108 with 9749 occurrences.
Number of elements with occurrences between 9900 and 10100: 605

select_n_elements_a_1: Selected 500000 elements from 1000000 elements. Time taken: 0.191114 seconds.
select_n_elements_a_2: Selected 500000 elements from 1000000 elements. Time taken: 0.112488 seconds.
select_n_elements_a_3: Selected 500000 elements from 1000000 elements. Time taken: 0.0632722 seconds.
select_n_elements_b_1: Selected 500000 elements from 1000000 elements. Time taken: 0.0289104 seconds.

Die Deque (select_n_elements_a_3/ElementsSelector) ist also unter den eigenen Versuchen noch die/der schnellste (nur etwa die Hälfte der Zeit des Zweitplatzierten und ein Viertel der des Drittplatzierten...)

So, und das muss nun erst mal reichen, keine Lust mehr.

 

[foofoobar]

$ g++ -O3 -std=c++17 -Wall -Wextra -Werror Main.cpp 
$ ./a.out 
Testing function:    select_n_elements_a_3 with input size: 875 and selection size: 88
Highest probability: 761 with 10356 occurrences.
Lowest probability:  652 with 9671 occurrences.
Number of elements with occurrences between 9900 and 10100: 332

select_n_elements_a_1: Selected 50000000 elements from 100000000 elements. Time taken: 4.07873 seconds.
select_n_elements_a_2: Selected 50000000 elements from 100000000 elements. Time taken: 4.12759 seconds.
select_n_elements_a_3: Selected 50000000 elements from 100000000 elements. Time taken: 1.81776 seconds.
select_n_elements_b_1: Selected 50000000 elements from 100000000 elements. Time taken: 0.689868 seconds.
$

Start sampling (5 Percent) (5000000 count)
End Sampling Time required = 0.12274 seconds
0: 82482960, 1: 47175951, 2: 37191809, 3: 41093301, 4: 55602759,

Meiner ist schneller und länger :-)

BTW:

 Performance counter stats for '/tmp/a.out':

         13.001,00 msec task-clock                       #    0,999 CPUs utilized             
               342      context-switches                 #   26,306 /sec                      
                15      cpu-migrations                   #    1,154 /sec                      
           788.496      page-faults                      #   60,649 K/sec                     
    67.738.009.155      cycles                           #    5,210 GHz                         (71,43%)
    17.373.149.772      stalled-cycles-frontend          #   25,65% frontend cycles idle        (71,44%)
    70.563.625.660      instructions                     #    1,04  insn per cycle            
                                                  #    0,25  stalled cycles per insn     (71,43%)
    10.881.773.476      branches                         #  836,995 M/sec                       (71,43%)
     1.495.680.726      branch-misses                    #   13,74% of all branches             (71,43%)
    33.473.001.062      L1-dcache-loads                  #    2,575 G/sec                       (71,42%)
       532.273.174      L1-dcache-load-misses            #    1,59% of all L1-dcache accesses   (71,43%)
   <not supported>      LLC-loads                                                             
   <not supported>      LLC-load-misses                                                       

      13,008361931 seconds time elapsed

      11,958447000 seconds user
       1,042603000 seconds sys

+   30,85%     0,00%  a.out    [unknown]             [.] 0000000000000000
+   20,92%     0,16%  a.out    a.out                 [.] std::chrono::duration<double, std::ratio<1l, 1l> > test_runtime<select_n_elements_a_2::{lambda<typename $T0>(std::vector<$T0, std::allocator<$T0> > const&, std::vector<$T0, std::allocator<$T0> >&, unsigned int)#1}>(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, select_n_elements_a_2::{lambda<typename $T0>(std::vector<$T0, std::allocator<$T0> > const&, std::vector<$T0, std::allocator<$
+   20,48%    18,20%  a.out    a.out                 [.] auto select_n_elements_a_2::{lambda<typename $T0>(std::vector<$T0, std::allocator<$T0> > const&, std::vector<$T0, std::allocator<$T0> >&, unsigned int)#1}::operator()<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> >&, unsigned int) const
+   15,76%    13,32%  a.out    a.out                 [.] void ElementsSelector::insert_randomly<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::deque<unsigned int, std::allocator<unsigned int> >&, unsigned int, unsigned int) [clone .isra.0]
+   15,50%    15,41%  a.out    a.out                 [.] void std::shuffle<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::linear_congruential_engine<unsigned long, 16807ul, 0ul, 2147483647ul>&>(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, std::linear_co
    14,84%    14,77%  a.out    a.out                 [.] void std::__introsort_loop<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, long, __gnu_cxx::__ops::_Iter_less_iter>(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, long, __gnu_cxx::__ops::_Iter_less_iter)
    14,62%    14,53%  a.out    a.out                 [.] void std::__introsort_loop<unsigned int*, long, __gnu_cxx::__ops::_Iter_less_iter>(unsigned int*, unsigned int*, long, __gnu_cxx::__ops::_Iter_less_iter) [clone .isra.0]
+    9,27%     3,81%  a.out    a.out                 [.] unsigned long std::uniform_int_distribution<unsigned long>::operator()<std::linear_congruential_engine<unsigned long, 16807ul, 0ul, 2147483647ul> >(std::linear_congruential_engine<unsigned long, 16807ul, 0ul, 2147483647ul>&, std::uniform_int_distribution<unsigned long>::param_type const&) [clone .isra.0]
+    9,26%     0,23%  a.out    [kernel.kallsyms]     [k] asm_exc_page_fault
+    8,58%     0,18%  a.out    [kernel.kallsyms]     [k] exc_page_fault
+    8,04%     0,28%  a.out    [kernel.kallsyms]     [k] do_user_addr_fault
+    6,62%     0,22%  a.out    [kernel.kallsyms]     [k] handle_mm_fault
+    6,12%     0,36%  a.out    [kernel.kallsyms]     [k] __handle_mm_fault
+    5,71%     0,16%  a.out    [kernel.kallsyms]     [k] handle_pte_fault
+    5,28%     0,54%  a.out    [kernel.kallsyms]     [k] do_anonymous_page
+    4,73%     0,74%  a.out    libc.so.6             [.] __memset_avx512_unaligned_erms
+    3,54%     0,00%  a.out    [unknown]             [.] 0x0000000900000004
+    3,54%     2,97%  a.out    a.out                 [.] auto select_n_elements_b_1::{lambda<typename $T0>(std::vector<$T0, std::allocator<$T0> > const&, std::vector<$T0, std::allocator<$T0> >&, unsigned int)#1}::operator()<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> >&, unsigned int) const
+    3,36%     0,16%  a.out    [kernel.kallsyms]     [k] alloc_anon_folio
+    3,01%     2,44%  a.out    a.out                 [.] auto select_n_elements_a_1::{lambda<typename $T0>(std::vector<$T0, std::allocator<$T0> > const&, std::vector<$T0, std::allocator<$T0> >&, unsigned int)#1}::operator()<unsigned int>(std::vector<unsigned int, std::allocator<unsigned int> > const&, std::vector<unsigned int, std::allocator<unsigned int> >&, unsigned int) const
+    2,84%     0,00%  a.out    [unknown]             [.] 0x0000000400000002
+    2,61%     1,53%  a.out    a.out                 [.] std::chrono::duration<double, std::ratio<1l, 1l> > test_runtime<select_n_elements_a_3::{lambda<typename $T0>(std::vector<$T0, std::allocator<$T0> > const&, std::vector<$T0, std::allocator<$T0> >&, unsigned int)#1}>(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, select_n_elements_a_3::{lambda<typename $T0>(std::vector<$T0, std::allocator<$T0> > const&, std::vector<$T0, std::allocator<$
+    1,56%     0,00%  a.out    [kernel.kallsyms]     [k] entry_SYSCALL_64_after_hwframe
+    1,56%     0,00%  a.out    [kernel.kallsyms]     [k] do_syscall_64
+    1,56%     0,00%  a.out    [kernel.kallsyms]     [k] x64_sys_call
+    1,54%     0,07%  a.out    [kernel.kallsyms]     [k] vma_alloc_folio_noprof

  50,90%           121  RAM hit
  36,12%         35363  N/A
  11,25%         11014  L1 hit
   0,99%            21  L3 hit
   0,70%           167  L2 hit
   0,06%             2  Uncached hit