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

[firespot]

Der thread zeigt ja wunderbar, wie hoch die Qualität der Standard-Bib ist.

Einige allgemeine Ideen:

-) Ich kann noch immer nicht das reserve() für den vector finden, obwohl das jetzt schon unzählige Male genannt worden ist.

-) std::vector ist für Standardfälle spezifiziert, und nicht für das letzte Quäntchen an Performance in ganz spezifischen Situationen. In letzterem Fall kann es durchaus Sinn machen, was selbstgestricktes als Container zu verwenden.
Ein std::vector ist z.B. auch auf dynamisches Wachsen/Shrinking und einfache Handhabung ausgelegt, und während die Iteratoren prinzipiell als plain-pointers realisiert werden können, sind sie das typischerweise nicht. Sondern als eine komplexere Struktur die z.B. bei increment/decrement/de-reference auf Gültigkeit (z.B. out-of-bounds) überprüft (selbst bei optimization-on). Wenn also ein plain fixed-size array mit plain pointers als Iteratoren komplett ausreichen, dann sollte das Performance-mäßig auch besser sein als ein std::vector. Die Falle ist halt den Code dazu richtig hinzukriegen (Bsp. exception-safety).

-) Man kann durch gezielte Logik eventuell was rausholen, zwei Bsp.:

A)
Man erstelle einen std::vector<bool> oder ein boost::dynamic_bitset als Sekundärcontainer, mit Größe in.size(). Jedes Element darin mappt natürlich zum entsprechenden Element in in.
In einer Schleife ziehe man nun stets Indices in [0, in.size()-1] und setzt das dazugehörige Bit im Bit-Container. Falls das Bit noch nicht gesetzt war, zählt man einen Zähler rauf, ansonsten nicht. Das ganze wird solange im rinse-&-repeat Verfahren durchgeführt (while-Schleife) bis der Zähler bei n angelangt ist, das sind dann die zu behaltenden Elemente, und die kopiert man dann in den Output-Container.
Wenn n > 50% von in.size() ist, dann werden in.size()-n Indices gezogen und diese markieren dann die nicht zu behaltenden Elemente.

B)
1) x = n
2) Man ziehe x Elemente in [0, in.size()-1] und schreibst sie in einen temporären Container (mit voralloziierter Größe x)
3) Man sortiert diese gezogenen Elemente und unter Überspringen von Dupletten schreibt man diese in einen Index-Output-Container. Dieser wird nun (wegen den Dupletten) weniger als n Elemente enthalten (diese sind aber bereits sortiert, was gleich wichtig wird).
4) x = n - [Größe vom Index-Output-Container]
5) Man ziehe Elemente in [0, in.size()-1]; per std::binary_search() wird überprüft ob das gezogene Elemente bereits im Index-output-Container vorkommt (genau für das binary_search() ist es essentiell dass die Elemente darin sortiert sind!); falls ja Element verwerfen, falls nein in den (mittlerweile geleerten aber recycleten) temporären Container schreiben; solange durchführen bis x Elemente im temporären Container sind.
6) Man sortiert die gezogenen Elemente im temporären Container und unter Überspringen von Dupletten schreibt man diese wieder in den Index-Output-Container.
7) Falls der Index-Output-Container die Größe n erreicht hat, Ende; das sind die Indices deren Elemente man dann in out schreibt.
8) Andernfalls werden die Elemente im Index-Output-Container sortiert (notwendig für das binary_search()), dann rinse-&-repeat 4)-8).
Wie bei A) gilt: Wenn n > 50% von in.size() ist, sind die gezogenen Indices diejenigen für die nicht zu behaltenden Elemente.

EDIT: Ev. ist es besser, in 5) das std::binary_search wegzulassen und stattdessen den temporären Container einfach mit x Elementen befüllen, diese dann gemäß 6) sortieren aber beim Übertragen dieser Elemente in den Index-Output-Container nur jene übertragen die im Index-Output-Container noch nicht schon vorhanden sind. Da beide Container sortiert sind lässt sich das sehr effizient realisieren (man braucht nur einen einzigen sich vorwärts bewegenden Iterator je Container). Wichtig ist, dass das memory des Index-Output-Containers auf n Elementen vorreserviert worden ist (std::vector::reserve()), damit beim Hinzufügen von Elemente am Ende dieses Containers im Zuge dieses Kopierens der Iterator dieses Containers dabei nicht invalidiert wird.

Die Idee hier ist insbesondere, dass wenn n klein bzw. groß (letzteres durch die Reverse-Logik des Ziehens der nicht zu behaltenden Elemente) im Vergleich zu in.size() ist entsprechend weniger Zufallszahlen gezogen werden müssen und Elemente hin-und-her kopiert werden müssen als beim shuffle() oder ähnlichem. Je näher n gegen 50% geht, desto mehr wird dieser Vorteil verloren gehen, und dann könnte es Sinn machen auf die shuffle()-Logik umzusteigen.
Bei 5% zu ziehenden Elemente würde ich erwarten, dass obige Variante bedeutsam schneller ist als die shuffle-Version.

Am besten wird es sein, mal die Implementation von std::sample() anzuschauen was die macht weswege sie so effizient ist. Würde mich auch gar nicht wundern, wenn die je nach der Proportion der zu ziehenden Elemente ebenfalls jeweils andere Logiken verwendet (die Sortiertalgorithmen machen sowas ja auch und switchen dynamisch um jenachdem wie sehr die Elemente schon sortiert wirken bzw. nicht, etc.).

 

[kali-hi]

wie hoch die Qualität der Standard-Bib ist.

Das hat ja auch keiner bestritten...

Ich kann noch immer nicht das reserve() für den vector finden,

An welchen Stellen denn?

vector<uint32_t> indexes(in.size()); reserviert bereits genug Platz...

 

[firespot]

Also ich würde die Funktion so schreiben. Die hab ich nicht auf den letzten Funken Performance getrimmt (dafür sollte man, wie schon gesagt, z.B. ein dynamisches einfaches Array statt einem vector nehmen), sondern einfach nur versucht unnötige Ops - auch kleine - zu ersparen. Und natürlich das ganze bug-frei aufziehen.
Beachte die Kommentare im Code. Das reserve() bezieht sich auf den Output-Container.

Was ich mir hier erspart habe: Umstellung auf ein flexibles, sauberes Interface mit zwei Random-Access Iteratoren (begin, end) für die Input-Range. einen Output-Iterator für den Output und den RNG ebenfalls als Funktionsargument übergeben.
So wie es die Standard-Bib macht, und daher ohne Beschränkung auf einen konkreten Container-Typ oder RNG für die Nutzer dieser Funktion.

