ComputerBase Menü
Aktuelles

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

BeBur schrieb:
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.
Zum Vergrößern anklicken....
Viele Würfel-Spiele haben extra Regeln für einen Pasch.
 
Verstehe, gezinkte Würfel :D

big-bang-theory-dice.gif
 
Ich habe mir gerade die gcc Implementation von std::sample angeschaut:
https://github.com/gcc-mirror/gcc/b...stdc++-v3/include/bits/stl_algo.h#L5743-L5869

Ist schon beeindruckend wie einfach und effizient das geht wenn man weiß wie; der reservoir-sampling Algorithmus für random-access-iterators ist z.B. wirklich super-simpel und entsprechend schnell - man muss halt nur schlau genug sein um überhaupt mit der dazugehörigen Idee aufzukommen :D.
 
  • Gefällt mir
Reaktionen: kuddlmuddl und kali-hi
So, diese Funktion sollte der Zufälligkeit jetzt genügen:

C++: 
template <typename E>
void insert_randomly(const vector<E> &in, deque<uint32_t> &dq, const uint32_t start, const uint32_t end)
{
    static auto gen = default_random_engine{random_device{}()};
    uniform_int_distribution<size_t> dist(0, 1);

    if (start >= end)
    {
        if (start == end)
        {
            const size_t i = dist(gen);
            switch (i)
            {
            case 0:
                dq.push_front(start);
                break;
            case 1:
                dq.push_back(start);
                break;
            default:
                break;
            }
        }
        return;
    }

    const size_t i = dist(gen);
    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;
    }
}

C++: 
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 < 1000; i++)
    {
        vector<uint32_t> out = {};
        select_n_elements(in, out, 100);
        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 << "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 == 100)
        {
            ten_count++;
        }
    }
    cout << "Number of elements with 100 occurrences: " << ten_count << endl;
    cout << endl;
}

Code: 
Highest probability for select_n_elements_a_1:
163 with 141 occurrences.
Lowest probability for select_n_elements_a_1:
823 with 68 occurrences.
Number of elements with 100 occurrences: 38

Highest probability for select_n_elements_a_2:
100 with 149 occurrences.
Lowest probability for select_n_elements_a_2:
896 with 53 occurrences.
Number of elements with 100 occurrences: 21

Highest probability for select_n_elements_a_3:
121 with 131 occurrences.
Lowest probability for select_n_elements_a_3:
430 with 74 occurrences.
Number of elements with 100 occurrences: 45

Highest probability for select_n_elements_b_1:
476 with 133 occurrences.
Lowest probability for select_n_elements_b_1:
640 with 73 occurrences.
Number of elements with 100 occurrences: 40
 
kali-hi schrieb:
So, diese Funktion sollte der Zufälligkeit jetzt genügen:
Zum Vergrößern anklicken....
Ne, schau dir mal an wie oft im Schnitt Element # 0 gezogen wird ...

Bastel bitte mal eine saubere Testfunktion auf Zufälligkeit. Das bisherige reicht wirklich nicht aus, und hinterlässt leider sogar falsche Eindrücke bzgl. Erfüllung von Zufälligkeitskriterien.
 
Später vielleicht... ich hab auch noch andere Sachen zu tun, aber was ist denn mit der 0? Diese sollte zwischen 75 und 125-mal oft gezogen werden.

Es gibt bestimmt auch Libs mit Standardverfahren, um die Zufälligkeit zu testen.
 
kali-hi schrieb:
Später vielleicht... ich hab auch noch andere Sachen zu tun, aber was ist denn mit der 0? Diese sollte zwischen 75 und 125-mal oft gezogen werden.
Zum Vergrößern anklicken....
Sie wird doppelt so häufig gezogen wie gemäß uniformer Verteilung zu erwarten wäre (in meinem Testlauf 203 mal).
 
firespot schrieb:
in meinem Testlauf 203 mal
Zum Vergrößern anklicken....
Stimmt, es gibt da ein "Gefälle"...

Das lag an dieser Zeile:

insert_randomly(in, dq, 0, in.size());

es wurden 1001 anstatt 1000 Elemente hinzugefügt. Richtig wäre:

insert_randomly(in, dq, 0, in.size() - 1);

Anfängerfehler. ;)


Korrektur und zweite Testmethode (bitte noch einmal damit testen):

