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

[kali-hi]

Es geht darum, wie man aus einer Liste (Datenstruktur) zufällig 10 % der Elemente effizient ziehen könnte...

Sagen wir, es gibt 3 Mio. Elemente und 300 Tsd. sollen von diesen gezogen werden.

Mir würden da spontan fünf Wege einfallen:

a) Jeweils einen zufälligen Index wählen, und das Element aus der Liste entfernen
b) Jeweils einen zufälligen Index wählen, die Elemente markieren, und hinterher nur einmal über die Liste iterieren und alle markierten Elemente on-the-fly entfernen
c) Die Liste mischen, und die ersten n Elemente ziehen (oder die letzten n)
d) Eine unsortierte Binärdatenstruktur verwenden, und die ersten n Elemente ziehen
e) Eine neue Liste anlegen, jeweils einen zufälligen Index wählen, und das Element aus der alten in die neue Liste kopieren (also nicht entfernen), und hinterher die alte durch neue Liste ersetzen

Was wäre am besten? Würde sich etwas ändern, wenn anstatt 10 % auch, sagen wir, 50 bis 100 % (generischer Parameter) aus der Liste gezogen werden könnten?

Das sind keine Hausaufgaben, eher ein Gedankenexperiment

 

[mr_andersson]

d, wenn die Daten schon als Binärbaum vorliegen.

Ansonsten a, wobei es sich bei mehr als 50% je nach Hardware, Datenmenge und Anforderungen an den RNG anbieten kann, nur die auszuwählen, die man behalten will und eine neue Liste mit diesen Elementen zu erstellen.

 

[JackForceOne]

Zur Frage "Was wäre am besten?" fehlt wie so oft ein Ziel an dem der Erfolg gemessen werden kann. Auch hast Du nicht gesagt, ob x% zufällig gezogen werden sollen oder nicht. Und der Zufall, naja der ist so eine Sache. Für diesen Fall hier ist es wahrscheinlich nicht sonderlich wichtig, aber echter Zufall ist nicht ganz so easy zu erzeugen.

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

 

[Tornhoof]

Du musst dir Ziehen mit Zurücklegen vs. ohne Zurücklegen überlegen, also effektiv ob du Duplikate haben willst.
Die Variante ohne Zurücklegen, also ohne Duplikate ist nicht so einfach wie sich das anhört, einfach die Werte entfernen funktioniert da nicht, weil sich dann der Bereich für deinen Zufallszahlengenerator ändert (wenn man es streng sieht und dann potentiell eine andere Verteilung hast)

Der einfachste Weg normalerweise:
- Solange zufällig Werte auswählen aus deiner Liste und in ein Set schreiben bis du 10% erreicht hast, also das Set größe X erreicht hat.

Damit änderst du deine Eingabeliste nicht ab (was nicht effizient wäre) und umgehst Fairnessprobleme beim Generator.

 

[madmax2010]

Willst du auf Laufzeitkomplexitaet hinaus?

c) Die Liste mischen, und die ersten n Elemente ziehen (oder die letzten n)

das ist auf jedenfall o(n)

 

[Tornhoof]

Im zugehörigen Shuffle Algorithmus Artikel auf Wikipedia ist auch das Problem der Fairness beim Ziehen beschrieben: https://en.wikipedia.org/wiki/Fisher–Yates_shuffle

 

[kali-hi]

das ist auf jedenfall o(n)

muss ich widersprechen, O(n²) hätte Fisher-Yates

Jedes 10. Element zu ziehen, wäre wahrscheinlich nicht fair - oder?

 

[Web-Schecki]

Und der Zufall, naja der ist so eine Sache. Für diesen Fall hier ist es wahrscheinlich nicht sonderlich wichtig, aber echter Zufall ist nicht ganz so easy zu erzeugen.

Jedes halbwegs moderne Betriebssystem stellt dir Routinen zur Verfügung, die sogar kryptographisch sichere Zufallszahlen erzeugen. Für Kernelentwickler ist das also durchaus ein Problem, ansonsten nicht.