template <class E>
void select_n_elements_a_1(const std::vector<E> &in, std::vector<E> &out, typename std::vector<E>::size_type n)
{
  static auto gen = std::default_random_engine{std::random_device{}()};
 
  // size_type ist der semantisch korrekte Typ (und hier korrekt falls in je > 2^32 Elemente
  // enthalten sollte ...)
  typedef typename std::vector<E>::size_type size_type;
  // Erstellen und Befüllen von indexes mit den korrekten Werten in einem Wisch. (Hoffentlich
  // ist std::ranges::to entsprechend intelligent implementiert ...)
  auto indexes = std::ranges::to<std::vector>(std::ranges::iota_view(size_type(0), size_type(in.size())));
  shuffle(indexes.begin(), indexes.end(), gen);
 
  // Falls Output sortiert sein soll:
  std::sort(indexes.begin(), indexes.begin() + n);
 
  // WICHTIG: Ohne out.clear() hat man einen Bug falls out nicht bereits bei Eingabe empty
  // war !
  out.clear();
  // reserve(): out muss dann beim push_back() garantiert nie memory neu alloziieren u
  // Elemente rumkopieren
  out.reserve(n);
  // endit: -) ist ein const-Iterator, siehe das "c" in cbegin() (könnte u.U.
  //           effizienter sein)
  //        -) wird EINMALIG berechnet, um sich das stetige Neuerrechnen in jeder
  //           Schleifeniteration zu ersparen (da ein std::vector-Iterator vermutlich auf
  //           out-of-bounds überprüfen wird, erspart man sich diese unnötige Op bei
  //           jeder Iteration)
  auto const endit = indexes.cbegin() + n;
  // Prä-Fix Increment für it (also ++it) ist besser als Post-Fix (Micro-Optimization)
  for (auto it = indexes.cbegin(); it != endit; ++it)
  {
    out.push_back(in[*it]);
  }
};

 

[BeBur]

@firespot Verstehe da grad nicht, wieso du nicht std::sample genommen hast.

 

[foofoobar]

Der thread zeigt ja wunderbar, wie hoch die Qualität der Standard-Bib ist.

Einige allgemeine Ideen:

-) Ich kann noch immer nicht das reserve() für den vector finden, obwohl das jetzt schon unzählige Male genannt worden ist.

-) std::vector ist für Standardfälle spezifiziert, und nicht für das letzte Quäntchen an Performance in ganz spezifischen Situationen. In letzterem Fall kann es durchaus Sinn machen, was selbstgestricktes als Container zu verwenden.
Ein std::vector ist z.B. auch auf dynamisches Wachsen/Shrinking und einfache Handhabung ausgelegt, und während die Iteratoren prinzipiell als plain-pointers realisiert werden können, sind sie das typischerweise nicht. Sondern als eine komplexere Struktur die z.B. bei increment/decrement/de-reference auf Gültigkeit (z.B. out-of-bounds) überprüft (selbst bei optimization-on). Wenn also ein plain fixed-size array mit plain pointers als Iteratoren komplett ausreichen, dann sollte das Performance-mäßig auch besser sein als ein std::vector. Die Falle ist halt den Code dazu richtig hinzukriegen (Bsp. exception-safety).

-) Man kann durch gezielte Logik eventuell was rausholen, zwei Bsp.:

A)
Man erstelle einen std::vector<bool> oder ein boost::dynamic_bitset als Sekundärcontainer, mit Größe in.size(). Jedes Element darin mappt natürlich zum entsprechenden Element in in.
In einer Schleife ziehe man nun stets Indices in [0, in.size()-1] und setzt das dazugehörige Bit im Bit-Container. Falls das Bit noch nicht gesetzt war, zählt man einen Zähler rauf, ansonsten nicht. Das ganze wird solange im rinse-&-repeat Verfahren durchgeführt (while-Schleife) bis der Zähler bei n angelangt ist, das sind dann die zu behaltenden Elemente, und die kopiert man dann in den Output-Container.
Wenn n > 50% von in.size() ist, dann werden in.size()-n Indices gezogen und diese markieren dann die nicht zu behaltenden Elemente.

B)
1) x = n
2) Man ziehe x Elemente in [0, in.size()-1] und schreibst sie in einen temporären Container (mit voralloziierter Größe x)
3) Man sortiert diese gezogenen Elemente und unter Überspringen von Dupletten schreibt man diese in einen Index-Output-Container. Dieser wird nun (wegen den Dupletten) weniger als n Elemente enthalten (diese sind aber bereits sortiert, was gleich wichtig wird).
4) x = n - [Größe vom Index-Output-Container]
5) Man ziehe Elemente in [0, in.size()-1]; per std::binary_search() wird überprüft ob das gezogene Elemente bereits im Index-output-Container vorkommt (genau für das binary_search() ist es essentiell dass die Elemente darin sortiert sind!); falls ja Element verwerfen, falls nein in den (mittlerweile geleerten aber recycleten) temporären Container schreiben; solange durchführen bis x Elemente im temporären Container sind.
6) Man sortiert die gezogenen Elemente im temporären Container und unter Überspringen von Dupletten schreibt man diese wieder in den Index-Output-Container.
7) Falls der Index-Output-Container die Größe n erreicht hat, Ende; das sind die Indices deren Elemente man dann in out schreibt.
8) Andernfalls werden die Elemente im Index-Output-Container sortiert (notwendig für das binary_search()), dann rinse-&-repeat 4)-8).
Wie bei A) gilt: Wenn n > 50% von in.size() ist, sind die gezogenen Indices diejenigen für die nicht zu behaltenden Elemente.

EDIT: Ev. ist es besser, in 5) das std::binary_search wegzulassen und stattdessen den temporären Container einfach mit x Elementen befüllen, diese dann gemäß 6) sortieren aber beim Übertragen dieser Elemente in den Index-Output-Container nur jene übertragen die im Index-Output-Container noch nicht schon vorhanden sind. Da beide Container sortiert sind lässt sich das sehr effizient realisieren (man braucht nur einen einzigen sich vorwärts bewegenden Iterator je Container). Wichtig ist, dass das memory des Index-Output-Containers auf n Elementen vorreserviert worden ist (std::vector::reserve()), damit beim Hinzufügen von Elemente am Ende dieses Containers im Zuge dieses Kopierens der Iterator dieses Containers dabei nicht invalidiert wird.

