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


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

Anthor : a quel fonction native fait tu références, j'ai pas bien compris?

Wells: Effectivement c'est une méthode peut être meilleur que la "méthode 1", et la fonction array_rand() serait plus rapide que la "méthode 1" niveau perf?

gameprog2 : L'algorithme en algorithme n'est pas intéressant, on parle en code, et php de préférence^^ Je demande justement le meilleur algo php (à comprendre le plus rapide/optimisé) concernant le problème exposé.


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

(26-01-2009, 12:07 PM)Argorate a écrit : gameprog2 : L'algorithme en algorithme n'est pas intéressant, on parle en code, et php de préférence^^ Je demande justement le meilleur algo php (à comprendre le plus rapide/optimisé) concernant le problème exposé.

le problème c'est que tu n'a pas une solution optimal pour tous les cas de figures (sauf si t'as un seule cas ton 20 objet à tirer sur 30; auquel cas ben tu fait un rapide benchmark et t'auras ta réponse^^)... Donc faudrait limite implémenter une version qui sélectionne l'algo le plus pertinent en fonction de tes inputs.


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

Je pense que c'est effectivement ce que je vais faire, mais c'était pour savoir si il existait des méthode ou fonction que je ne connaissais pas, maintenant que j'ai eu quelques proposition supplémentaire, je vais pouvoir tester le plus pertinent pour mon cas.

Merci a tous Wink


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

gameprog2 -> Je ne suis pas d'accord, ce sont 3 algorithmes différents !
Qu'ils utilisent le mot Algorithme en parlant de sa retranscryption en un langage (ici PHP) n'est pas si grave car on comprend très bien.
Il ne connait pas l'algorithmie alors il utilise ce langage pour la réprésenter, ce qui est, je pense, valable et compréhensible.

Argorate -> Il existe encore surement des centaines de méthodes plus ou moins dérivés de celles-là mais elles restent les plus efficaces.
Par contre dans ta méthode 1, je ne vois pas pourquoi tu conserves le nombre tiré si tu le supprime de ton tableau. Je ne vois pas non plus pourquoi 2 boucles...
Ton:
$rand = mt_rand(1, count($dispo));
Est très mal placé !
Voici une version correcte de cette méthode:
Code PHP :
<?php 
$NbDispo
= range(1, 30); // tableau de toutes les valeurs possibles
$NbTires = array();
for(
$i=1; $i<=20; $i++) {
$a = array_rand($NbDispo);
$NbTires[] = $a;
unset(
$NbDispo[array_search($a, $NbDispo)]);
}

Mais Perso, j'aurais plutot utilisé cette méthode
Code PHP :
<?php 
$NbDispo
= range(1, 30); // tableau de toutes les valeurs possibles
$NbTires = array_rand($NbDispo, 20); //On tire 20 nombres aléatoirement

Ou si, on ne sait pour quelle raison, tu ne l'aimes pas, je te conseille aussi la méthode 2 gentiment finalisé par Findel !


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

Effectivement je me suis trompé, j'ai mis le rand avant la boucle -_-' j'ai éditer. Merci Wink

Sinon, pour te répondre "pourquoi je conserve la valeur que je supprime du tableau?" C'est tout simplement que c'est le but même de l'algorithme^^
De tirer 20 nombres aux hasards, mais faut-il encore que je puisse les conserver non? Big Grin

Quand a la deuxième boucle elle sert au décalage du tableau:
On prend un l'élément se trouvant a l'indice i+1 et le place a l'indice i (qui est le chiffre tiré, donc on peut écrire par dessus, puisqu'on veux l'effacer), je décale ainsi tout mon tableau d'un rang a gauche et je supprime la dernière case qui est alors devenu un doublon.

On a, au départ:
--------------
|1|2|3|4|5|6|
--------------
le rand sort : 3

alors je décale:
--------------
|1|2|4|4|5|6|
--------------
Puis encore:
--------------
|1|2|4|5|5|6|
--------------
Jusqu'au bout:
--------------
|1|2|4|5|6|6|
--------------
Et enfin je détruit la dernière case:
------------
|1|2|4|5|6|
------------

Moi se qui me dérange avec :

Citation :$NbDispo = range(1, 30); // tableau de toutes les valeurs possibles
$NbTires = array_rand($NbDispo, 20); //On tire 20 nombres aléatoirement

C'est que je ne connais pas l'algo de ces fonctions, donc difficiles de savoir si c'est plus optimiser, donc j'en reviens a dire qu'il faudra que je fasse une série de test. Smile


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