Zur Frage: Solange du einen proportionalen Anteil an Elementen ziehen willst (und nicht etwa eine konstante Anzahl), wird es trivialerweise ohnehin auf asymptotisch lineare Laufzeit hinauslaufen, da du dir ja zumindest mal die gezogenen Elemente anschauen musst.
Aus dieser Sicht ist es ziemlich egal, solange du keine naive Implementierung wählst, die dir superlineare asymptotische Laufzeit reinknallt.
Fisher-Yates-Shuffle wurde ja schon genannt und kann in asymptotisch linearer Laufzeit permutieren. Wäre auch mein erster Ansatz.
In der Praxis kommt es sicherlich auf die genaue Implementierung an. Wenn wir wirklich von einer einfach verketteten Listen als Datenstruktur sprechen, dann sehe ich wenig Chancen auf sublineare asympotitische Laufzeit (in Erwartung): Alle Elemente haben dieselbe Wahrscheinlichkeit, das erste Element zu sein, dass du ziehst. Dementsprechend hast du mit Wahrscheinlichkeit 1/2 bereits im ersten Schritt ein Element aus der hinteren Hälfte der Liste, also eine erwartete Laufzeit von mindestens n/4, weil du mit Wahrscheinlichkeit 1/2 ja erstmal durch die halbe Liste laufen musst, um zum ersten Element zu kommen.

Falls das ganze als Array vorliegt und du per Index in Konstantzeit auf die Elemente zugreifen kannst, dann kann man sicherlich etwas cleverer vorgehen, solange du weniger als die Hälfte der Elemente extrahieren willst. Du willst dann also k Elemente aus der Menge {1,...,n} ziehen, und zwar ohne Zurücklegen. Das ist tendenziell anspruchsvoll, lässt sich aber wie folgt lösen: Ziehe in jedem Schritt solange aus {1,...,n} (rein zufällig), bis du ein Element erwischst, dass du bisher noch nicht gezogen hast.
Es lässt sich zeigen, dass du dann in Erwartung und mit hoher Wahrscheinlichkeit nur O(k) Schritte brauchst.

O(n²) hätte Fisher-Yates

Da muss ich widersprechen, bei vernünftiger Implementierung läuft dieser Algorithmus in O(n). Siehe Wikipedia.

Jedes 10. Element zu ziehen, wäre wahrscheinlich nicht fair - oder?

Was heißt hier fair?
Es wäre halt schlicht nicht zufällig...

 

[Tornhoof]

muss ich widersprechen, O(n²) hätte Fisher-Yates

Das ist nicht richtig, die Beschreibung in Knuths Buch vom Durstenfeld ist O(n), die originale Beschreibung von Fisher und Yates ist O(n²)

Ergänzung (16. Oktober 2025)

die sogar kryptographisch sichere Zufallszahlen erzeugen. Für Kernelentwickler ist das also durchaus ein Problem, ansonsten nicht.

Nur wenn das entsprechende Framework entsprechende Zufallszahlen in einem fixen Bereich erzeugen kann, ansonsten hast das Mod bias Problem wieder. Zb in c# ist's eine relativ neue Erfindung
https://learn.microsoft.com/en-us/d...generator-getint32(system-int32-system-int32) (.NET Core 3.0)

 

[Piktogramm]

Es geht darum, wie man aus einer Liste (Datenstruktur) zufällig 10 % der Elemente effizient ziehen könnte...
[...]

a) Jeweils einen zufälligen Index wählen, und das Element aus der Liste entfernen
b) Jeweils einen zufälligen Index wählen, die Elemente markieren, und hinterher nur einmal über die Liste iterieren und alle markierten Elemente on-the-fly entfernen
c) Die Liste mischen, und die ersten n Elemente ziehen (oder die letzten n)
d) Eine unsortierte Binärdatenstruktur verwenden, und die ersten n Elemente ziehen
e) Eine neue Liste anlegen, jeweils einen zufälligen Index wählen, und das Element aus der alten in die neue Liste kopieren (also nicht entfernen), und hinterher die alte durch neue Liste ersetzen