Die Idee hier ist insbesondere, dass wenn n klein bzw. groß (letzteres durch die Reverse-Logik des Ziehens der nicht zu behaltenden Elemente) im Vergleich zu in.size() ist entsprechend weniger Zufallszahlen gezogen werden müssen und Elemente hin-und-her kopiert werden müssen als beim shuffle() oder ähnlichem. Je näher n gegen 50% geht, desto mehr wird dieser Vorteil verloren gehen, und dann könnte es Sinn machen auf die shuffle()-Logik umzusteigen.
Bei 5% zu ziehenden Elemente würde ich erwarten, dass obige Variante bedeutsam schneller ist als die shuffle-Version.

Am besten wird es sein, mal die Implementation von std::sample() anzuschauen was die macht weswege sie so effizient ist. Würde mich auch gar nicht wundern, wenn die je nach der Proportion der zu ziehenden Elemente ebenfalls jeweils andere Logiken verwendet (die Sortiertalgorithmen machen sowas ja auch und switchen dynamisch um jenachdem wie sehr die Elemente schon sortiert wirken bzw. nicht, etc.).

Also ich suche bei einen bereits gezogenen Element einfach nach dem nächsten nicht gezogenen Element.
Wenn n zufällig ist ist auch n+x zufällig :-)

#define inc_with_wrap(foo) (foo < ElementsCnt ? foo + 1 : 0)

    issampled = alloca(ElementsCnt);                    // TODO check
    for (percent = 5; percent <= 95; percent += 5) {
        int cnt, tmp, run, rand, runner = 0;

        bzero(Elements_copy, ElementsCnt * sizeof(char*));
        bzero (issampled,ElementsCnt);
        cnt = (int) (ElementsCnt * ((double) percent / 100));
        printf("Start sampling (%d Percent) (%d count)\n", percent, cnt); clock_gettime(CLOCK_MONOTONIC, &begin);

        for (i = 0; i <= cnt; i++) {
            rand = myrand;
            if (!issampled[rand]) {                        // Element was free;
                Elements_copy[runner++] = Elements[rand]; issampled[rand]++;
            } else {                            // Element was sampled before
                tmp = rand;
                tmp = inc_with_wrap(tmp);
                while (rand != tmp && issampled[tmp]) {            // Search for Empty Element
                    tmp = inc_with_wrap(tmp);
                }
                if (rand == tmp) {
                    puts("Infinite Loop stopped");
                    exit(1);
                }
                Elements_copy[runner++] = Elements[tmp]; issampled[tmp]++;
            }
        }
        clock_gettime(CLOCK_MONOTONIC, &end);
        printf("End Sampling Time required = %.5f seconds\n", ((double) end.tv_sec + 1.0e-9 * end.tv_nsec) - ((double) begin.tv_sec + 1.0e-9 * begin.tv_nsec));

Siehe #84

Binäre Suchen oder Binäre Bäume würde ich zum markieren eher nicht nutzen weil die Zugriffe ins RAM (teuer) verschlingen und pointer-chasing bremst CPUs bzgl. Spekulation und Prefetch richtig heftig aus, da ist was mit gehashten Arrays in der Regel flotter. Macht aber auch nur Sinn wenn man Speicher sparen will/soll (@kali-hi: Zum Speichersparen ja/nein hast immer noch nichts gesagt). Ansonsten einfach ein weiteres Array nutzen oder halt leicht schmutzig aber möglicherweise flotter das MSB der Pointer dafür nutzen :-) Aber solange mich keiner schlägt bau ich das nicht rein.

Das inverse sampling ist keine schlechte Idee, allerdings hatten wir ja bereits festgestellt das Fisher-Yates ab 2/3 ziehen das reine ziehen überholt. Und Kali-Hi hat sich auch noch nicht dazu geäussert ob man die die Eingangsdaten zerstören darf.

 

[kali-hi]

Zum Speichersparen ja/nein hast immer noch nichts gesagt

Speicherplatz ist egal, solange dieser konstant/linear, aber nicht polynomial wächst... sprich: c*n, wobei c>=1, ist voll in Ordnung.

Und Kali-Hi hat sich auch noch nicht dazu geäussert ob man die die Eingangsdaten zerstören darf.

Nein, das wäre blöd, denn mit den gezogenen und den nicht gezogenen Elementen soll ja auch noch etwas gemacht werden.

MMn. hast du aber einen Denkfehler in deinem Code... denn es geht ja um Strings bzw. Personen, also etwas mit nicht fester Länge.

 

[foofoobar]

Speicherplatz ist egal, solange dieser konstant/linear, aber nicht polynomial wächst... sprich: c*n, wobei c>=1, ist voll in Ordnung.

Zusätzlicher Speicher auf dem man rumwurstet kostet RAM-Bandbreite.
In der Regel wartet man mehrere Hundert Takte auf einen RAM-Zugriff der nicht in /dev/glaskugel steht.
In der Zeit kann eine CPU jede Menge Socken stricken.

Die Cache Hit-Rate ist wie erwartet unterirdisch:

  94,56%          9070  RAM hit
   2,95%        125677  N/A
   1,28%             5  I/O hit
   0,65%         27636  L1 hit
   0,34%           317  L3 hit
   0,21%           810  L2 hit
   0,00%             1  Uncached hit

Für RAM-Bandbreiten messen ist mein Kernel zu alt: https://lwn.net/Articles/946708/
Vielleicht hat ja jemand hier eine Karre mit Intel oder einem neueren Kernel am Start.

IPC ist 2/3 und wenn ich das richtig verstehe gammelt der L1D mit knapp 1G/sec vor sich hin:

 Performance counter stats for './m':

         46.681,79 msec task-clock                       #    0,999 CPUs utilized             
             1.217      context-switches                 #   26,070 /sec                      
                29      cpu-migrations                   #    0,621 /sec                      
         1.157.293      page-faults                      #   24,791 K/sec                     
   243.543.407.130      cycles                           #    5,217 GHz                         (71,43%)
    12.679.879.107      stalled-cycles-frontend          #    5,21% frontend cycles idle        (71,43%)
   162.050.651.203      instructions                     #    0,67  insn per cycle            
                                                  #    0,08  stalled cycles per insn     (71,42%)
    26.987.852.666      branches                         #  578,124 M/sec                       (71,43%)
       810.161.069      branch-misses                    #    3,00% of all branches             (71,43%)
    44.481.187.224      L1-dcache-loads                  #  952,860 M/sec                       (71,42%)
     2.751.832.507      L1-dcache-load-misses            #    6,19% of all L1-dcache accesses   (71,43%)
   <not supported>      LLC-loads                                                             
   <not supported>      LLC-load-misses                                                       

      46,705677924 seconds time elapsed

      44,658480000 seconds user
       2,022116000 seconds sys

