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

[kali-hi]

Und Vector ist nicht gerade die effizienteste Datenstruktur.

Mir würde für den use case aber keine effizientere einfallen...

Und du solltest nicht von einer Liste sprechen wenn du Vektoren meinst.

MbMn... ist ein Vektor auch eine Liste.

 

[simpsonsfan]

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

Gutes Prinzip.

/**
 * @brief (pseudo-)randomly selects n elements of `in` and adds the elements to
 * `out` . An element may not be selected twice.
 *
 * @tparam E typename
 * @param in pointer to a vector filled with at least `n` elements
 * @param out pointer to output vector to which randomly selected elements shall
 * be appended. The appended elements will be in (pseudo-)random order.
 * @param n number of elements to select. Must be less than or equal to the size
 * of `in`
 */
template <typename E>
void select_n_elements(const vector<E> &in, vector<E> &out, uint32_t n)

Einwände?

Edit: Es macht halt schon entscheidenden Unterschied, ob man eine verkettete Liste oder einen std::vector oder ein simples Array hat. Betreibt man bspw. HPC, dann ist Performance wichtig (übrigens oft eine Verringerung an FLOPS wichtiger als ein erhöhter RAM-Bedarf.) Die Anmerkungen bzgl. schärferer/präziserer Anforderungen sind schon sinnvoll.

 

[Keylan]

Wenn Meier und Schulze gezogen werden, dann soll dort nicht auf einmal Schulze und Meier herauskommen. Am Beispiel verständlich?

Interessant wie hier nach und nach doch immer mehr Anforderungen an dieses "abstrakte" Gedankenspiel gestellt werden. Und nein das POLA gibt diese Anforderung nicht automatisch her. Nutzer könnten je nach Motivation für diesen Zufallsauszug ganz andere Vorstellungen mitbringen wie sich die erhaltene Liste darstellen soll.

Z. B. wenn die ursprungsliste Liste eine natürliche Ordnung hat, das diese erhalten bleibt, statt die Reihenfolge der Zufallszüge darzustellen. Diese ist ja vor allem für den Menschen der die Liste interpretiert gar nicht nachvollziehbar.

 

[kali-hi]

Einwände?

Ja

The appended elements will be in (pseudo-)random order.

Das würde ich hierbei einfach nicht erwarten...

Vielleicht denke ich auch zu kompliziert.

Ergänzung (17. Oktober 2025)

Z. B. wenn die ursprungsliste Liste eine natürliche Ordnung hat, das diese erhalten bleibt, statt die Reihenfolge der Zufallszüge darzustellen. Diese ist ja vor allem für den Menschen der die Liste interpretiert gar nicht nachvollziehbar.

Genau das spricht doch für das POLA...

 

[simpsonsfan]

Du würdest nicht erwarten, dass sich die Funktion so verhält wie in der Doku beschrieben?

 

[kali-hi]

dass sich die Funktion so verhält wie in der Doku beschrieben?

nope, das war nicht gemeint. Die Funktion sollte sich gemäß der Docs verhalten, aber die Docs sollten nicht für Überraschungen sorgen, also nicht unintuitiv sein, imho.

 

[foofoobar]

Mir würde für den use case aber keine effizientere einfallen...

Wenn du Speicher verbrauchen darfst (das ist auch ein Effizienzmerkmal) wäre ein array aus Pointern auf die eigentlichen Elemente effizient wenn die Anzahl der zu ziehenden Elemente klein gegenüber der Anzahl der Eingabeelemente ist.

Grob beschrieben:
Mann besorgt sich noch mal geNULLten Platz für das Pointer Array, danach zieht man zufällig aus den Array Elemente raus, bei jedem raus ziehen prüft man den Pointer auf NULL, falls NULL neuer Zufall neues Element ziehen usw.
Beim raus ziehen kopiert man den Pointer in den Platz in den Buffer an die richtige Stelle und NULLt das in den Eingabedaten. Zum Schluss oder bei Fehlern (kann man sich schenken wenn man die Eingabedaten zerstören darf) kopiert man alles ungleich NULL aus dem Buffer wieder in das originale Pointer Array zurück.