Was wäre am besten? Würde sich etwas ändern, wenn anstatt 10 % auch, sagen wir, 50 bis 100 % (generischer Parameter) aus der Liste gezogen werden könnten?

Das sind keine Hausaufgaben, eher ein Gedankenexperiment

Klingt, riecht, sieht aus wie eine Hausausgabe aus einer Grundlagenvorlesung.
Dafür, dass du in mindestens einem anderem Thread einen auf dicke Programmiererhose gemacht hast, ist das hier "wunderlich".

Um deine Vorgaben bewerten zu können fehlen Eigenschaften der Liste und Anforderungen an die Zufälligkeit. Die Liste kann geordnet sein, kann ungeordnet sein, kann clustert sein, oder aber bereits (hinreichend) zufällig. Beim "Zufall" der Auswahl gibt es dann auch Abstufungen, muss/darf die Zufälligkeit statistisch unauffällig sein oder nicht.

Was die einzelnen Punkte angeht, wieso präsentierst du hier keinen einzigen Gedanken dazu? Es schaut halt wirklich wie Hausaufgabe aus, bei der du die Diskussion Dritte machen lassen willst, mit sehr wenig Eigenleistung.
Es könnte an der Unschärfe natürlicher Sprache liegen, aber keine der Vorschläge würde ich wählen. Beispiel a) :

• Gegeben ist eine Liste L1, du willst Elemente (En mit n=[0 ; 2.999.999]) von zufällig auswählen und entfernen. Schlussbedingung ist wahrscheinlich, dass die Liste nur noch n=300.000 Elemente enthält.
  • Das Entfernen aus einer Liste bedeutet, dass die Elemente im Speicher deallokiert werden. (de)alloc ist vergleichsweise teuer.
    • Speicherfragmentation galore.
  • Jenachdem wie die Liste aufgebaut ist, muss mindestens ein Pointer umgeschrieben werden.
  • Da das Entfernen auf der Liste zufällig erfolgen soll, springst du massiv auf der Liste rum. Für jeden Sprung muss (je wie die Liste aufgebaut ist) im Mittel die verbleibende Liste zu 50% abgeschritten werden.
    • Dadurch, dass du zufällig Elemente aus der Liste kegelst, ist Cachelokalität erwartbar schlecht, Branchmissprediction wahrscheinlich hoch.

Wenn du selber aus a) gekommen ist und das für effizient hältst wäre das kein gutes Zeichen. Wenn a) eine Vorgabe aus der Hausaufgabe ist und du nicht selber "siehst", dass das Bockmist ist wäre das Wiederholen vom ersten Lehrjahr bzw. Semester zu empfehlen.

Edit: Die Diskussion über die O-Notation ist ganz nett, aber brauchts das, wenn man "Entfernen von Elementen aus Liste" überhaupt zur Diskussion stellt?

Edit2: Es fehlt auch die Anforderung, welche Zufälligkeit die zu erzeugende Liste L2 hat. Die Elemente dieser müssen zufällig aus L1 gewählt werden, aber muss L2 selber zufällig angeordnet sein, oder darf L2 die Ordnung aus L1 übertragen werden?

Jedes halbwegs moderne Betriebssystem stellt dir Routinen zur Verfügung, die sogar kryptographisch sichere Zufallszahlen erzeugen. Für Kernelentwickler ist das also durchaus ein Problem, ansonsten nicht.

Wobei /dev/rand Ressourcen frisst und dafür recht wenig Durchsatz liefert. Je nach Anforderung an die Zufälligkeit sollte man sich auf /dev/urand nur einen Seed ziehen .

 

[Web-Schecki]

Nur wenn das entsprechende Framework entsprechende Zufallszahlen in einem fixen Bereich erzeugen kann

