Comment mélanger à partir de travaux aléatoires en Python?
Je demande parce que ça marche très vite. Lorsque j'essaie d'écrire shuffle, cela fonctionne 1 minute pour l'élément 10 ^ 6, mais Python shuffle le fait en 8 secondes?
Pourquoi ne pas simplement regarder le code source ?
paresseux
4
le meilleur algorithme de shuffle est le shuffle de fisher-yates , il fonctionne en temps O (n) et s'est avéré être un shuffle parfait (en supposant une bonne source aléatoire)
Python random.shuffleutilise le shuffle de Fisher-Yates , qui s'exécute en temps O (n) et s'est avéré être un shuffle parfait (en supposant un bon générateur de nombres aléatoires).
Il itère le tableau de la dernière à la première entrée, en commutant chaque entrée avec une entrée à un index aléatoire en dessous.
Le processus de base du brassage de Fisher – Yates est similaire à la prise au hasard de billets numérotés dans un chapeau ou de cartes dans un jeu, l'un après l'autre jusqu'à ce qu'il n'en reste plus. Ce que l'algorithme spécifique fournit est une façon de le faire numériquement d'une manière efficace et rigoureuse qui, correctement effectuée, garantit un résultat non biaisé ...
La solution moderne ... consiste à déplacer les numéros "frappés" à la fin de la liste en les échangeant avec le dernier numéro non frappé à chaque itération. Cela réduit la complexité temporelle de l'algorithme à O (n), par rapport à O (n 2 ) pour l'implémentation naïve. Cette modification donne l'algorithme suivant (pour un tableau à base zéro).
To shuffle an array a of n elements (indices 0..n-1):for i from n −1 downto 1do
j ← random integer with0≤ j ≤ i
exchange a[j]and a[i]
Réponses:
Python
random.shuffleutilise le shuffle de Fisher-Yates , qui s'exécute en temps O (n) et s'est avéré être un shuffle parfait (en supposant un bon générateur de nombres aléatoires).Il itère le tableau de la dernière à la première entrée, en commutant chaque entrée avec une entrée à un index aléatoire en dessous.
la source