Jak działa losowe odtwarzanie losowe w Pythonie?

Jak losowo działa losowo w Pythonie?

Pytam, ponieważ działa bardzo szybko. Kiedy próbuję pisać losowo, działa to 1 minutę dla elementu 10 ^ 6, ale tasowanie Pythona robi to w 8 sekund?

Python random.shuffleużywa tasowania Fishera-Yatesa , który działa w czasie O (n) i udowodniono, że jest idealnym tasowaniem (przy założeniu dobrego generatora liczb losowych).

Powtarza tablicę od ostatniej do pierwszej pozycji, przełączając każdą pozycję z pozycją o losowym indeksie poniżej.

Podstawowy proces tasowania Fishera – Yatesa jest podobny do losowego wybierania ponumerowanych biletów z kapelusza lub kart z talii, jeden po drugim, aż nie będzie już więcej. Ten konkretny algorytm zapewnia sposób wykonywania tego numerycznie w wydajny i rygorystyczny sposób, który odpowiednio wykonany gwarantuje obiektywny wynik ...

Nowoczesne ... rozwiązanie polega na przenoszeniu „trafionych” liczb na koniec listy poprzez zamianę ich z ostatnią nieotkniętą liczbą przy każdej iteracji. Zmniejsza to złożoność czasową algorytmu do O (n), w porównaniu do O (n ² ) dla implementacji naiwnej. Ta zmiana daje następujący algorytm (dla tablicy zerowej).

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]