Wie im Titel möchte ich den Shuffle-Algorithmus nach Knuth-Fisher-Yates verwenden, um N zufällige Elemente aus einer Liste auszuwählen, aber ohne List.toArray zu verwenden und die Liste zu ändern. Hier ist mein aktueller Code:
%Vor%Es verwendet list.toArray (), um ein neues Array zu erstellen, damit die ursprüngliche Liste nicht geändert wird. Allerdings ist mein Problem jetzt, dass meine Liste sehr groß sein kann, 1 Million Elemente haben kann. Dann ist list.toArray () zu langsam. Und mein n könnte zwischen 1 und 1 Million liegen. Wenn n klein ist (etwa 2), ist die Funktion sehr ineffizient, da sie list.toArray () für eine Liste von 1 Million Elementen noch ausführen muss.
Kann jemand helfen, den obigen Code zu verbessern, damit er effizienter mit großen Listen umgehen kann? Danke.
Hier nehme ich an, dass Knuth-Fisher-Yates shuffle der beste Algorithmus ist, um n zufällige Elemente aus einer Liste auszuwählen. Habe ich recht? Ich wäre sehr froh, wenn es andere Algorithmen gäbe, die besser sind als Knuth-Fisher-Yates Shuffle, um die Arbeit in Bezug auf die Geschwindigkeit und die Qualität der Ergebnisse zu erledigen (garantiere echte Zufälligkeit).
Aktualisierung:
Hier sind einige meiner Testergebnisse:
Wenn Auswahl n aus 1000000 Elementen.
Wenn n & lt; 1000000/4 der schnellste Weg ist, die Bitmap-Funktion von Daniel Lemire zu verwenden, um zuerst n zufällige ID auszuwählen, dann hole die Elemente mit diesen IDs:
%Vor%Das genNBitSet verwendet den Code generateUniformBitmap von Ссылка
Wenn n & gt; 1000000/4 ist, ist die Reservoir-Probenahme-Methode schneller.
Also habe ich eine Funktion zum Kombinieren dieser beiden Methoden erstellt.
Sie suchen wahrscheinlich nach etwas wie Resorvoir Sampling .
Beginne mit einem initialen Array mit ersten k -Elementen und modifiziere es mit neuen Elementen mit abnehmenden Wahrscheinlichkeiten:
Java-ähnlicher Pseudocode:
%Vor%Dies erfordert einen einzigen Durchlauf der Daten mit sehr billigen Ops bei jeder Iteration, und der Speicherplatzverbrauch ist linear mit der erforderlichen Ausgabegröße.
Wenn n im Vergleich zur Länge der Liste sehr klein ist, nehmen Sie eine leere Menge von Ints und fügen Sie einen zufälligen Index hinzu, bis die Menge die richtige Größe hat.
Wenn n mit der Länge der Liste vergleichbar ist, machen Sie dasselbe, aber geben Sie dann Elemente in der Liste zurück, die keine Indizes in der Gruppe enthalten.
Im mittleren Bereich können Sie durch die Liste iterieren und nach dem Zufallsprinzip Elemente auswählen, basierend darauf, wie viele Elemente Sie gesehen haben und wie viele Elemente Sie bereits zurückgegeben haben. Im Pseudocode, wenn Sie k Elemente von N wollen:
%Vor%Hier gibt random (x) eine Zufallszahl zwischen 0 (inklusive) und x (exklusiv) zurück.
Dies erzeugt eine gleichmäßig zufällige Stichprobe von k Elementen. Sie können auch einen Iterator erstellen, um zu vermeiden, dass die Ergebnisliste zum Speichern von Speicher erstellt wird, vorausgesetzt, dass die Liste unverändert bleibt, wenn Sie darüber iterieren.
Durch das Profiling können Sie den Übergangspunkt bestimmen, an dem es sinnvoll ist, von der naiven Methode der Satzbildung zur Iterationsmethode zu wechseln.
Nehmen wir an, Sie können n zufällige Indizes aus m paarweise disjunkten generieren und sie dann effizient in der Auflistung nachschlagen. Wenn Sie die Reihenfolge der Elemente nicht zufällig benötigen, können Sie einen Algorithmus verwenden, der auf Robert Floyd basiert.
%Vor% Wenn die Reihenfolge zufällig sein soll, können Sie Fisher-Yates ausführen, wobei Sie anstelle eines Arrays ein HashMap verwenden, das nur die Zuordnungen speichert, bei denen der Schlüssel und der Wert unterschiedlich sind. Unter der Annahme, dass Hashing konstante Zeit ist, sind beide dieser Algorithmen asymptotisch optimal (obwohl klar, wenn Sie den größten Teil des Arrays zufällig Stichprobe dann gibt es Datenstrukturen mit besseren Konstanten).
Nur aus praktischen Gründen: Ein MCVE mit einer Implementierung des Resorvoir Sampling von amit vorgeschlagen ( mögliche upvotes sollten zu ihm gehen (Ich hack 'nur ein wenig Code))
Es scheint in der Tat ein Algorithmus zu sein, der die Fälle gut abdeckt, in denen die Anzahl der Elemente niedrig im Vergleich zur Listengröße ist, und die Fälle die Anzahl der Elemente ist hoch im Vergleich zur Listengröße (vorausgesetzt, dass die Eigenschaften auf der Zufälligkeit des Ergebnisses, die auf der Wikipedia-Seite angegeben sind, korrekt sind).
%Vor% Wenn n viel kleiner als die Größe ist, könnten Sie diesen Algorithmus verwenden, der leider quadratisch mit n ist, aber hängt von der Größe des Arrays ab.
Beispiel mit size = 100 und n = 4.
In Kürze wählst du aus den verbleibenden Zahlen aus und erfährst dann, welche Nummer du ausgewählt hast. Ich würde dafür die Linkliste verwenden, aber vielleicht gibt es bessere Datenstrukturen.