Das hat aber nichts mit Hardware-RNGs zutun. Das ist ein Problem, das jede vernünftige Softwarebibliothek zur Generierung von Wahrscheinlichkeitsverteilungen löst. Den Modulo-Bias kann man leicht umschiffen.

Wobei /dev/rand Ressourcen frisst und dafür recht wenig Durchsatz liefert. Je nach Anforderung an die Zufälligkeit sollte man sich auf /dev/urand nur einen Seed ziehen .

Klar, hier im konkreten Fall geht's auch sicherlich nicht um kryptographisch sicheren Zufall. Macht den Einwurf von Hardware-RNGs doch aber nur noch absurder

 

[firespot]

In C++ hat das Iterieren über eine std::list die Komplexität O(n), weil eine list einfach jeweils aus Knoten besteht die mit dem Vorgänger- und Nachgängerknoten verknüpft sind. Daher solltest du tunlichst schauen, nur ein einziges Mal über diese Liste zu iterieren, bzw. anders gesagt solltest du alles vermeiden was in der Liste ein Hin- und Herspringen erfordert (da du ja auf dem Weg zu einem Knoten alle zwischenliegenden Knoten abklappern musst).
Damit fallen Varianten a), c) und e) schon mal weg.

Bei Variante d) verstehe ich nicht, wo diese unsortierte Binärstruktur herkommen soll, und warum die Reihenfolge darin "zufällig" sein soll. Scheint auch wegzufallen.

Damit bleibt eh nur mehr eine Variation von b) übrig.

Aus der Wahrscheinlichkeitstheorie heraus stellt sich die Frage, ob du Ziehen mit oder ohne Zurücklegen machen möchtest (wie schon oben von anderen Teilnehmern bereits angesprochen).
Weiters stellt sich die Frage, ob du die ursprüngliche Liste verändern möchtest oder nur die gezogenen Elemente extrahieren möchtest.
Um das ganze flexible bzgl. diesen Punkten aber trotzdem effizient handzuhaben, würde ich folgendes tun:

Nennen wird die Listelänge n, dann würde ich einen std::vector anlegen und dann:

-) falls Ziehen ohne Zurücklegen:
*) den vector mit den Werten 0 bis n-1 befüllen (diese stellen die Listen-Indices dar)
*) per std::random_shuffle() diese Indices zufällig umsortieren (hat nur die Komplexität std::distance(first, last) - 1, siehe https://en.cppreference.com/w/cpp/algorithm/random_shuffle.html; beachte, dass ein vector random-access-iterators bereitstellt)
*) aus diesem vector nur die ersten m Werte (m enspricht den gewünschten % von n) behalten (also die überschüssigen Indices entfernen)
*) diese verbliebenen Werte (= die Zielindices der zufällig ausgewählten Elemente in der Liste) aufsteigend sortieren
*) Beim ersten Zielindex im vector anfangen und das dazugehörige Listenelement aufsuchen und rauskopieren (in irgendeinen Container), dann mit dem zweiten Zielindex im vector fortfahren usw. Das ist ein one-pass über sowohl die list wie den vector. Der Container enthält dann die zufällig gewählten Werte.
*) ACHTUNG: Solltest du on-the-fly die gewählten Elemente aus der Liste entfernen wollen, dann musst du für die im vector gespeicherten Indices jeweils die Anzahl der bereits aus der Liste entfernten Elemente abziehen um den korrekten aktuellen Listen-Index zu erhalten!

-) falls Ziehen mit Zurücklegen:
*) den vector auf die Größe der insgesamt zu ziehenden Indices (das war m im Abschnitt oben) vor-alloziieren (vector::reseve()).
*) m-Mal Zufallszahlen zwischen 0 und n-1 ziehen (std::uniform_int_distribution()) und in den vector reinschreiben
*) den vector (= die Zielindices der zufällig ausgewählten Elemente in der Liste) aufsteigend sortieren, dann weiter wie im Abschnitt oben. Selbverständlich ergibt es bei Ziehen-mit-Zurücklegen keinen Sinn, überhaupt irgendein Element aus der Liste zu entfernen