Das Ergebnis sind dann alle nicht NULL Pointer aus dem Buffer.

memcpy() ist teuer!

 

[Keylan]

Wenn Meier und Schulze gezogen werden, dann soll dort nicht auf einmal Schulze und Meier herauskommen. Am Beispiel verständlich?

Vielleicht habe ich dich falsch verstanden, ggf. ausgelöst durch die Reaktion von @foofoobar.

Also "Nein", dass Beispiel ist nicht verständlich. Was ist der Grund, dass Meier vor Schulze in der Ergebnisliste stehen soll?

Das Meier vor Schulze gezogen wurde?

oder

Das Meiner in der Ursprungsliste vor Schultze eingetragen war?

 

[foofoobar]

MbMn... ist ein Vektor auch eine Liste.

Hängt davon ab wie teuer ein indizierter Zugriff sein darf. Wenn man keinen indizierten Zugriff benötigt kann man sich den Verwaltungsaufwand dafür schenken falls man den indizierten Zugriff nicht durch eine lineare "Suche" ineffizient machen will.

FYI: Ich habe bei vielen Sachen immer den Meta-Assembler-Code vor Augen und was auf einer CPU lange dauert oder schnell geht oder was das OS stresst oder nicht, aber der Begriff "effizient" steht ja nun mal in der Überschrift.

Und letztendlich hängt es auch davon ob du viel oder wenig Elemente gegenüber der Anzahl der Eingabeelemente ziehen willst, und du solltest auch definieren ob man die Eingabeelemente zerstören darf oder nicht, und ob sich "effizient" auf Speicher oder auf CPU bezieht oder ob der Zufall teuer und gut sein darf so das man andere Aspekte die Laufzeit brauchen dann möglicherweise vernachlässigen kann.

Schlaf am besten ne Nacht drüber :-)

 

[BeBur]

MbMn... ist ein Vektor auch eine Liste.

Nein, wenn es dir um C++ geht, dann solltest du auch C++ Terminologie verwenden. Ich bin genau wie @foofoobar darüber gestolpert, dass du "Liste" schreibst, was verdächtig klingt, weil es std::list gibt, aber wenn jemand "Liste" schreibt und von C++ spricht, dann verdächtige ich die Person, dass diese Person Liste im Umgangssprachlichen (und damit nicht klar definierten) Sinne meint und nicht std::list.

std::vector ist ein ContiguousContainer und eine festes Anzahl an k Elementen daraus auszulesen hat daher selbstverständlich eine O(1) Laufzeit. Das Problem reduziert sich daher darauf, die jeweils zuletzt generierte Zufallszahl darauf zu prüfen, ob sie unique ist.

d) Eine unsortierte Binärdatenstruktur verwenden, und die ersten n Elemente ziehen

Unsortiert ist nicht das selbe wie zufällig. Außerdem ist das "das Pferd von hinten aufzäumen". Man könnte auch schreiben "die Werte unsortiert in einen Vektor schreiben und die erste n Elemente ziehen". Klar, wenn die Werte schon in zufälliger Reihenfolge vorliegen (davon ausgehend, das sei mit 'unsortiert' gemeint) ist sowieso alles egal, dann nimmst du einfach die ersten k Elemente, unabhängig von der Datenstruktur.

BTW: Und Vector ist nicht gerade die effizienteste Datenstruktur

Was gefällt dir an std::vector nicht?

Was wäre am besten?

Kann man letztendlich nicht beantworten, da das von konkreten Rahmenbedingungen abhängt und die Implementierung in einer Programmiersprache ist da tendenziell eher eine nachgelagerte Frage. Sicherlich gibt es da spannende wissenschaftliche Aufsätze zu und sobald es um Fragen der Parallelisierung geht wird es vermutlich ziemlich crazy, vor allem wenn man noch aktuelle GPU Architekturen berücksichtigen will.

 

