Probleme d'optimisation: tirage aléatoire sans remise.

[Argorate]

Bonjour,

Je suis actuellement entrain de voir pour la méthode, ou l'algorithme qui serait le plus rapide concernant le tirage au sort de n nombre dans un ensemble A de p nombre.
Le problème étant simplement que la fonction mt_rand() (ou même rand()) se fait "avec remise". (du moins de se que j'en sais)).

Donc la question serait, admettons qu'on est:
Ensemble A = {1, 2, 3...28, 29, 30}
et qu'on fasse une boucle qui doit tourner jusqu'à sortir 20 nombres différent de l'ensemble A.

Comment faire pour restreindre l'ensemble A en retirant les nombres qui sont sortie au tour de boucle précédente?

--------------------------------------------- Mauvaise Méthode ---------------------------------------------
Alors certains pourraient me dire, tu peux faire comme ça (voir-ci dessous):
Le problème de ce genre d'algorithme est qu'il y a beaucoup de tour de boucle qui ne serve à rien!
Car plus on tire des "bon" numéro, moins il y en a de disponible, plus les probabilité que le rand() trouve un nombre déjà tiré est grand => tour de boucle inutile augmente.

Code PHP :

<?php 

$i=0;

while($i<20)

{

$rand = mt_rand(1,30);



//si il y a rien dans la case <=> dispo

if($dispo[$rand]==0)

{

      $dispo[$rand] = 1; //on le rend indisponible

      $tab[] = $rand; // on conserve le nombre tiré

      $i++;

}

else $i--; //sinon on recommence

} 

[Seren]

Réponse bourrine.

Tu fais une boucle qui fait 100 000 fois la méthode 1 et 100 000 fois la méthode 2 et tu compares le temps d'execution.

Je suis pas sûr que ce soit exact dans tous les cas parce qu'il peut y avoir des phénomènes de mise en cache, mais ça donne une idée grossière.

[Holy]

Tout dépend du nombre de chiffres que tu veux pour ton nombre et du nombre de nombres (hem). Si la quantité de nombres que tu as besoin est peu élevée, tu peux taper dans le tas étant donné la probabilité de tomber plusieurs fois sur le même nombre.

Si la quantité de nombres dont tu as besoin est élevée, je te conseille de faire un array avec une série de nombre (range() ou array_fill() peuvent être utiles), tu fais un array_rand() qui sélectionne le nombre de valeurs définies dans ton tableau de manière aléatoire, et ça retourne un tableau avec les index (enfin suffit de lire la doc).

Je dis ça de tête donc j'ai pas d'idées précises quant aux performances. J'avais utilisé un système de ce type pour générer une grille de sudoku y a longtemps, et ça marchait plutôt bien.

[wild-D]

la mauvaise méthode n'est pas automatiquement mauvaise^^
tout dépend de la situation: si tu dois tirer 3 objet parmis 5 c'est vrai que c'est pas cool; mais si c'est 3 parmis 1M elle me semble même bien meilleure que tes autres propositions.

sérieusement imaginons que tu doives utiliser ta méthode 1 ou 2 avec un stock de 1M de choix (bon j'exagère un peu , mais c'est pour le principe)... ça va être lourd.

[Argorate]

Oui, Je suis d'accord!

Je parles dans un cas "restreint", cela s'adapte a la situation évidement.

Moi je parle de mon problème ^^

Donc vous vous feriez comment?

[Findel]

Moi je ferais ça :

Code :

$dispo= range(1, 30); // tableau de toutes les valeurs possibles
shuffle($dispo); // hop, c'est tout mélangé
$tab = array_chunk($dispo,20); // je garde que les 20 premiers, c'est mes 20 tirages sans remise

Edit : ah ben c'est ta "méthode 2" on dirait

[Argorate]

C'est exact, c'est la méthode 2, mais niveau perf, c'est plus rapide?

J'avoue que n'étant pas chez moi, je peux pas utiliser le serveur de la boite pour faire un test a grande échelle^^

[Anthor]

Pourquoi un algorithme non compilé serait-il plus rapide qu'une fonction native ?

Je pense que la c'est surtout la question à te poser ^^

[Wells]

hum perso pour mon moteur de combat je fait ceci:

Code PHP :

<?php 

$arme_qui_tire=array_rand($armes_restant);

[........]

unset($armes_restant[$arme_qui_tire]); 

[gameprog2]

vous parlez de code ou d'algorythme c'est pas pareil hein^^
1) Le probleme énonce : Comment faire un tirage de 20 valeurs différentes incluses dans un ensemble de valeurs sans que chaque valeur tirée soit répétée.
2) L'algo dit : D'un ensemble on supprime l'élément qui a été tiré par le hasard

3) L'application de l'algo en code se fait de différentes manières, qu'on voit dans vos réponses d'ailleurs.