Und 1/3 der Zeit hängt der code in der "Zufallserzeugung" ab, das ist doch mehr als ich erwartet habe:

+   99,30%     0,00%  m        m                     [.] _start
+   99,30%     0,00%  m        libc.so.6             [.] __libc_start_main@@GLIBC_2.34
+   99,30%     0,00%  m        libc.so.6             [.] __libc_start_call_main
+   93,04%    58,78%  m        m                     [.] main
+   30,67%    22,28%  m        m                     [.] random_uint32
+   12,40%     3,48%  m        libc.so.6             [.] __printf_buffer
+   11,32%     0,38%  m        libc.so.6             [.] __snprintf_chk
+   10,71%     0,55%  m        libc.so.6             [.] __vsnprintf_internal
+    6,82%     2,05%  m        libc.so.6             [.] __printf_buffer_write
+    6,42%     0,12%  m        [kernel.kallsyms]     [k] asm_exc_page_fault
+    6,16%     0,09%  m        [kernel.kallsyms]     [k] exc_page_fault
+    5,96%     0,14%  m        [kernel.kallsyms]     [k] do_user_addr_fault
+    4,91%     0,95%  m        libc.so.6             [.] __memmove_avx512_unaligned_erms
+    3,20%     0,10%  m        [kernel.kallsyms]     [k] handle_mm_fault
+    2,93%     0,18%  m        [kernel.kallsyms]     [k] __handle_mm_fault
+    2,75%     0,07%  m        [kernel.kallsyms]     [k] handle_pte_fault
+    2,73%     0,17%  m        libc.so.6             [.] __strlen_evex
+    2,55%     0,28%  m        [kernel.kallsyms]     [k] do_anonymous_page
+    2,40%     0,16%  m        [kernel.kallsyms]     [k] lock_mm_and_find_vma
+    1,90%     0,04%  m        [kernel.kallsyms]     [k] expand_stack_locked
+    1,79%     0,37%  m        [kernel.kallsyms]     [k] expand_downwards
+    1,60%     0,08%  m        [kernel.kallsyms]     [k] alloc_anon_folio
+    1,44%     1,41%  m        libc.so.6             [.] _itoa_word
+    0,85%     0,85%  m        libc.so.6             [.] __memset_avx512_unaligned_erms
+    0,78%     0,70%  m        libc.so.6             [.] __strchrnul_evex
     0,71%     0,23%  m        [kernel.kallsyms]     [k] __mem_cgroup_charge
+    0,70%     0,04%  m        [kernel.kallsyms]     [k] vma_alloc_folio_noprof
+    0,70%     0,00%  m        [kernel.kallsyms]     [k] entry_SYSCALL_64_after_hwframe
+    0,70%     0,00%  m        [kernel.kallsyms]     [k] do_syscall_64
+    0,70%     0,00%  m        [kernel.kallsyms]     [k] x64_sys_call

MMn. hast du aber einen Denkfehler in deinem Code... denn es geht ja um Strings bzw. Personen, also etwas mit nicht fester Länge.

char **Elements, **Elements_copy;

 

[firespot]

@firespot Verstehe da grad nicht, wieso du nicht std::sample genommen hast.

War nur der Demonstration halber gedacht wie man die von @kali-hi erstellte Funktion prinzipiell an einigen Stellen verbessern könnte.

In Realcode würde ich das nie so machen, sondern std::sample nehmen und gut ist: kompakter kurzer Code, einfach verständlich, performant. Volltreffer.

 

[kali-hi]

Wenn man die Anforderung, dass die gezogenen Elemente auch sortiert sein sollen, weglässt, dann ist das gute alte Divide-and-Conquer die Lösung...

template <typename E>
void insert_randomly(const vector<E> &in, deque<uint32_t> &dq, const uint32_t start, const uint32_t end)
{
    if (start >= end)
    {
        return;
    }
    const uint32_t n = end - start;
    if (n == 1)
    {
        static auto gen = default_random_engine{random_device{}()};
        uniform_int_distribution<size_t> dist(0, 1);
        size_t i = dist(gen);
        if (i == 0)
        {
            dq.push_front(start);
        }
        else
        {
            dq.push_back(start);
        }
        return;
    }
    const uint32_t mid = start + n / 2;
    insert_randomly(in, dq, start, mid);
    insert_randomly(in, dq, mid, end);
}

inline constexpr auto select_n_elements_a_3 = []<typename E>(const vector<E> &in, vector<E> &out, const uint32_t n)
{
    if (in.size() == 0 || n == 0 || n > in.size())
    {
        return;
    }
    deque<uint32_t> dq;
    insert_randomly(in, dq, 0, in.size());
    for (uint32_t i = 0; i < n; i++)
    {
        out.push_back(in[dq.front()]);
        dq.pop_front();
    }
};

 

[kali-hi]

Edit: Nein, das war es doch nicht... Es ist zwar Divide-and-Conquer, aber letztendlich werden die Element nicht anders als wie in einer Schleife durchgegangen (also sukzessiv aufsteigend).

 

[firespot]

Also ich suche bei einen bereits gezogenen Element einfach nach dem nächsten nicht gezogenen Element.
Wenn n zufällig ist ist auch n+x zufällig :-)

Das von mir beschriebene Ziehen ist vollkommen zufällig: denn wenn stets aus einer uniformen Verteilung in [0, in.size()-1] gezogen wird, und dann jene Elemente daraus verworfen werden die schon vormals gezogen worden sind, sind die übrig gebliebenen weiterhin uniform verteilt. Es handelt sich hier um eine uniforme bedingte Verteilung (conditional distribution), also bedingt dass ein Element noch nicht gezogen war (die übriggebliebenen) ist das vollkommen uniform.
Bsp: Du ziehst x-Mal aus 1-10, die 5 und die 8 waren aber vormals schon gezogen und werden nicht berücksichtigt. Alle 5er und 8er werden also verworfen, aber dann sind die restlichen Elemente weiterhin uniform über {1, 2, 3, 4, 6, 7, 9, 10} verteilt.
Und n bzw. x waren in meiner Beschreibung nicht Indices, sondern die Anzahl der pro Schritt zu ziehenden Elemente!