Falls du mehr als 50% der Elemente in der Liste ziehen willst, kann man das Spiel so umdrehen, dass die im std::vector gespeicherten Zielindices nicht die zu behaltenden sondern die nicht zu behaltenden Indices darstellen. Dadurch kann der vector am Schluss maximal n/2 Werte enthalten, was das Sortieren und Abklappern dieses vectors etwas abkürzt (wird aber wohl nur bei extrem großen Datensätzen bzw. einer %-Zahl deutlich über 50 wohl was nenneswertes bringen).

 

[kali-hi]

Ok, wäre denn das richtig? Es scheint in O(n) zu laufen...

#include <cstdint>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

template < typename E >
    void select_n_elements(const vector < E > & in, vector < E > & out, uint32_t n) {
        srand((unsigned) time(0));
        set < uint32_t > indices = {};
        while (indices.size() < n) {
            int i = rand() % in.size();
            if (!indices.contains(i)) {
                indices.insert(i);
            }
        }
        vector < uint32_t > indices_2(indices.begin(), indices.end());
        sort(indices_2.begin(), indices_2.end());
        for (const uint32_t & i: indices_2) {
            out.push_back(in [i]);
        }
    }

int main() {
    vector < string > in = {
        "1",
        "2",
        "3",
        "4",
        "5",
        "6"
    };
    vector < string > out = {};
    select_n_elements(in, out, 3);
    for (auto s: out) {
        cout << s << endl;
    }
}

 

[simpsonsfan]

Was soll denn der Sinn von Zeilen 21+22 sein?

Und warum nicht einfach ein Indexarray (ich meine damit natürlich einen Vector) erstellen und mit std::range::shuffle eine Zufallspermutation erstellen? Dann überlässt du die ganze Arbeit der Standardbibliothek und brauchst nicht händiusch ein Set anzulegen.

 

[kali-hi]

Was soll denn der Sinn von Zeilen 21+22 sein?

Ich dachte, ich sortiere die Indices vorher nochmal, damit die Ergebnisliste auch gleich sortiert ist... Zudem dachte ich, dadurch könnte i-wie schneller durch die Eingabeliste gelaufen werden...

und mit std::range::shuffle eine Zufallspermutation erstellen?

Touché Da hast du recht

... aber wäre die Speicherplatzkomplexität dann nicht 2*n?

 

[firespot]

time(0) ist schlecht, denn wenn wenn der Code mehrmals in derselben Sekunde durchlaufen wird, produziert er (bei gleichen Input-Daten) immer dasselbe Ergebnis. Das hat dann herzlich wenig mit Zufall zu tun.

Bgzl. der while-Schleife in Zeile 15 wurde ja schon was gesagt. Abgesehen davon läufst du damit in Gefahr, in eine Fast-Endlos-Schleife rennen zu können (stelle dir vor was passieren wird, wenn in.size() == 1e9 und n = 1e9 - 1 sind ....).

Das Problem ist nicht schwierig zu lösen, muss aber von Grund auf durchdacht werden.

 

[kali-hi]

Na, dann schlag doch was besseres vor

Oder kommt man hier um Kompromisse nicht drum herum?

immer dasselbe Ergebnis

Das sehe ich anders, aber dazu müssten wir erst mal definieren, was ein "fairer" Zufall ist... Reicht einmaliges Mischen der Indices aus, oder vielleicht doch eher 10-mal? 🤔

 

[Piktogramm]

Na, dann schlag doch was besseres vor

Kann Eigenleistung negativ werden?
Edit: Zeit ist ein beschissener Seed, Quellen für einen gescheiten Seed stehen in der Dokumentation, wurden im Thread genannt.

Oder kommt man hier um Kompromisse nicht drum herum?

Nein, nie.

Das sehe ich anders, aber dazu müssten wir erst mal definieren, was ein "fairer" Zufall ist... Reicht einmaliges Mischen der Indices aus, oder vielleicht doch eher 10-mal? 🤔

Hör auf zu schwätzen, lies die Dokumentation!

