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

[Argorate]

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é.

[wild-D]

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.

[Argorate]

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

[Cartman34]

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

} 

[Argorate]

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

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?

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 :

$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.

[Cartman34]

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.

[Argorate]

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:

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++;

} 

[keke]

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é

[Argorate]

Rectification qui m'a était suggéré sur IRC (oué je fais un peu de pub)
Toujours la plus mauvaise, mais nettement mieux cependant:

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;

} 

[jo_link_noir]

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.