Binäre Suchen oder Binäre Bäume würde ich zum markieren eher nicht nutzen weil die Zugriffe ins RAM (teuer) verschlingen und pointer-chasing bremst CPUs bzgl. Spekulation und Prefetch richtig heftig aus, da ist was mit gehashten Arrays in der Regel flotter. Macht aber auch nur Sinn wenn man Speicher sparen will/soll (@kali-hi: Zum Speichersparen ja/nein hast immer noch nichts gesagt). Ansonsten einfach ein weiteres Array nutzen oder halt leicht schmutzig aber möglicherweise flotter das MSB der Pointer dafür nutzen :-) Aber solange mich keiner schlägt bau ich das nicht rein.

Mein Algorithmus B) hat eine binäre Suche, aber keinen binären Baum sondern einen sortierten Vektor. Das ist ein feiner Trick um sich den overhead des Baums zu ersparen wenn besagter vector eh nur gelegentlich sortiert werden muss (ist bei mir auch der Fall, am Ende einer Iteration). Quelle: Scott Meyers, "Effective STL". Außerdem habe ich per Edit sogar noch eine Variante ganz ohne binäre Suche hinzugefügt.

Das inverse sampling ist keine schlechte Idee, allerdings hatten wir ja bereits festgestellt das Fisher-Yates ab 2/3 ziehen das reine ziehen überholt. Und Kali-Hi hat sich auch noch nicht dazu geäussert ob man die die Eingangsdaten zerstören darf.

Mein Algorithmus zerstört die Eingangsdaten in keinster Weise.

Der Punkt ist folgender: Wenn nur relativ wenige Elemente gezogen (oder per reverse logic verworfen) verworfen werden müssen, dann macht es Sinn die Logik des Angehens des Problems komplett zu ändern.
Extrembeispiel: 1.000.000 Elemente, man zieht nur 3 daraus. Dann ergibt es überhaupt keinen Sinn diese eine Million Elemente allesamt durchzu-shuffeln, sondern man zieht einfach munter aus [0, 999.999] bis man drei verschiedene zusammen hat. Das erste Element ist immer ein noch nicht gezogenes. Das zweite ist höchstwahrscheinlich ein noch nicht gezogenes - man muss es nur gegen das eine bereits gezogene vergleichen. Das dritte ditto - man muss es nur gegen zwei gezogene vergleichen. Wenn ich mich jetzt auf die Schnelle nicht vertan habe ist die Wahrscheinlichkeit mit nur 3-Mal Ziehen auch gleich gänzlich fertig zu sein 1 - ((0 + 1 + 2)/1,000,000), also > 99,999%.

Je niedriger die Anzahl der zu ziehenden (oder zu verwerfenden) Element im Vergleich zum Kandidaten-Pool ist, desto mehr werden alternative Algorithmen (wie die vorgeschlagenen) mit der gänzlich-durch-shuffeln-Variante den Boden aufwischen. Umgekehrt gilt natürlich: je näher man bei ca. 50% zu ziehenden Elementen ist, desto mehr werden diese alternativen Algorithmen performance-mäßig komplett zusammenbrechen, da man viel zu oft "umsonst" zieht, weil man ein bereits gezogenes Element nochmals erhält. Dann ist die gänzlich-durch-shuffeln-Variante sicher deutlich besser.
Spannend ist die Frage, wo der Bruchpunkt liegt, also wo im Schnitt das andere Verfahren besser wird. Ich vermute rein aus dem Bauchgefühl (!) heraus wenn so um die 10% der Elemente aus dem Gesamtpool zu ziehen sind, aber vielleicht liege ich damit auch deutlich daneben.

Man kann auch folgende Logik verwenden:
n sei die Anzahl der insgesamt zu ziehenden Elemente (gezogen als Indices), m ist die Anzahl der bereits gezogenenen Indices.
Dann zieht man pro Runde uniform aus [0, in.size() - 1 - m] (man nenne das Ergebnis daraus y), und der zu behaltende Index ist dann y + [Anzahl an bereits gezogenen Indices <= y]. Das ist vollkommen korrekt uniform verteilt (man "überspringt" gedanklich ja einfach nur bereits gezogene Indices) und garantiert, dass genau n-Mal gezogen werden muss.
Bsp.: in.size() = 10; m = 4.
Runde 1: Es wird aus [0, 9] gezogen, sagen wir es kommt 4 raus. Es wird 4 als solches genommen
Runde 2: Es wird aus [0, 8] gezogen, sagen wir es kommt 5 raus. Dann wird 6 genommen (6 = 5 + 1; weil ja mit der 4 bereits ein Element <= 5 vorliegt)
Runde 3: Es wird aus [0, 7] gezogen, es kommt die 1 raus. Die wird so genommen (da sowohl 1 < 4 und 1 < 6).
Runde 4: Es wird aus [0, 6] gezogen, es kommt die 6 raus. Dann wird 9 genommen (9 = 6 + 3, weil ja die bereits ermittelten Indices 4, 6 und 1 allesamt <= 6 sind).
Die Preisfrage ist, wie man die Ermittelung von [Anzahl an bereits gezogenen Indices <= y] effizient hinkriegt, denn damit steht und fällt das ganze. Wenn n klein ist spielt das keine große Rolle (der Algorithmus wird sowieso wieder mit der gänzlich-durch-shufflen-Variante den Boden aufwischen). Spannend wirds bei größerem n und es dann wirklich darauf ankommt, diese Ermittelung as efficient as possible hinzukriegen; sowie weiters auch wieder, wo im Vergleich zur gänzlich-durch-shufflen-Variante der Bruchpunkt liegt um den Algorithmus besser dahingehend zu switchen.

 

[foofoobar]

Die Preisfrage ist, wie man die Ermittelung von [Anzahl an bereits gezogenen Indices <= y] effizient hinkriegt, denn damit steht und fällt das ganze. Wenn n klein ist spielt das keine große Rolle (der Algorithmus wird sowieso wieder mit der gänzlich-durch-shufflen-Variante den Boden aufwischen). Spannend wirds bei größerem n und es dann wirklich darauf ankommt, diese Ermittelung as efficient as possible hinzukriegen; sowie weiters auch wieder, wo im Vergleich zur gänzlich-durch-shufflen-Variante der Bruchpunkt liegt um den Algorithmus besser dahingehend zu switchen.

Schreib mal Code den man vermessen kann.

 

[kali-hi]

Edit: Nein, das war es doch nicht... Es ist zwar Divide-and-Conquer, aber letztendlich werden die Element nicht anders als wie in einer Schleife durchgegangen (also sukzessiv aufsteigend).

Hier wäre noch einmal die DaC-Variante mit der Deque...

Ich hatte aber noch keine Zeit, um Zeiten zu messen ... und ich bin mir auch noch etwas unsicher, ob die Indizes in der Deque jetzt tatsächlich gemischt (also zufallsverteilt) sind.

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