C++: 
#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)
{
    static auto gen = default_random_engine{random_device{}()};
    uniform_int_distribution<size_t> dist(0, 1);

    if (start >= end)
    {
        if (start == end)
        {
            const size_t i = dist(gen);
            switch (i)
            {
            case 0:
                dq.push_front(start);
                break;
            case 1:
                dq.push_back(start);
                break;
            default:
                break;
            }
        }
        return;
    }

    const size_t i = dist(gen);
    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;
    }
}

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() - 1);
    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_1(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 < 1000; i++)
    {
        vector<uint32_t> out = {};
        select_n_elements(in, out, 100);
        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 << "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 == 100)
        {
            ten_count++;
        }
    }
    cout << "Number of elements with 100 occurrences: " << ten_count << endl;
    cout << endl;
}

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);
    for (uint32_t i = 0; i < 100000; i++)
    {
        vector<uint32_t> out = {};
        select_n_elements(in, out, 1);
        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 << "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 count = 0;
    for (const auto &pair : counts)
    {
        if (pair.second == 100)
        {
            count++;
        }
    }
    cout << "Number of elements with 100 occurrences: " << count << endl;
    cout << endl;
}

int main()
{
    test_probabilites_1("select_n_elements_a_3", select_n_elements_a_3);
    test_probabilites_2("select_n_elements_a_3", select_n_elements_a_3);

    // 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;
}
 
firespot schrieb:
Ich habe mir gerade die gcc Implementation von std::sample angeschaut:
https://github.com/gcc-mirror/gcc/blob/14d8a5ae472ca5743016f37da2dd4770d83dea21/libstdc++-v3/include/bits/stl_algo.h#L5743-L5869

Ist schon beeindruckend wie einfach und effizient das geht wenn man weiß wie; der reservoir-sampling Algorithmus für random-access-iterators ist z.B. wirklich super-simpel und entsprechend schnell - man muss halt nur schlau genug sein um überhaupt mit der dazugehörigen Idee aufzukommen :D.
Zum Vergrößern anklicken....
Das geht in die Richtung meines Vorschlags wie man aus einer linked-List ziehen könnte, also einfach jedes n'te (n=zufall) ziehen.
 
  • Gefällt mir
Reaktionen: kali-hi
foofoobar schrieb:
wie man aus einer linked-List ziehen könnte, also einfach jedes n'te (n=zufall) ziehen
Zum Vergrößern anklicken....
Aber... spätestens bei mehr als 50 % zu ziehenden Elementen hast du doch einen Bias und es geht in die Hardcore-Mathematik...
 
kali-hi schrieb:
Aber... spätestens bei mehr als 50 % zu ziehenden Elementen hast du doch einen Bias und es geht in die Hardcore-Mathematik...
Zum Vergrößern anklicken....
Wo siehst du da einen Bias, ich hab darüber nachgedacht und finde keinen Bias.
 
Weil doch dann die "Sprungweite" (welches ist der nächste Index) < 1 wird.
 
Das Problem mit der linked-list (std::list) ist, dass bereits das Durch-Navigieren durch diese sehr teuer ist. Und weiters muss eine modifizierbare std::list (für das Entfernen von Elementen daraus) ja auch mal von irgendwo herkommen.
Und ohne freies Navigieren zu jedem Element in der list lässt sich die Zufälligkeit gemäß einer uniformen Verteilung (innerhalb dessen was der RNG selbst diesbezüglich erreicht) nicht mehr realisieren, oder nur durch andere Umwege die wieder Performance kosten.

Der gcc reservoir sampling algorithmus zieht zwar in.size()-n Zufallszahlen, was bei kleinem n diesbezüglich ungünstig ist, aber er ist in jedem Fall extrem sparsam bzgl. Kopier-Operationen und Memory wird auch nur auf das absolut notwendige (Out selber) beschränkt. Als Allrounder ist dieser Algo extrem gut.
Für Sonderfälle mit kleinem n im Vergleich zu in.size() würde sich sicher ein alternativer Algorithmus (der nur n Zufallszahlen zieht, aber dafür dann mehr memory zum Speichern bereits gezogener Elemente braucht) anbieten; ist aber ein edge-Case und ich verstehe, dass sich die gcc Programmierer den Mehraufwand dazu nicht antun.
 
  • Gefällt mir
Reaktionen: kali-hi
firespot schrieb:
Das Problem mit der linked-list (std::list) ist, dass bereits das Durch-Navigieren durch diese sehr teuer ist. Und weiters muss eine modifizierbare std::list (für das Entfernen von Elementen daraus) ja auch mal von irgendwo herkommen.
Zum Vergrößern anklicken....
Nicht immer kann man sich aussuchen in welcher Form Daten vorliegen.
Kali-Hi hat diesbezüglich ja die maximale Verwirrung gestiftet.
firespot schrieb:
Und ohne freies Navigieren zu jedem Element in der list lässt sich die Zufälligkeit gemäß einer uniformen Verteilung (innerhalb dessen was der RNG selbst diesbezüglich erreicht) nicht mehr realisieren, oder nur durch andere Umwege die wieder Performance kosten.
Zum Vergrößern anklicken....
Wo ist der Unterschied der "Zufälligkeit" ob ich für jedes Element mit einer Wahrscheinlichkeit von 50% entscheide ob ich das Element behalte oder ob ich die Hälfte der Elemente über einen zufälligen Index auswähle?
Und wenn man den PRNG als teuer ansieht kann man auch den Verbrauch an zufälligen Bits reduzieren, für den Fall 50% braucht man dann nur ein Bit anstatt vieler Bits. D.h. wenn der PRNG pro Operation 32 Bits wirft braucht es dann nur 1/32 der Aufrufe des PRNGs.
Wenn man sich also für Prozent mit einen Int begnügt reichen 7Bits an Zufall, und der Skip über mehrere Elemente ist das eine Optimierung.
 
