Discussion :

[Holic]

Bonjours, pour les besoins d'un projet personnel je doit générer aléatoirement un nombre donné de coordonnées du style x,y sur une grille de 500*500 (chaque case fait 10*10), mon soucis étant que chaque coordonnée x,y générée ne doit pas déjà avoir été générée auparavant au même coordonnées, je souhaite faire une sorte de random sélectif.

J'ai codé le petit bout de code ci-dessous qui est fonctionnel, cependant si le nombre à générer devient important, php rame, cela est du je pense à ma boucle while, je souhaiterais donc savoir si il existe un moyen plus "propre" de faire cela, merci.

Vous pouvez voir le résultat de la génération actuelle sur ce lien : http://waelin-chatbot.fr/simulation/

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//Nombre de cases générées souhaité
$nb = 10;
 
//initialisation du tableau contenant les coordonnées des cases
$tab = array();
 
 
for($i = 1; $i <= $nb; $i++){
 
	$x = rand(1,50);
	$y = rand(1,50);
 
	$coor = $x.','.$y;
	$present = true;
 
	while($present){
 
		//Si $coor n'est pas présent dans $tab, on sort du while	
		if(!in_array($coor, $tab)){ $present = false; }
 
		//Si $present vaut toujours vrai, on régénère des coordonnées
		//avant de repasser dans le while 	
		if($present){
 
			$x = rand(1,50);
			$y = rand(1,50);
			$coor = $x.','.$y;
		}
	}
 
	//Ajout des coordonnées
	$tab[] = $coor;
}

[sabotage]

in_array va etre lent sur de gros tableau.
tu iras plus vite en utilisant les index de tableau :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
$nb = 10;
 
$tab = array();
 
for($i = 1; $i <= $nb; $i++){
 
	do {
		$x = rand(1,50);
		$y = rand(1,50);
		$coor = $x.','.$y;
 
	} while(isset($tab[$coor]))
 
        $tab[$coor] = TRUE;
}

[Holic]

Salut sabotage, merci pour cette réponse

j'ai regardé ton code et je comprends pas le "$tab[$coor] = TRUE;" à la ligne 15

c'est seulement les coordonnés générés que je souhaite rajouter à mon tableau.

[sabotage]

C'est seulement pour la boucle.
Après tu fais $tab = array_keys($tab); pour remettre les index en valeurs.

[Holic]

Bien, je viens de tester, et PHP m'indique une erreur de syntaxe au niveau de la ligne 15 justement ><

[rawsrc]

Salut,

pour gagner en perfs, essaie avec un in_array typé :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if ( ! in_array($coor, $tab, true))

En testant ton code tel quel avec $nb = 1000;, j'obtiens : 0,0835 s, juste en rajoutant le typage : 0,0143 s (5,9 fois plus rapide)

Et en cherchant à optimiser dans ce genre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function random($nb)
{
$i  = -1;
 
    // initialisation du tableau contenant les coordonnées des cases
    $tab = array();
 
    $get_coord = function() { return rand(1, 50).','.rand(1, 50); };
 
    while (++$i < $nb)
    {
        $c = $get_coord();
        while (isset($tab[$c]))
        {
            $c = $get_coord();
        }
 
        $tab[$c] = true;
    }
 
    return array_keys($tab);
}

J'obtiens : 0.00165 s soit 51 fois plus rapide pour 1000 coordonnées

[Holic]

Salut rawsrc, j'ai essayer ton code, alors effectivement sa semble bien plus rapide, cependant des que je dépasse les 1200/1300 le script se met a ramer et dépasse les 30s de php ...

[sabotage]

Quand tu as trouvé 1250 coordonnées, tu as 1 chance sur 2 de ne pas trouver une coordonnée libre sur le tirage.

[Holic]

Ha ... sachant qu'il faut que j'en génère 2500 max différents pour remplir la grille sa ne conviendra pas ... je vais rester sur mon script de base qui fonctionne correctement pour 2500, je l'ai modifié en fonction de vos remarques pour améliorer la vitesse, sa suffira amplement pour le moment.

Merci à vous pour vos propositions et vos idées

[sabotage]

Tu n'as pas suivi : Le problème est le même quelque soit la méthode utilisée. Plus tu as déjà trouvé d'éléments, plus il est dur d'en trouver un libre. Tu peux même chercher à l'infini même c'est si improbable.
Mais sur 2500 éléments ça reste raisonnable.

Pour revenir à notre script, avec la méthode qu'on te propose, il faut quelques centièmes de secondes pour remplir les 2500 cases de ta grille (0,02s en moyenne ici sur mon poste).