Ce sont des fonctions natives, que tu connaisses leur Algo ne te servira pas à grand chose car je crois qu'elles sont programmées en un langage de plus bas niveau, donc plus rapide...
Fais tes benchmark, y'a des topics avec des scripts de benchmark tout fait sur le forum.


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

Voici les résultats obtenus avec le serveur de mon travail, donc on peut supposé que les résultats son sans doute un peu faussé car on doit être 2 ou 3 sur le serveur. Mais la différence est tellement notable qu'il n'y a pas de doute:
Voilà se que j'ai obtenue comme résultat pour 1 000 000 de test par méthode:

Citation :Methode 1: Temps moyen : 0.002 463 416 217 09 secondes (Temps Exec. 2463.41621709secondes)

Methode 2: Temps moyen : 0.000 034 199 709 653 9 secondes Temps Exec. 34.1997096539secondes)

Methode 3: Temps moyen : 0.000 029 232 471 94 29 secondes (Temps Exec. 29.2324719429secondes)

Methode 4: Temps moyen : 0.000 172 626 668 93 secondes(Temps Exec. 172.62666893secondes)

Voici le code des methodes tester:

Code PHP :
<?php 
function methode1()
{
$time = microtime(true);
$dispo= range(1, 30);
$i=0;
while(
$i<20)
{
$rand = mt_rand(1, count($dispo)); //on tire entre 1 et la taille de notre tableau.

$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++;
}
$time2 = microtime(true);
$time = $time2 - $time;

return
$time;
}

function
methode2()
{
$time = microtime(true);

$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

$time2 = microtime(true);
$time = $time2 - $time;

return
$time;
}

function
methode3()
{
$time = microtime(true);

$NbDispo = range(1, 30);
$NbTires = array_rand($NbDispo, 20);

$time2 = microtime(true);
$time = $time2 - $time;

return
$time;
}

function
methode4()
{
$time = microtime(true);
$i=0;
$dispo = array_fill(1, 30, 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
$i++;
}
}
$time2 = microtime(true);
$time = $time2 - $time;

return
$time;
}

$methode=1; $nb_boucle = 1000000;
while(
$methode<5)
{
$i=1; $resultat=0; $func = 'methode'.$methode;
while(
$i<=$nb_boucle)
{
$resultat += $func();
$i++;
}
echo
'Methode '.$methode.': Temps moyen : '.($resultat/$nb_boucle).' secondes (Temps Exec. '.$resultat.'secondes)<br><br>';
$methode++;
}

On peut donc dire que tu avais raison IGstaff, c'est bien l'array_rand() qui semble le plus approprié ici. Wink

Merci a tous.


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

Dingue !

J'y aurais pas cru. Merci d'avoir mis le code source. j'essayerais tantôt avec d'autres valeurs de tests ...

kéké


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

Rectification qui m'a était suggéré sur IRC (oué je fais un peu de pub)
Toujours la plus mauvaise, mais nettement mieux cependant:
Citation :Methode 1: Temps moyen : 0.000 619 438 126 564 secondes (Temps Exec. 619.438126564secondes)

avec $taille_tab = count($dispo); qui évite de faire plusieurs count() dans la boucle qui ralentit énormément...
Code PHP :
<?php 
function methode1()
{
$time = microtime(true);
$dispo= range(1, 30);
$i=0;
while(
$i<20)
{
$taille_tab = count($dispo);
$rand = mt_rand(1, $taille_tab); //on tire entre 1 et la taille de notre tableau.

$a = $rand;
while(
$a<=$taille_tab)
{
if(
$a == $taille_tab) 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++;
}
$time2 = microtime(true);
$time = $time2 - $time;

return
$time;
}

Conclusion/Résumé:

Citation :Methode 1: Temps moyen : 0.002 463 416 217 09 secondes (Temps Exec. 2463.41621709secondes) (ancienne version)

Methode 1: Temps moyen : 0.000 619 438 126 564 secondes (Temps Exec. 619.438126564secondes) (nouvelle version)

Methode 2: Temps moyen : 0.000 034 199 709 653 9 secondes Temps Exec. 34.1997096539secondes)

Methode 3: Temps moyen : 0.000 029 232 471 94 29 secondes (Temps Exec. 29.2324719429secondes)

Methode 4: Temps moyen : 0.000 172 626 668 93 secondes(Temps Exec. 172.62666893secondes)



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

tu peux aussi mettre $taille_tab = count($dispo); à l'extérieur de la 1er boucle, et quand tu supprime un élément, tu soustrait de 1 $taille_tab.
Ce sera mieux, mais je pense que reste la plus lente des méthodes.