Wie funktioniert Python Random Shuffle?

11

Wie funktioniert Shuffle from Random in Python?

Ich frage, weil es sehr schnell funktioniert. Wenn ich versuche, Shuffle zu schreiben, funktioniert es 1 Minute für 10 ^ 6 Elemente, aber Python Shuffle macht das in 8 Sekunden?

Paweł Szymański
quelle
14
Warum nicht einfach den Quellcode anschauen ?
Faultier
4
Der beste Shuffle-Algorithmus ist der Fisher-Yates- Shuffle. Er läuft in O (n) -Zeit und ist nachweislich ein perfekter Shuffle (unter der Annahme einer guten
Ratschenfreak
1
@ratchetfreak: Python verwendet Fisher-Yates.
Martijn Pieters
1
Was ist Ihr Algorithmus für das Mischen?
Whatsisname
@sloth, übrigens, Raymond Hettinger schlug 2011 eine universelle Praxis für die Verknüpfung von Dokumenten mit dem Quellcode vor .
Cristian Ciupitu

Antworten:

17

Pythons random.shuffleverwendet das Fisher-Yates-Shuffle , das in O (n) -Zeit ausgeführt wird und sich als perfektes Shuffle erwiesen hat (unter der Annahme eines guten Zufallszahlengenerators).

Es iteriert das Array vom letzten zum ersten Eintrag und wechselt jeden Eintrag mit einem Eintrag an einem zufälligen Index darunter.

Der grundlegende Vorgang des Fisher-Yates-Mischens ähnelt dem zufälligen Auswählen nummerierter Tickets aus einem Hut oder Karten aus einem Deck nacheinander, bis keine mehr übrig sind. Der spezifische Algorithmus bietet eine Möglichkeit, dies auf effiziente und strenge Weise numerisch zu tun, was bei richtiger Ausführung ein unvoreingenommenes Ergebnis garantiert ...

Die moderne ... Lösung besteht darin, die "getroffenen" Zahlen an das Ende der Liste zu verschieben, indem sie bei jeder Iteration gegen die letzte nicht getroffene Zahl ausgetauscht werden. Dies reduziert die zeitliche Komplexität des Algorithmus auf O (n) im Vergleich zu O (n 2 ) für die naive Implementierung. Diese Änderung ergibt den folgenden Algorithmus (für ein Array auf Nullbasis).

To shuffle an array a of n elements (indices 0..n-1):
  for i from n  1 downto 1 do
       j  random integer with 0  j  i
       exchange a[j] and a[i]
Mücke
quelle