La meilleure façon de générer un nombre aléatoire

[kizakoo]

Bonsoir, j'ai une petite question: quelle est la manière la plus aléatoire de générer un chiffre à partir d'un tableau:

- choisir aléatoirement un chiffre dans le tableau
- trier aléatoirement le tableau puis choisir le premier élément
-----

[pm42]

- choisir aléatoirement un chiffre dans le tableau

Simple, rapide et efficace.

- trier aléatoirement le tableau puis choisir le premier élément

Je ne connais pas le concept de tri aléatoire qui semble oxymoronique mais si on suppose que tu veux dire "mélanger le tableau", cela va être beaucoup plus lent que la 1ère méthode pour ne rien apporter de plus.
Le nombre de mélanges qu'il faudrait faire pour que ce soit aléatoire mériterait d'être calculé parce que je pense que ce n'est pas négligeable.

[minushabens]

pour obtenir une permutation aléatoire d'une liste (un tableau) on tire l'indice du premier élément, puis celui du second, etc. donc si c'est pour ensuite choisir le premier élément de la liste permutée, c'est exactement la même chose que choisir aléatoirement un élément de la liste, sauf que ça prend plus de temps.

[pm42]

pour obtenir une permutation aléatoire d'une liste (un tableau) on tire l'indice du premier élément, puis celui du second, etc. donc si c'est pour ensuite choisir le premier élément de la liste permutée, c'est exactement la même chose que choisir aléatoirement un élément de la liste, sauf que ça prend plus de temps.

Oui mais la gestion des collisions possibles fait qu'en pratique, l'algorithme est plus coûteux que cela soit en CPU, soit en mémoire, soit les 2.

[A voir en vidéo sur Futura]

[kizakoo]

Oui mais la gestion des collisions possibles fait qu'en pratique, l'algorithme est plus coûteux que cela soit en CPU, soit en mémoire, soit les 2.

Merci de cette réponse pm42, pouvez-vous la developper un peu ?
merciii

[pm42]

Merci de cette réponse pm42, pouvez-vous la developper un peu ?

Tu mélanges ton tableau en déterminant où tu vas envoyer le 1er élément. Pour cela tu tires un indice aléatoire.
Ensuite, tu détermines où envoyer le 2nd élément. Mais il y a une chance que tu envoies celui ci sur le même indice que celui du 1er.

Donc il faut que d'une façon ou d'une autre, tu gardes la trace des indices que tu as déjà tiré pour être sur de ne pas envoyer 2 éléments à la même place.

[goaoute]

tu tires un indice aléatoire..

Hum...Et tu le sort d'où l'aléatoire de l'indice tiré ?

[pm42]

Hum...Et tu le sort d'où l'aléatoire de l'indice tiré ?

Perso, d'une carte PCI qui mesure un phénomène quantique. Mais il y a d'autres méthodes bien sur, plus simples. Tu peux lire le chapitre dédié du Knuth en introduction au sujet.
Tout dépend du besoin.

[kizakoo]

Tu mélanges ton tableau en déterminant où tu vas envoyer le 1er élément. Pour cela tu tires un indice aléatoire.
Ensuite, tu détermines où envoyer le 2nd élément. Mais il y a une chance que tu envoies celui ci sur le même indice que celui du 1er.

Donc il faut que d'une façon ou d'une autre, tu gardes la trace des indices que tu as déjà tiré pour être sur de ne pas envoyer 2 éléments à la même place.

Justement je trie mon tableau à partir du dernier élèment. C'est -à-dire:
considérons le tableau: 0 1 2 3 4 5 6 7 8 9
pour 9 je choisis un indice aléatoire dans 0..8 puis je place cet indice dans la dernière case ensuite je choisis pour 8 un indice aléatoire parmi 0 1 2 3 4 5 6 7 9 et ainsi de suite. donc le cas où le meme indice sera choisi ne se présente pas. Sinon en terme de mémoire et de complexité ?

[LeMulet]

Bonsoir, j'ai une petite question: quelle est la manière la plus aléatoire de générer un chiffre à partir d'un tableau:

C'est de lire le tableau séquentiellement, qui a été préalablement initialisé avec des nombres (et pas des chiffres) aléatoires, du début à la fin, puis de boucler.

Si le tableau est assez grand, le fait que la série unique utilisée soit constante ne devrait pas poser de problème pour certaines applications.
Par exemple, si l'application contient beaucoup de "bruit" (le moment du tirage est complexe), et que plusieurs sous-systèmes de ce type produisent également des tirages (et donc s'intercalent dans la série...) ça permet peut-être même d'obtenir un système de tirage aléatoire plus efficace que la fonction "random" classiquement implémentée dans tous les langages dignes de ce nom (qui elle ne se base pas sur un tableau, si je ne m'abuse)
Par exemple un minecraft avec beaucoup de "bestioles" qui employent des random peut employer un système de ce type (tableau pré-initialisé), sans produire d'effets de répétition.

[pm42]

Justement je trie mon tableau à partir du dernier élèment. C'est -à-dire:
considérons le tableau: 0 1 2 3 4 5 6 7 8 9
pour 9 je choisis un indice aléatoire dans 0..8 puis je place cet indice dans la dernière case ensuite je choisis pour 8 un indice aléatoire parmi 0 1 2 3 4 5 6 7 9 et ainsi de suite. donc le cas où le meme indice sera choisi ne se présente pas. Sinon en terme de mémoire et de complexité ?

Déjà en faisant ça et si j'ai bien compris, tu ne fais pas de l'aléatoire puisque tu t'interdis d'avoir 9 en 9ème position, etc.
Le plus simple pour ce que tu veux, c'est la méthode suivante : https://fr.wikipedia.org/wiki/Mélange_de_Fisher-Yates

Certaines librairies te le fournisse par défaut comme random.shuffle() en python par ex.

[pm42]

C'est de lire le tableau séquentiellement, qui a été préalablement initialisé avec des nombres (et pas des chiffres) aléatoires, du début à la fin, puis de boucler.

Ce n'est pas le besoin.

Si le tableau est assez grand, le fait que la série unique utilisée soit constante ne devrait pas poser de problème pour certaines applications.

Quelle "série unique" ? Pourquoi est elle devenue "constante" alors qu'on parlait d'aléatoire ?
Et si comme on peut le supposer, le problème est avec les générateurs pseudo-aléatoires, c'est le contraire : si le tableau est grand, on risque les problèmes...

Par exemple, si l'application contient beaucoup de "bruit" (le moment du tirage est complexe), et que plusieurs sous-systèmes de ce type produisent également des tirages (et donc s'intercalent dans la série...) ça permet peut-être même d'obtenir un système de tirage aléatoire plus efficace que la fonction "random" classiquement implémentée dans tous les langages dignes de ce nom (qui elle ne se base pas sur un tableau, si je ne m'abuse)
Par exemple un minecraft avec beaucoup de "bestioles" qui employent des random peut employer un système de ce type (tableau pré-initialisé), sans produire d'effets de répétition.

J'hésite entre incompréhensible et faux mais c'est dans doute les 2.

Mais surtout, c'est réinventer la roue. Les environnements de programmation moderne fournissent du vrai aléatoire (genre /dev/random) ou des librairies très bien conçues pour que le pseudo-aléatoire soit de qualité.
Et vu son impact en cryptographie, le sujet a été largement étudié.