JeuWeb - Crée ton jeu par navigateur
Probleme d'optimisation: tirage aléatoire sans remise. - Version imprimable

+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Discussions, Aide, Ressources... (https://jeuweb.org/forumdisplay.php?fid=38)
+--- Forum : Programmation, infrastructure (https://jeuweb.org/forumdisplay.php?fid=51)
+--- Sujet : Probleme d'optimisation: tirage aléatoire sans remise. (/showthread.php?tid=3578)

Pages : 1 2 3


Probleme d'optimisation: tirage aléatoire sans remise. - Argorate - 23-01-2009

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
}


--------------------------------------------- Méthode 1 ---------------------------------------------
Cela consiste à réduire l'ensemble A en réduisant le nombre de case du tableau, en suppriment les éléments déjà tirés.

Code PHP :
<?php 
$dispo
= array(1,2,3....28,29,30);//on remplirais notre tableau différemment si on le coder vraiment.

$i=0;
while(
$i<20)
{
$rand = mt_rand(1, count($dispo)); //on tire entre 1 et la taille de notre tableau.
$tab[] = $rand; // on conserve le nombre tiré

$a = $rand;
while(
$a<=count($dispo))
{
if(
$a == count($dispo)) unset($dispo[$a]); //on détruit le dernier élément du tableau pour avoir le bon nombre d'élément au prochain tour de boucle
else $dispo[$a] = $dispo[$a+1]; //on décale notre tableau vers la gauche
$a++;
}
$i++;
}

--------------------------------------------- Méthode 2 ---------------------------------------------
Le principe serait de prendre les 20 premier élément d'un tableau qui en comprend 30. Pour assuré le coté aléatoire de la chose, on utiliserait:
Citation :Shuffle

(PHP 4, PHP 5)

shuffle — Mélange les éléments d'un tableau
Autrement dit on mélange l'ordre dans notre tableau et on prend que les 20 premier.

C'est un ami qui m'en a parlé, je ne connais même pas la fonction, donc pas de code a montrer, mais vous avez compris le principe.

--------------------------------------------- Conclusion ---------------------------------------------

Je ne sais pas si il existe déjà une fonction qui fait se que je recherche, ni quel algo est le meilleur, pour moi c'est la méthode 1 qui me semblerais la plus pertinente, mais peut être y a t-il encore mieux?


EDIT: L'ordre n'a aucune importance, qu'on tire le "1" en premier ou en dernier, cela n'a pas d'importance.
Pas besoin d'introduire la notion d'ordre dans vos réponses donc, merci Smile


RE: Probleme d'optimisation: tirage aléatoire sans remise. - Seren - 23-01-2009

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.


RE: Probleme d'optimisation: tirage aléatoire sans remise. - Holy - 23-01-2009

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.


RE: Probleme d'optimisation: tirage aléatoire sans remise. - wild-D - 23-01-2009

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 Tongue, mais c'est pour le principe)... ça va être lourd.


RE: Probleme d'optimisation: tirage aléatoire sans remise. - Argorate - 23-01-2009

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?


RE: Probleme d'optimisation: tirage aléatoire sans remise. - Findel - 23-01-2009

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 Smile


RE: Probleme d'optimisation: tirage aléatoire sans remise. - Argorate - 23-01-2009

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^^


RE: Probleme d'optimisation: tirage aléatoire sans remise. - Anthor - 23-01-2009

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

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


RE: Probleme d'optimisation: tirage aléatoire sans remise. - Wells - 23-01-2009

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]);



RE: Probleme d'optimisation: tirage aléatoire sans remise. - gameprog2 - 23-01-2009

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.