using namespace std;

inline constexpr auto select_n_elements_a_1 = []<typename E>(const vector<E> &in, vector<E> &out, const uint32_t n)
{
    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 (in.size() == 0 || n == 0 || n > in.size())
    {
        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]]);
    }
};

template <typename E>
void insert_randomly(const vector<E> &in, deque<uint32_t> &dq, const uint32_t start, const uint32_t end)
{
    if (start >= end)
    {
        return;
    }
    const uint32_t mid = (start + end) / 2;
    {
        cout << "Inserting element index: " << mid << endl;
        static auto gen = default_random_engine{random_device{}()};
        uniform_int_distribution<size_t> dist(0, 1);
        size_t i = dist(gen);
        if (i == 0)
        {
            dq.push_front(mid);
        }
        else
        {
            dq.push_back(mid);
        }
    }
    insert_randomly(in, dq, start, mid);
    insert_randomly(in, dq, mid + 1, end);
}

inline constexpr auto select_n_elements_a_3 = []<typename E>(const vector<E> &in, vector<E> &out, const uint32_t n)
{
    if (in.size() == 0 || n == 0 || n > in.size())
    {
        return;
    }
    deque<uint32_t> dq;
    insert_randomly(in, dq, 0, in.size());
    for (uint32_t i = 0; i < n; i++)
    {
        out.push_back(in[dq.front()]);
        dq.pop_front();
    }
};

inline constexpr auto select_n_elements_b = []<typename E>(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);
};

// test until the first match, unused
template <typename T>
void test1(T select_n_elements, const uint32_t n, const uint32_t type)
{
    vector<uint32_t> in(n);
    iota(begin(in), end(in), 0);
    for (size_t i = 0; i < in.size();)
    {
        vector<uint32_t> out = {};
        select_n_elements(in, out, type == 0 ? 1 : n - 1);

        if (type == 0 && out[0] == i || type == 1 && find(out.begin(), out.end(), i) == out.end())
        {
            i++;
        }
    }
}

template <typename T>
chrono::duration<double> time1(T select_n_elements, const uint32_t n1, const uint32_t n2)
{
    vector<int> in(n1);
    iota(begin(in), end(in), 0);
    vector<int> out = {};
    auto start = chrono::system_clock::now();
    select_n_elements(in, out, n2);
    auto end = chrono::system_clock::now();
    return end - start;
}

int main()
{
    {
        // Example usage a)
        vector<string> in = {"a (01)", "b (02)", "c (03)", "d (04)", "e (05)", "f (06)", "g (07)", "h (08)", "i (09)", "j (10)"};
        vector<string> out = {};
        select_n_elements_a_3(in, out, 4);
        for (const auto &item : out)
        {
            cout << item << " ";
        }
        cout << endl;
    }
    {
        // Example usage b)
        vector<string> in = {"a (1)", "b (2)", "c (3)", "d (4)", "e (5)", "f (6)", "g (7)", "h (8)", "i (9)"};
        vector<string> out = {};
        select_n_elements_a_3(in, out, 4);
        for (const auto &item : out)
        {
            cout << item << " ";
        }
        cout << endl;
    }
    {
        // Example usage c)
        vector<int> in = {1};
        vector<int> out = {};
        select_n_elements_a_3(in, out, 1);
        for (const auto &item : out)
        {
            cout << item << " ";
        }
        cout << endl;
    }

    // const uint32_t n1 = 100000; // 100 thousand
    // uint32_t n2 = 0;
    // uint32_t delta = n1 / 2;
    // double dist = 100;
    // cout << setprecision(4);
    // for (size_t i = 1; i <= 55; i++)
    // {
    //     auto t1 = time1(select_n_elements_a_3, n1, n2);
    //     auto t2 = time1(select_n_elements_b, n1, n2);
    //     auto d = (t1 - t2) / t1 * 100.0;
    //     cout << "i=" << i << "\tn2=" << n2 << "\told_dist=" << dist << "\tnew_dist=" << d << "\tdelta=" << delta << endl;

    //     if (d < dist)
    //     {
    //         n2 += delta;
    //     }
    //     else if (d > dist)
    //     {
    //         n2 -= delta;
    //     }
    //     delta -= delta / 5;
    //     dist = d;
    // }
    // cout << "Final n2: " << n2 << endl;

    // const uint32_t n11 = 100000; // 100 thousand
    // const uint32_t n21 = 10000;  // approx 10%
    // auto t1 = time1(select_n_elements_a_3, n11, n21);
    // auto t2 = time1(select_n_elements_b, n11, n21);
    // auto diff_percent = (t1 - t2) / t1 * 100.0;
    // cout << "Final test with n1=" << n11 << " n2=" << n21 << " t1=" << t1.count() << " t2=" << t2.count() << " diff_percent=" << diff_percent << "%" << endl;

    return 0;
}

Inserting element index: 5
Inserting element index: 2
Inserting element index: 1
Inserting element index: 0
Inserting element index: 4
Inserting element index: 3
Inserting element index: 8
Inserting element index: 7
Inserting element index: 6
Inserting element index: 9
g (07) a (01) f (06) c (03)
Inserting element index: 4
Inserting element index: 2
Inserting element index: 1
Inserting element index: 0
Inserting element index: 3
Inserting element index: 7
Inserting element index: 6
Inserting element index: 5
Inserting element index: 8
i (9) f (6) g (7) d (4)
Inserting element index: 0
1

Dadurch sollte eben die stochastische Häufung der äußeren Elemente in der Mitte und die der mittleren an den Rändern entfallen.

Ergänzung (29. Oktober 2025)

Edit: Ach ja... clear() und reserve() in select_n_elements_x() immer noch vergessen...

 

[foofoobar]

Edit: Ach ja... clear() und reserve() in select_n_elements_x() immer noch vergessen...

Warum hast du eigentlich das Wort "effizient" in die Überschrift geschrieben?

 

[kali-hi]

Nein, Verzeihung, ich habe mich vertan, select_n_elements_a_3 ist nicht genug zufallsverteilt:

#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;

inline constexpr auto select_n_elements_a_1 = []<typename E>(const vector<E> &in, vector<E> &out, const uint32_t n)
{
    if (in.size() == 0 || n == 0 || n > in.size())
    {
        return;
    }
    out.clear();
    out.reserve(n);
    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 (in.size() == 0 || n == 0 || n > in.size())
    {
        return;
    }
    out.clear();
    out.reserve(n);
    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]]);
    }
};