Zuletzt bearbeitet:
foofoobar schrieb:
Wo ist der Unterschied der "Zufälligkeit" ob ich für jedes Element mit einer Wahrscheinlichkeit von 50% entscheide ob ich das Element behalte oder ob ich die Hälfte der Elemente über einen zufälligen Index auswähle?
Zum Vergrößern anklicken....
Die Ansätze ergeben andere Lösungen.

Gegeben n = in.size()/2 (also die Hälfte, wie von dir erwähnt), dann ergibt letzteres die hier gesuchten zufälligen n Elemente, während ersteres eine Sequenz an Elementen auswählt deren Gesamtanzahl einer Binomialverteilung mit B(in.size(), 0.5) folgt - also nur im Mittel die richtige Anzahl hat, zumeist aber mehr/weniger als gewünscht (probiers einfach mal aus). Um das zu korrigieren muss man dann iterativ vorgehen und in weiteren Iterationen überschüssige Elemente entfernen (wenn vormals zu viele gezogen wurden) bzw. zusätzliche Elemente hinzufügen (wenn vormals zu wenige gezogen wurden).
Wenn dabei pro Iteration für alle am Beginn einer Iteration vorhandenen Kandidaten-Elemente strikt immer dieselbe Zieh-Wahrscheinlichkeit gilt, sehe ich ad hoc keine Verletzung des Zufälligkeitsprinzips (wichtig ist, dass man innerhalb einer Iteration die Zieh-Wahrscheinlichkeit nicht adaptiert; z.B. wäre es falsch, die Zieh-Wahrscheinlichkeit für noch nicht abgearbeitete Elemente auf 0 zu setzen wenn man schon n Elemente zusammen hat). Aber die Performance so eines Vorgehens wird aufgrund seiner Komplexität grottenschlecht sein.
 
firespot schrieb:
wichtig ist, dass man innerhalb einer Iteration die Zieh-Wahrscheinlichkeit nicht adaptiert; z.B. wäre es falsch, die Zieh-Wahrscheinlichkeit für noch nicht abgearbeitete Elemente auf 0 zu setzen wenn man schon n Elemente zusammen hat
Zum Vergrößern anklicken....
Mit anderen Worten, ein Bias entsteht, wenn man während einer Iteration an den Wahrscheinlichkeiten fummelt :)

Btw. ... gilt das auch (äquivalent) für ein early exit? Sprich... ich möchte 3 aus 5 ziehen, und 1 bis 3 sind schon gezogen; durch das early exit würden aber die 4 und 5 gar nicht betrachtet werden - stattdessen sollte ich also zum Beispiel 1, 2, 3 und 5 in Kauf nehmen, und anschließend ein Element wieder entfernen.
 
@kali-hi Yupp, korrekt beschrieben.
Ein early exit wäre strikt verboten (ein early exit ist äquivalent zu dem was ich oben als das Setzen von Wahrscheinlichkeit = 0 für verbliebene Elemente beschrieben habe, weil sie dann ja ebenfalls nicht gezogen werden können), weil es indirekt ebenfalls an den Wahrscheinlichkeiten rumfummelt.

Bsp.: Insgesamt 4 Elemente (in.size() == 4), daraus sollen zwei gezogen werden (n == 2).
Wenn man nun jedes Element durchgeht und jedes mit Wahrscheinlichkeit 0.5 (= 2/4) zieht, aber aufhört wenn man zwei Elemente zusammen hat (early exit), dann passiert folgendes:
-) Element #1 kann immer gezogen werden, ist also mit Wahrscheinlichkeit 0.5 im Ergebnis vorhanden
-) Element #2 kann ebenfalls immer gezogen werden, ist also mit Wahrscheinlichkeit 0.5 im Ergebnis vorhanden
-) Element #3 bekommt nur dann eine Chance überhaupt gezogen zu werden wenn nicht sowohl Element #1 als auch Element #2 bereits gezogen wurden (da ja ansonsten early exit). Letzteres passiert mit einer Wahrscheinlichkeit von 0.5^2, womit die Eingangswahrscheinlich für Element #3 auf 1-0.5^2 absinkt; multipliziert mit der generischen Zieh-Wahrscheinlichkeit von 0.5 ergibt das eine Wahrscheinlichkeit von (1-0.5^2) * 0.5 = 0.375.
-) Für Element #4 schaut es noch schlechter aus, weil es nur dann überhaupt eine Chance bekommt gezogen zu werden wenn von den Elementen #1-3 nur maximal eines gezogen wurde.