[foofoobar]

Was gefällt dir an std::vector nicht?

Siehe einen weiter oben.

 

[BeBur]

@foofoobar Vllt. ist es schon zu spät, aber keine Ahnung was du mit dem Beitrag sagen willst oder wie man das auf deine Aussage zu std::vector beziehen kann.

Was ist denn dein Vorschlag was man verwenden sollte wenn nicht std::vector?

 

[foofoobar]

@BeBur https://www.computerbase.de/forum/t...elementen-ziehen.2254960/page-3#post-31002327

Und unterscheiden ob es "viel" zu ziehende Elemente gegenüber den Eingabeelementen gibt, bei viel zu ziehenden Elementen ist wahrscheinlich Fisher-Yates und dann n Elememente von vorne ziehen am schnellsten.

BTW: Das sieht nach "brauchbaren" schnellen "Zufall" aus: https://en.wikipedia.org/wiki/Mersenne_Twister

 

[BeBur]

@foofoobar Ah, guter Punkt. Hier mal ein Beispielprogramm mit Auswertung auf meinem AMD Ryzon 5 5500, MSVC mit /O2. Sind keine Mittelwerte, kein warm up und es schwankt ein wenig, aber man sieht die Größenordnung jedenfalls.

N / Sample                    1.000               5.000              10.000              50.000             100.000           1.000.000
---------------------------------------------------------------------------------------------------------------------------------------
        100.000            0.000631            0.000690            0.000712            0.001305            0.000721                   -
      1.000.000            0.006140            0.007969            0.007233            0.007193            0.007166            0.007429
     10.000.000            0.061361            0.067906            0.072967            0.073061            0.088949            0.079233
    100.000.000            0.632432            0.623277            0.624851            0.613109            0.617544            0.706488

#include <iostream>
#include <vector>
#include <ranges>
#include <random>
#include <chrono>
#include <algorithm>
#include <iomanip>
#include <format>  
#include <locale>

