Select-Funktion

[Lennox]

Hallo, kann die "Bias"-Entstehung (die ersten Elemente werden immer etwas seltener und die letzten Elemente etwas öfter gezogen) hier irgendwie vermieden werden? Alle Vorschläge sind willkommen.

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

using namespace std;

template <typename E>
void select(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{}()};
    const double offset = (double)in.size() / n;
    const double step = offset * 2.0;
    uint32_t left = n;
    double last = -offset;
    auto dist = uniform_real_distribution<double>(0, step);
    while (left > 0)
    {
        int32_t next = round(last + dist(gen));
        if (next < 0 || next >= in.size())
            continue;
        out.push_back(in[next]);
        last = (n - left--) * offset + offset;
    }
}

void test_select()
{
    const double frac = 0.1;                        // selection fraction
    const uint32_t n1 = 1000;                       // input size
    const uint32_t n2 = 150000;                     // number of selections
    const uint32_t n3 = round(n1 * frac);           // selection size
    const uint32_t n4 = round(n1 * frac * n2);      // total selections
    const uint32_t n5 = round(n1 * frac * n2 / n1); // expected average selections per item
    unordered_map<uint32_t, uint32_t> counts;
    vector<uint32_t> in(n1);
    iota(begin(in), end(in), 0);
    for (uint32_t i = 0; i < n2; i++)
    {
        vector<uint32_t> out = {};
        select(in, out, n3);
        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 << pairs.front().first << " with " << pairs.front().second << endl;
    cout << pairs.back().first << " with " << pairs.back().second << endl;

    uint32_t min = n5 * 0.95, max = n5 * 1.05;
    uint32_t count = 0;
    for (const auto &pair : counts)
    {
        if (pair.second >= min && pair.second <= max)
        {
            count++;
        }
    }
    cout << "[" << min << "," << max << "] = " << (double)count / n1 * 100.0 << " %" << endl;
}

int main()
{
    test_select();
    return 0;
}

Möglicherweise habe ich nur ein +- 0.5 irgendwo vergessen, aber sicher bin ich mir da nicht.

[SeppJ]

Was ist denn deine genaue Anforderung? N Elemente fair und zufällig aus der Menge zu ziehen ginge ja offensichtlich viel einfacher. Du hast aber vor, das irgendwie gezielt zu verteilen? So, dass du, wenn du beispielsweise nur 2 Elemente ziehst, du eines aus der ersten Hälfte und eines aus der zweiten Hälfte ziehst?

[Lennox]

@SeppJ sagte in Select-Funktion:

Was ist denn deine genaue Anforderung?

Gute Frage, das habe ich noch nicht erwähnt.

Es sollen N Elemente zufällig (und fair (obwohl das ein schwammiger Begriff wäre)) aus der Menge gezogen werden und die Reihenfolge soll beibehalten werden.

@SeppJ sagte in Select-Funktion:

So, dass du, wenn du beispielsweise nur 2 Elemente ziehst, du eines aus der ersten Hälfte und eines aus der zweiten Hälfte ziehst?

Nein, das sollte eigentlich nicht passieren, da ja am Anfang offset * 2 gerechnet wird.

Beispiel: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

1 und 2 soll ebenso gezogen werden können wie 3 und 8.

[SeppJ]

Na, wenn es einfach nur zufällig sein soll, dann lass das ganze Gebiase halt weg. Zieh N verschiedene Zahlen aus der Menge möglicher Indizes, gerne auch sortiert, und dann die zugehörigen Elemente genommen, fertig. Schwieriger und anspruchsvoller wird das erst, wenn die Größe des Inhalts nicht feststeht, aber hier kennst du in.size() ja genau. Das gibt's aber auch direkt schon fertig: std::sample bzw. std::ranges::sample. Die kommen übrigens auch mit unbekannter Größe der Eingangsmenge zurecht.

[Lennox]

@SeppJ sagte in Select-Funktion:

Zieh N verschiedene Zahlen aus der Menge möglicher Indizes, gerne auch sortiert, und dann die zugehörigen Elemente genommen, fertig.

Das kann man zwar tun, dauert dann aber doppelt so lange, und wäre mathematisch auch nicht sauber.

Vielleicht muss man einfach nur Element für Element durchgehen und per Zufall ermitteln, ob das aktuelle Element gezogen wird oder nicht.

[SeppJ]

@Lennox sagte in Select-Funktion:

@SeppJ sagte in Select-Funktion:

Zieh N verschiedene Zahlen aus der Menge möglicher Indizes, gerne auch sortiert, und dann die zugehörigen Elemente genommen, fertig.

Das kann man zwar tun, dauert dann aber doppelt so lange, und wäre mathematisch auch nicht sauber.

Ähh, was?

Vielleicht muss man einfach nur Element für Element durchgehen und per Zufall ermitteln, ob das aktuelle Element gezogen wird oder nicht.

Oh, toll, das verschiebt dich bloß von O(anzahl samples) nach O(Größe der Menge). Du hattest was von Effizienz sagen wollen? Und wie du das mathematisch sauber machen willst, wäre noch interessanter

[Lennox]

Mal eine Zwischenfrage: Wie sortiert man denn einen zweiten Vektor, der eine Teilmenge des ersten darstellt, so, dass er in der Reihenfolge des ersten Vektors wäre? Ich kenne dafür den entsprechenden Begriff gerade nicht...

[DocShoe]

@Lennox
Indem du die Elemente des Quellvektors in deren Reihenfolge in den Zielvektor einfügst?