template <typename E>
void insert_randomly(const vector<E> &in, deque<uint32_t> &dq, const uint32_t start, const uint32_t end)
{
    if (start >= end)
    {
        return;
    }
    const uint32_t mid = (start + end) / 2;

    static auto gen = default_random_engine{random_device{}()};
    uniform_int_distribution<size_t> dist(0, 1);
    size_t i = dist(gen);
    if (i == 0)
    {
        dq.push_front(mid);
    }
    else
    {
        dq.push_back(mid);
    }

    insert_randomly(in, dq, start, mid);
    insert_randomly(in, dq, mid + 1, end);
}

inline constexpr auto select_n_elements_a_3 = []<typename E>(const vector<E> &in, vector<E> &out, const uint32_t n)
{
    if (in.size() == 0 || n == 0 || n > in.size())
    {
        return;
    }
    out.clear();
    out.reserve(n);
    deque<uint32_t> dq;
    insert_randomly(in, dq, 0, in.size());
    for (uint32_t i = 0; i < n; i++)
    {
        out.push_back(in[dq.front()]);
        dq.pop_front();
    }
};

inline constexpr auto select_n_elements_b = []<typename E>(const vector<E> &in, vector<E> &out, const uint32_t n)
{
    if (in.size() == 0 || n == 0 || n > in.size())
    {
        return;
    }
    out.clear();
    out.reserve(n);
    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<int> in(n1);
    iota(begin(in), end(in), 0);
    vector<int> 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)
{
    unordered_map<uint32_t, uint32_t> counts;
    vector<uint32_t> in(1000);
    iota(begin(in), end(in), 0);
    for (uint32_t i = 0; i < 100; i++)
    {
        vector<uint32_t> out = {};
        select_n_elements(in, out, 100);
        for (const auto &item : out)
        {
            counts[item]++;
        }
    }

    vector<pair<int, int>> pairs;
    for (auto itr = counts.begin(); itr != counts.end(); ++itr)
    {
        pairs.push_back(*itr);
    }
    sort(pairs.begin(), pairs.end(), [=](std::pair<int, int> &a, std::pair<int, int> &b)
         { return a.second < b.second; });

    cout << "Highest probability for " << func_name << ":" << endl;
    cout << pairs.back().first << " with " << pairs.back().second << " occurrences." << endl;
    cout << "Lowest probability for " << func_name << ":" << endl;
    cout << pairs.front().first << " with " << pairs.front().second << " occurrences." << endl;
    uint32_t ten_count = 0;
    for (const auto &pair : counts)
    {
        if (pair.second == 10)
        {
            ten_count++;
        }
    }
    cout << "Number of elements with ten occurrences: " << ten_count << endl;
    cout << endl;
}

int main()
{
    test_probabilites("select_n_elements_a_1", select_n_elements_a_1);
    test_probabilites("select_n_elements_a_2", select_n_elements_a_2);
    test_probabilites("select_n_elements_a_3", select_n_elements_a_3);
    test_probabilites("select_n_elements_b", select_n_elements_b);
    return 0;
}

Highest probability for select_n_elements_a_1:
811 with 19 occurrences.
Lowest probability for select_n_elements_a_1:
501 with 1 occurrences.
Number of elements with ten occurrences: 128

Highest probability for select_n_elements_a_2:
154 with 24 occurrences.
Lowest probability for select_n_elements_a_2:
593 with 2 occurrences.
Number of elements with ten occurrences: 125

Highest probability for select_n_elements_a_3:
967 with 67 occurrences.
Lowest probability for select_n_elements_a_3:
767 with 1 occurrences.
Number of elements with ten occurrences: 2

Highest probability for select_n_elements_b:
287 with 19 occurrences.
Lowest probability for select_n_elements_b:
25 with 2 occurrences.
Number of elements with ten occurrences: 141

67 Vorkommen von 967 und nur 2 Elemente, die genau 10-mal gezogen wurden, ist dann doch etwas wenig.

Warum hast du eigentlich das Wort "effizient" in die Überschrift geschrieben?

Ich verstehe deine Frage nicht.

 

[kali-hi]

Solved.

select_n_elements_a_3 (DaC Deque...) ist die schnellste der nicht std::sample Varianten, wenn mind. die Hälfte der Elemente gezogen werden sollen...

#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;

inline constexpr auto select_n_elements_a_1 = []<typename E>(const vector<E> &in, vector<E> &out, const uint32_t n)
{
    if (in.size() == 0 || n == 0 || n > in.size())
    {
        return;
    }
    out.clear();
    out.reserve(n);
    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 (in.size() == 0 || n == 0 || n > in.size())
    {
        return;
    }
    out.clear();
    out.reserve(n);
    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]]);
    }
};

template <typename E>
void insert_randomly(const vector<E> &in, deque<uint32_t> &dq, const uint32_t start, const uint32_t end)
{
    if (start >= end)
    {
        return;
    }
    const uint32_t mid = (start + end) / 2;

    static auto gen = default_random_engine{random_device{}()};
    uniform_int_distribution<size_t> dist(0, 1);
    size_t i = dist(gen);
    if (i == 0)
    {
        dq.push_front(mid);
    }
    else
    {
        dq.push_back(mid);
    }

    i = dist(gen);
    if (i == 0)
    {
        insert_randomly(in, dq, mid + 1, end);
        insert_randomly(in, dq, start, mid);
    }
    else
    {
        insert_randomly(in, dq, start, mid);
        insert_randomly(in, dq, mid + 1, end);
    }
}

inline constexpr auto select_n_elements_a_3 = []<typename E>(const vector<E> &in, vector<E> &out, const uint32_t n)
{
    if (in.size() == 0 || n == 0 || n > in.size())
    {
        return;
    }
    out.clear();
    out.reserve(n);
    deque<uint32_t> dq;
    insert_randomly(in, dq, 0, in.size());
    for (uint32_t i = 0; i < n; i++)
    {
        out.push_back(in[dq.front()]);
        dq.pop_front();
    }
};