... aber wäre die Speicherplatzkomplexität dann nicht 2*n?

Jain, es kommt drauf an, wie groß im Mittel die Strings aus L1 sind. In deinem Beispiel sind in L1 eigentlich nur Chars, im Indexvektor aber uInt32. Entsprechend ist der volle Index in deinem Beispiel immer größer als die Nutzdaten. Das Verhältnis verschiebt sich halt.

Ansonsten bleibt halt immer das Bilden von Batchen, wenn die Anforderung an Zufallsauswahl nicht zu hart ist.
Edit: Batchen.. blödes Eingedeutsche -.- "Batches" sind gemeint.

 

[JackForceOne]

Ich hatte das mit dem Zufall nur kurz erwähnt, weil der TE absichtlich (?) abstrakt von Datenstrukturen gesprochen hat. Wenn man natürlich von x86 ausgeht mit Linux Kernel, dann ist das Problem schon gelöst, aber da es ja um allgemeines effizientes zufälliges ziehen aus großen Mengen im Eingangspost ging, wollte ich es nicht unerwähnt lassen, dass man oft nicht (auf jeder Plattform) schnell genug Zufall erzeugen kann.

 

[firespot]

Die Indices einmalig durchmischen reicht vollkommen aus.

Aber wenn du stets denselben Random-Number-Generator (RNG) im SELBEN Zustand (Seed) und für DENSELBEN Zweck (spezifizierte Verteilung der zu ziehenden Zufallszahlen) nutzt, wird er immer DIESELBEN Zufallszahlen liefern. Und damit ist dann - bei wiederholter Nutzung - der Zufallseffekt komplett dahin. Stell dir vor beim Lotto würden jede Woche stets DIESELBEN "Zufalls"zahlen gezogen werden!

Typische Lösung: Den RNG nur EINMALIG im Programm mit seed initialisieren.

Statistisches Zusatzdetail:
rand() % n ist statistisch gesehen (typischerweise) nicht uniform verteilt, da der Bereich [RAND_MAX - n * int(RAND_MAX/n), RAND_MAX] typischerweise nicht die Range von 0 bis n-1 abdeckt.
Bsp: RAND_MAX = 10000, n = 9000 (ich weiß dass RAND_MAX in der Praxis nicht 10000 ist, hier gehts nur um die Illustration des statistischen Effekts):
Die Zahlen zwichen 0 und 1000 haben damit eine DOPPELT so hohe Wahrscheinlichkeit gezogen zu werden als die anderen, da sie sowohl bei einem rand()-Wert zwischen 0 und 1000 als auch einem zwischen 9000 und 10000 erfasst werden. Autsch.
Deshalb: Nutze die Zufallszahlen-Funktionen (Generators, distributions, functions, ect.) der Standardbibliothek!

Abgesehen davon achte bitte auf korrekte Terminologie und Verwendungszweck. Du hast in deinem Eingangs-Post von einer "Liste" gesprochen, was in C++ eine std::list. Die verhält sich aber teilweise grundlegend anders als ein std::deque oder ein std::vector, bgzl. allem möglichem (access, iterators, efficient insertion/deletion at front or end, memory consumption, block allocations ...). Nicht umsonst stellt die Standardbibliothek diverse Container bereit, weil jeder davon individuelle Stärken und Schwächen hat.
Der von mir im obigen Post beschriebene Algorithmus hat die Eigenschaft einer std::list berücksichtigt, aber dann wurde es in deinem Beispiel-Code plötzlich ein std::vector?
Beim Ziehen MIT Zurücklegen ist der Unterschied hier dann nämlich enorm, denn da kann man bei einem std::vector einfach per std::uniform_int_distribution() die Indizes ziehen und (via random-access) direkt auf das dazugehörige std::vector Elemente zugreifen. Das kann man sogar kompakt als Code Ein-Zeiler schreiben.
(Beim Ziehen OHNE Zurücklegen wird man trotzdem einen Hilfscontainer benötigen).