int main() {
    using namespace std;
    using clock = chrono::high_resolution_clock;

    locale::global(locale(""));

    // Testparameter
    vector<size_t> total_sizes = { 100'000, 1'000'000, 10'000'000, 100'000'000 };
    vector<size_t> sample_sizes = { 1'000, 5'000, 10'000, 50'000, 100'000, 1'000'000 };

    random_device rd;
    mt19937 rnd_generator(rd());

    // Tabellenkopf
    cout << left << setw(15) << "N / Sample";
    for (size_t s : sample_sizes)
        cout << right << setw(20) << format("{:L}", s);
    cout << "\n" << string(15 + 20 * sample_sizes.size(), '-') << "\n";

    // Für jede Datenmenge N:
    for (size_t N : total_sizes) {
        cout << right << setw(15) << format("{:L}", N);

        // 1. Erzeuge Werte und Pointer
        vector<int> values;
        values.reserve(N);
        for (int i : views::iota(0, static_cast<int>(N)))
            values.push_back(i);

        vector<int*> ptrs;
        ptrs.reserve(N);
        for (auto& v : values)
            ptrs.push_back(&v);

        // 2. Messen für verschiedene Samplegrößen
        for (size_t sample_count : sample_sizes) {
            if (sample_count > N) {
                cout << right << setw(20) << "-";
                continue;
            }

            vector<int*> random_selection;
            random_selection.reserve(sample_count);

            auto start = clock::now();
            ranges::sample(ptrs, back_inserter(random_selection), sample_count, rnd_generator);
            auto end = clock::now();

            chrono::duration<double> elapsed = end - start;
            cout << right << setw(20) << format("{:.6f}", elapsed.count());
        }

        cout << "\n";
    }

    return 0;
}

 

[kali-hi]

@BeBur Selbstgespräche?

Wo mischt du?
Wieso wird die Eingabereihenfolge nicht beibehalten?
Und so etwas schreibt man in eine Funktion, nicht in main().

 

[BeBur]

Wo mischt du?

Braucht man nicht, std::sample zieht zufällige Indizes.

Wieso wird die Eingabereihenfolge nicht beibehalten?

Ja, müsste man hinterher halt noch sortieren. Vorab geht das prinzipbedingt ja nicht.

Und so etwas schreibt man in eine Funktion, nicht in main().

Ist bei so einem Code-Snippet irrelevant.

 

[kali-hi]

Braucht man nicht, std::sample zieht zufällige Indizes.

Dann ziehst du doch doppelt...

 

[BeBur]

@kali-hi
Nein, std::sample 'zieht' Stichproben aus dem Vektor. Ich sehe auch grad, das auch die Reihenfolge erhalten bleibt. man braucht hinterher also auch nicht sortieren.

vgl. cppreference.com und siehe auch das Beispiel dort:

Possible output:

in = [6] { 1 2 3 4 5 6 }
n = 0, out = [0] { }
n = 1, out = [1] { 5 }
n = 2, out = [2] { 4 5 }
n = 3, out = [3] { 2 3 5 }
n = 4, out = [4] { 2 4 5 6 }
n = 5, out = [5] { 1 2 3 5 6 }
n = 6, out = [6] { 1 2 3 4 5 6 }
n = 7, out = [6] { 1 2 3 4 5 6 }

 

[kali-hi]

vgl. cppreference.com und siehe auch das Beispiel dort:

Das Beispiel sieht auch nicht zufällig aus, wenn die 5 (und 6) in 6 von 7 Fällen gezogen wird...

Man müsste sich halt anschauen, wie std::ranges::sample implementiert wurde... Womöglich genauso, wie ich es auf der vorherigen Seite tat... Damit wäre dann hinsichtlich der Laufzeitkosten auch nichts gewonnen.

 

[BeBur]

Das Beispiel sieht auch nicht zufällig aus, wenn die 5 (und 6) in 6 von 7 Fällen gezogen wird...

Menschen sind schlecht im generieren von Zufall weil sie u.a. versuchen das was sie für Muster halten zu vermeiden.

Man müsste sich halt anschauen, wie std::ranges::sample implementiert wurde... Womöglich genauso, wie ich es auf der vorherigen Seite tat... Damit wäre dann hinsichtlich der Laufzeitkosten auch nichts gewonnen.

Im Regelfall sollte man die Funktionen aus std verwenden. Die interagieren konsistent mit anderen Teilen von std, die Wahrscheinlichkeit von Bugs ist um ein vielfaches geringer und die Laufzeit ist für den alllgemeinen Fall üblicherweise optimal oder nahezu optimal. Mal ganz davon abgesehen, dass es sehr ineffizient ist, solche allgemeinen Funktionalitäten zu implementieren, die schon in hoher Qualität existieren.

Ich habe deine Implementierung grad noch mit reingehackt, die scheint um den Faktor 10 langsamer zu sein:

std::sample:
N / Sample                    1.000               5.000              10.000              50.000             100.000
-------------------------------------------------------------------------------------------------------------------
100.000                    0.000525            0.000543            0.000734            0.001118            0.000672
1.000.000                  0.005099            0.005913            0.006715            0.006535            0.007157
10.000.000                 0.050521            0.051892            0.052334            0.060259            0.064509
100.000.000                0.557222            0.533302            0.496073            0.520974            0.498813


select_n_elements:
N / Sample                    1.000               5.000              10.000              50.000             100.000
-------------------------------------------------------------------------------------------------------------------
100.000                    0.001629            0.002822            0.003969            0.015119            0.033494
1.000.000                  0.015445            0.017876            0.019876            0.033231            0.049901
10.000.000                 0.281106            0.303119            0.339406            0.370431            0.385298
100.000.000                4.407719            4.626497            4.695387            4.907063            4.996831