inline constexpr auto select_n_elements_b_1 = []<typename E>(const vector<E> &in, vector<E> &out, const uint32_t n)
{
    if (in.size() == 0 || n == 0 || n > in.size())
    {
        return;
    }
    out.clear();
    out.reserve(n);
    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<int> in(n1);
    iota(begin(in), end(in), 0);
    vector<int> 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)
{
    unordered_map<uint32_t, uint32_t> counts;
    vector<uint32_t> in(1000);
    iota(begin(in), end(in), 0);
    for (uint32_t i = 0; i < 100; i++)
    {
        vector<uint32_t> out = {};
        select_n_elements(in, out, 100);
        for (const auto &item : out)
        {
            counts[item]++;
        }
    }

    vector<pair<int, int>> pairs;
    for (auto itr = counts.begin(); itr != counts.end(); ++itr)
    {
        pairs.push_back(*itr);
    }
    sort(pairs.begin(), pairs.end(), [=](std::pair<int, int> &a, std::pair<int, int> &b)
         { return a.second < b.second; });

    cout << "Highest probability for " << func_name << ":" << endl;
    cout << pairs.back().first << " with " << pairs.back().second << " occurrences." << endl;
    cout << "Lowest probability for " << func_name << ":" << endl;
    cout << pairs.front().first << " with " << pairs.front().second << " occurrences." << endl;
    uint32_t ten_count = 0;
    for (const auto &pair : counts)
    {
        if (pair.second == 10)
        {
            ten_count++;
        }
    }
    cout << "Number of elements with ten occurrences: " << ten_count << endl;
    cout << endl;
}

int main()
{
    test_probabilites("select_n_elements_a_1", select_n_elements_a_1);
    test_probabilites("select_n_elements_a_2", select_n_elements_a_2);
    test_probabilites("select_n_elements_a_3", select_n_elements_a_3);
    test_probabilites("select_n_elements_b_1", select_n_elements_b_1);

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

    return 0;
}

Highest probability for select_n_elements_a_1:
246 with 21 occurrences.
Lowest probability for select_n_elements_a_1:
369 with 1 occurrences.
Number of elements with ten occurrences: 127

Highest probability for select_n_elements_a_2:
106 with 23 occurrences.
Lowest probability for select_n_elements_a_2:
916 with 2 occurrences.
Number of elements with ten occurrences: 114

Highest probability for select_n_elements_a_3:
405 with 21 occurrences.
Lowest probability for select_n_elements_a_3:
62 with 2 occurrences.
Number of elements with ten occurrences: 129

Highest probability for select_n_elements_b_1:
384 with 22 occurrences.
Lowest probability for select_n_elements_b_1:
315 with 2 occurrences.
Number of elements with ten occurrences: 130

select_n_elements_a_1: Selected 900000 elements from 1000000 elements. Time taken: 0.0843652 seconds.
select_n_elements_a_2: Selected 900000 elements from 1000000 elements. Time taken: 0.088481 seconds.
select_n_elements_a_3: Selected 900000 elements from 1000000 elements. Time taken: 0.0560466 seconds.
select_n_elements_b_1: Selected 900000 elements from 1000000 elements. Time taken: 0.0185281 seconds.

Ich glaube, jetzt wurde wirklich alles von allen Seiten beleuchtet. Gn8

 

[firespot]

Solved.

Nicht wirklich

Ich glaube, jetzt wurde wirklich alles von allen Seiten beleuchtet. Gn8

Nicht wirklich

Weißt es ist halt immer leicht der Performance halber die korrekte Funktionalität zu opfern. Und das ist hier wunderschön der Fall.
Hier eine adaptierte Test-Funktion, die sampelt auch gleich 100,000 Mal für eine richtig große Stichprobe:

template <typename T>
void test_probabilites_2(string func_name, T select_n_elements)
{
    unordered_map<uint32_t, uint32_t> counts;
    vector<uint32_t> in(1000);
    iota(begin(in), end(in), 0);
    auto const SamplingN = 100000;
    for (uint32_t i = 0; i < SamplingN; i++)
    {
        vector<uint32_t> out = {};
        select_n_elements(in, out, 100);
        for (const auto &item : out)
        {
            counts[item]++;
        }
    }
    
    auto const output_count = [&counts](uint32_t index) {
        cout << "Number of occurrences of element " << index << ": " << counts[index] << endl;
    };
    
    cout << "Sampling " << SamplingN << " times, please wait ..." << endl;
    output_count(0);
    output_count(124);
    output_count(125);
    output_count(126);
    output_count(249);
    output_count(250);
    output_count(251);
    output_count(499);
    output_count(500);
    output_count(501);
    output_count(749);
    output_count(750);
    output_count(751);
    output_count(874);
    output_count(875);
    output_count(876);
    output_count(999);
}

int main()
{
    test_probabilites_2("select_n_elements_a_3", select_n_elements_a_3);
    return 0;
}

Output:

Sampling 100000 times, please wait ...
Number of occurrences of element 0: 10285
Number of occurrences of element 124: 10344
Number of occurrences of element 125: 8
Number of occurrences of element 126: 10207
Number of occurrences of element 249: 10204
Number of occurrences of element 250: 0
Number of occurrences of element 251: 10230
Number of occurrences of element 499: 10150
Number of occurrences of element 500: 0
Number of occurrences of element 501: 10245
Number of occurrences of element 749: 10102
Number of occurrences of element 750: 0
Number of occurrences of element 751: 10286
Number of occurrences of element 874: 10180
Number of occurrences of element 875: 18
Number of occurrences of element 876: 10356
Number of occurrences of element 999: 10241

Wirkt nicht so ganz zufällig auf mich .

Ich hab die Output-Indices übrigens absichtlich so gewählt, dass sie einen Hint bzgl. des Logik-Fehlers in der Funktion select_n_elements_a_3 liefern.

Etwas tatsächlich zufällig hinkriegen ist gar nicht so einfach wie man denken mag.

 

[foofoobar]

Etwas tatsächlich zufällig hinkriegen ist gar nicht so einfach wie man denken mag.

Die gezogenen Nummern sollten die selben Tests bestehen wie der genutzte PRNG.
Die Anzahl der Elemente sollte dann aus der Menge n² sein um da einen sinnvoll testbaren Bitstream draus zu machen.

https://en.wikipedia.org/wiki/Randomness_test

 

[BeBur]

Etwas tatsächlich zufällig hinkriegen ist gar nicht so einfach wie man denken mag.

Und außerdem regelmäßig recht schwierig. Selbst wenn man mit zufällig "gleichverteilt" meint. Kommt natürlich auch auf die Anforderungen und den Anwendungsfall an. Ein kleiner Bias ist je nach Anwendungsfall keine Katastrophe (oder halt doch), aber fällt je nach Test nicht unbedingt auf.

 

[kali-hi]

Ich muss mir insert_randomly vielleicht noch einmal ansehen, sodass es dort keinen Bias gibt (falls dies überhaupt möglich ist...)

Ggf. könnte man aus 0 bis 2 wählen: 0=füge sofort ein, 1=füge zwischen erstem und zweitem rekursiven Aufruf ein, 2=füge zum Schluss ein... (aber das wäre nur so eine Idee)