Ich habe ein Array, A = [a1,a2,a3,...aP] mit der Größe P . Ich muss q Elemente aus Array A probieren.
Ich habe vor, eine Schleife mit q Iterationen zu verwenden und bei jeder Iteration zufällig eine Elemen- te von A auszuwählen. Aber wie kann ich sicherstellen, dass die ausgewählte Zahl bei jeder Iteration anders ist?
Die anderen Antworten beinhalten das Mischen des Arrays, das O(n) ist.
Es bedeutet, das ursprüngliche Array zu ändern (destruktiv) oder das ursprüngliche Array zu kopieren (speicherintensiv).
Der erste Weg, den Speicher effizienter zu machen, besteht darin, das Original Array nicht zu mischen, sondern ein Array von Indizes zu mischen.
%Vor%Es ist zumindest unabhängig vom Inhalt des @deck, aber es ist immer noch O (nlogn) Leistung und O (n) Speicher.
Ein effizienterer Algorithmus (nicht unbedingt schneller, hängt nun davon ab, wie groß Ihr Array ist) ist, jedes Element des Arrays zu betrachten und zu entscheiden, ob es in das Array übergeht. Dies ist vergleichbar mit Sie wählen eine zufällige Zeile aus einer Datei aus, ohne die gesamte Datei in den Speicher einzulesen , wobei jede Zeile eine 1 / N-Chance hat, ausgewählt zu werden, wobei N die Zeilennummer ist. Die erste Zeile hat also eine Chance von 1/1 (sie wird immer ausgewählt). Der nächste hat eine 1/2. Dann 1/3 und so weiter. Jede Auswahl überschreibt die vorherige Auswahl. Dies führt dazu, dass jede Zeile eine Chance von 1 / total_lines hat.
Sie können es sich selbst erarbeiten. Eine einzeilige Datei hat eine Chance von 1/1, sodass die erste Zeile immer ausgewählt wird. Eine zweizeilige Datei ... die erste Zeile hat eine 1/1, dann eine Chance von 1/2, zu überleben, was 1/2 ist, und die zweite Zeile hat eine Chance von 1/2. Für eine dreizeilige Datei ... hat die erste Zeile eine Chance von 1/1, ausgewählt zu werden, und dann eine Überlebenschance von 1/2 * 2/3, die 2/6 oder 1/3 ist. Und so weiter.
Der Algorithmus ist O (n) für die Geschwindigkeit, er durchläuft einmal ein ungeordnetes Array und verbraucht nicht mehr Speicher als zum Speichern der Picks benötigt wird.
Mit ein wenig Modifikation funktioniert das für mehrere Picks. Statt einer 1/$position Chance ist es $picks_left / $position . Jedes Mal, wenn eine Auswahl erfolgreich ist, verringern Sie $ picks_left. Du arbeitest von der hohen Position zur niedrigen. Im Gegensatz zu früher überschreiben Sie nicht.
Dies ist wie perl5i seine Pick-Methode implementiert (kommt als nächstes Freigabe).
Um zu verstehen, warum dies funktioniert, nehmen Sie das Beispiel, indem Sie 2 aus einer 4-Elemente-Liste auswählen. Jeder sollte eine Chance von 1/2 haben, ausgewählt zu werden.
%Vor%Einfach genug. Das nächste Element hat eine Chance von 1/2, dass ein Element bereits ausgewählt wurde. In diesem Fall sind die Chancen 1/3. Ansonsten sind die Chancen 2/3. Mathe machen ...
%Vor%Next hat eine 1/4 Chance, dass beide Elemente bereits ausgewählt sind (1/2 * 1/2), dann hat es keine Chance; 1/2 Chance, dass nur eine ausgewählt wird, dann ist es 1/2; und das verbleibende 1/4, dass keine Gegenstände gepflückt werden, in welchem Fall es 2/2 ist.
%Vor%Schließlich, für den letzten Gegenstand, gibt es eine 1/2 der vorherigen nahm die letzte Auswahl.
%Vor%Nicht gerade ein Beweis, aber gut um sich davon zu überzeugen, dass es funktioniert.
Von perldoc perlfaq4 :
Wie mische ich ein Array zufällig?
Wenn Sie Perl 5.8.0 oder höher installiert haben oder wenn Sie dies getan haben Scalar-List-Utils 1.03 oder später installiert, können Sie sagen:
%Vor%Wenn nicht, können Sie einen Fisher-Yates Shuffle verwenden.
%Vor%
Sie können auch List::Gen verwenden:
Sie können den Fisher-Yates Shuffle-Algorithmus verwenden, um Ihr Array nach dem Zufallsprinzip zu permutieren und dann zu verwenden eine Scheibe der ersten q Elemente. Hier ist Code von PerlMonks :
%Vor% Sie können dies wahrscheinlich optimieren, indem Sie die Zufallswiedergabe anhalten, nachdem q zufällige Elemente ausgewählt wurden. (So wie dies geschrieben ist, möchten Sie die letzten q Elemente haben.)
Tags und Links perl