Ich hab das mal in R simuliert, wobei Ergebnis-Samples bei denen nur 0 oder 1 Element überhaupt gezogen wurden gänzlich ignoriert wurden. Bei den restlichen Samples wurden immer nur die ersten beiden gezogenen Elemente behalten (Simulation des early exit). Das "Dichte"-Histogramm dazu (die Wahrscheinlichkeiten sind dabei so skaliert, dass sie in Summe 1 ergeben) schaut so aus - man sieht gut, wie die Wahrscheinlichkeiten für Element #3 und #4 absacken.

Code: 
set.seed(20) # Fixer RNG-Seed; Zeile weglassen für Zeit-basierten Seed
samples <- NULL
input <- 1:4
n <- 2
for (i in 1:10000) {
  x <- input[runif(length(input)) < n/length(input)]
  if (length(x) >= n) {
    samples <- c(samples, x[1:n])
  }
}
hist(samples, freq = FALSE, breaks = c(0, input))

Rplot.png
 
  • Gefällt mir
Reaktionen: kali-hi
Funny. Das Histogramm zeigt genau auf wie ein ganz einfacher Algorithmus entwickelt werden kann - indem man für die Elemente die Zieh-Wahrscheinlichkeiten jeweils so korrigiert, dass die im Histogram aufgezeigten reduzierten Eingangswahrscheinlichkeit wieder gegenkompensiert werden und am Schluss garantiert genau n Elemente gezogen werden (beides zusammen einfach per Berücksichtigung wie viele Elemente schon gezogen worden sind vs. wie viele noch zu ziehen sind; und wieviele Elemente bereits abgearbeitet vs. noch nicht abgearbeitet worden sind):

C++: 
#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_y = []<typename E>(const vector<E> &in, vector<E> &out, typename vector<E>::size_type n)
{
    out.clear();
    if (in.size() == 0 || n == 0) return;
    out.reserve(n);
  
    n = min(n, in.size());
  
    typedef typename vector<E>::size_type size_type;
  
    size_type elementsToProcess = in.size();
    size_type elementsProcessed = 0;
    size_type elementsToDraw = n;
    size_type elementsDrawn = 0;
  
    static auto gen = default_random_engine{random_device{}()};
  
    auto it = in.cbegin();
    while (elementsDrawn != n) {
        uniform_int_distribution<size_type> dist(0, elementsToProcess - 1);
        if (dist(gen) < elementsToDraw) {
            out.push_back(*it);
            ++elementsDrawn;
            --elementsToDraw;
        }
        ++elementsProcessed;
        --elementsToProcess;
        ++it;
    }
};

template <typename T>
void test_probabilites_1(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 < 100000; i++)
    {
        vector<uint32_t> out = {};
        select_n_elements(in, out, 100);
        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 << "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;

    cout << endl;
}

int main()
{
    test_probabilites_1("select_n_elements_y", select_n_elements_y);
    return 0;
}

Sofern da kein bug drinnen ist, wärs das meiner Meinung nach.

Und auf den ersten Blick sieht das auch analog aus zur gcc Implementation für forward iterators, wenngleich letztere noch cleverer implementiert ist.
 
  • Gefällt mir
Reaktionen: kali-hi
Du musst dich einloggen oder registrieren, um hier zu antworten.
Zurück
Oben

Willkommen auf ComputerBase!

Mit Werbung weiterlesen

Besuche ComputerBase wie gewohnt mit Werbung und Tracking. Die Zustimmung ist jederzeit widerrufbar.

Details im Privacy Center und in der Liste unserer Partner. Ein Widerruf ist möglich in der Datenschutzerklärung.

… oder ComputerBase Pro bestellen

Nutze ComputerBase ohne Werbebanner, Video-Ads und Werbetracking schon für 4 €/Monat oder 36 €/Jahr.

Mehr zu ComputerBase Pro

Bereits Pro-Nutzer? Hier anmelden.

Tracking: Wir und unsere 171 Partner verarbeiten personenbezogene Daten, indem wir mit auf Ihrem Gerät gespeicherten Informationen (z. B. eindeutige Kennungen in Cookies) ein Nutzungsprofil erstellen, um z. B. Anzeigen zu personalisieren. Verarbeitungszwecke: Genaue Standortdaten und Abfrage von Geräteeigenschaften zur Identifikation, Informationen auf einem Gerät speichern und/oder abrufen, Personalisierte Anzeigen und Inhalte, Anzeigen- und Inhaltsmessungen, Erkenntnisse über Zielgruppen und Produktentwicklungen.

Impressum Kontakt Datenschutz