Discussion :

[topgun1223]

Bonjour à tous,

Je suis bloqué sur un algo depuis quelques temps et je n'arrive pas à trouver de solution. Voici ce que j'aimerai faire :

Code :

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

1
2
3
4
5
6
7
8
 
foreach($myArrays as $myKey => $myArray){
     foreach($myArrays as $otherKey => $otherArray){
          if ($ohterArray == $myArray) break;
          if (//une certaine condition sur les deux tableaux)
              unset($myArrays[$otherKey]);
     }
}

En gros, $myArrays est bien modifié dans la deuxième boucle mais malheureusement ce n'est pas effectif quand on revient dans la première boucle. J'aimerai bien que lorsque l'on revienne dans la première boucle, il n'y ait plus les éléments virés dans la deuxième boucle. Je veux faire ça car j'ai beaucoup de données dans $myArrays et c'est déjà assez lourd de boucler deux fois dessus !

Alors si quelqu'un aurait une solution à mon problème, je suis preneur

[djibxav]

Un algo d'élimination de doublons ?
Pas possible, autant que je sache, avec foreach d'avoir le tableau impacté en temps réel.

Par contre ça marche avec un for

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
 
//Tableau a dédoublonner
$arr = array('A','B','A','C','D','B','E','F','F','A','C','F','D');
 
$maxval = sizeof($arr);	//nbre d'item dans le tableau
 
//boucle 1
for($i=0;$i<$maxval;$i++) {
	//boucle 2
	for($j=0;$j<$maxval;$j++) {
		if ($i == $j)  continue; //on ignore la comparaison avec soi même
		if($arr[$i] == $arr[$j]) unset($arr[$j]); //si valeur identique on fait sauter la 2eme
	}
	$arr = array_values($arr); 	//reindexation du tableau sinon aille aille aille le for
	$maxval = sizeof($arr);		//recalcul du nombre d'items
}

Si tu var_dump le tableau à chaque itération, tu verra qu'il diminue bien de taille en temps réel.

[rawsrc]

Bonjour,

Pour éviter de redimensionner le tableau à chaque itération (ce qui peut être problématique), il faut procéder autrement :
1. A chaque itération : remplir un tableau des clés à supprimer
2. Faire un array_diff_key() en fin de traitement

Je pense qu'il serait judicieux que tu postes ton code complet avec tes tests, histoire de voir s'il n'y aurait pas un raccourci. Parce qu'il n'est jamais bon de faire des foreach imbriqués sur le même tableau.

[topgun1223]

Merci pour vos réponses.

Et je vais essayer d'être plus précis dans ce que je veux faire. Ce n'est pas un algo d'élimination de doublons mais un algo de regroupement de données.
J'ai un tableau avec des données localisées. Je voudrais regrouper ces données suivant la distance qui les sépare. Donc pour le moment je ne vois pas d'autres solutions que de comparer les données une à une dans une double boucle...

Voici mon algo complet :

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
 
$clusters = array (); //Tableau de tableaux de donnée
foreach ($datas as $data) {
	$cluster = array ();
        $cluster ['data'] = array ();
        array_push ( $cluster ['data'], $data );
	$cluster ['lat'] = $data ['lat'];
	$cluster ['long'] = $data ['long'];
	array_push ( $clusters, $cluster );
}
 
foreach ($clusters as $keycluster => $cluster) {
	foreach ($clusters as $keyotherCluster => $otherCluster) {
               if ($keycluster != $keyotherCluster && distance < à un certain nombre) {
                array_push ($clusters[$keycluster]['data'], $clusters[$keyotherCluster]['data'][0]);
                unset($clusters[$keyohterCluster]);
               }
        }
}

Voilà concrètement ce que je voudrais faire. Sauf qu'apparemment la modification de $clusters faite dans la deuxième boucle n'est pas prise en compte dans la première. Et j'ai bien conscience que c'est un algo assez lourd, donc si quelqu'un voit un moyen de l'optimiser, je suis preneur !

[djibxav]

Un problème me viens à l'exprit.

Prenons un tableau de 4 points a,b,c,d

avec les distances suivantes:

ab = 10
ac = 30
ad = 10
bc = 15
bd = 5

et imaginons que tu regroupe les points séparés de moins de 12

Si je suis ton algo avec a en première boucle tu va successivement retirer b et d du tableau puisque ab = 10 et ad = 10

Mais alors tu n'évaluera jamais bc, bd et cd alors qu'il parait judicieux d'évaluer bd qui a une distance de seulement 5, du coup si tu cherche le plus cours, c'est dommage.

Par contre une fois a passé en première boucle, il a été évalué avec toutes les autres données, il serait donc judicieux pour alléger le traitement de n'évaluer en 2eme boucle qu'avec les indices supérieurs à celui de la boucle 1

boucle1 sur indice1 = 0 a sizeof
boucle2 sur indice2 = indice1+1 à sizeof
//boucle d'or dans la maison des ours
fin boucle2
fin boucle1

[topgun1223]

Ah oui, bien vu pour l'opti ! Merci

Sinon, j'ai réussi à avoir quelque chose qui fonctionne, même si c'est pas très beau.

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
 
$finalClusters = array();
$deleteClusters = array();
 
foreach ($clusters as $keycluster => $cluster) {
	for ($keyotherCluster = $keycluster + 1; $keyotherCluster < count($clusters); $keyotherCluster++) {
		$otherCluster = $clusters[$keyotherCluster];
               if ($keycluster != $keyotherCluster && distance < à un certain nombre) {
                array_push ($clusters[$keycluster]['data'], $clusters[$keyotherCluster]['data'][0]);
                if (!in_array($otherCluster['id'], $deleteClusters)){
			array_push($deleteCluster, $otherCluster['id']);
			if (!in_array($cluster['id'], $finalClusters))
				array_push($finalClusters, $cluster['id']);
		}   
             }
        }
}
return $this->removeDuplicate($clusters, $finalClusters);
 
public function removeDuplicate($arrays, $final){
	$result = array();
	foreach ($arrays as $array){
		if (in_array($array['id'], $final))
			array_push($result, $array);
	}
	return $result;
}

Ca m'embête un peu de devoir parcourir une fois de plus mon gros tableau pour enfin avoir le bon tableau...

[djibxav]

Je ne comprend pas certaines choses.

Pourquoi un removeDuplicate alors que ce n'était pas le but de l'algo ?
Si ton tableau de départ contient des doublons de points, peut être vaut-il mieux le dé-dupliquer avant de le traiter, tu aura moins de données à évaluer, tu n'en sera que plus gagnant.

Si le but est de créer des couples pourquoi les créer dans ton tableau d'origine contenant des points alors qu'il serait plus simple de garder ton tableau de points propre et stocker tes couples dans un nouveau tableau ?
C'est comme si tu attache des briques lego 2 par 2, en remettant celles attaché dans la même boite que celles qui ne le sont pas au lieu de prendre une nouvelle boite, on s'emmêle vite les pinceaux.

[topgun1223]

J'ai fait un removeDuplicate car je me retrouve avec des doublons de regroupement. Par exemple si j'ai les regroupements suivants : a;b et c;d mon algo va me retourner a;b, b;a, c;d, d;c. C'est pour ça que je voulais faire un unset directement après avoir trouvé un regroupement à faire pour supprimer la donnée et donc ne pas avoir de doublons. Mais mon tableau de départ n'a pas de doublons.

il serait plus simple de garder ton tableau de points propre et stocker tes couples dans un nouveau tableau ?

Au final c'est ce que je fais il me semble, vu que je stock les id dans mon $finalClusters et dans removeDuplicate, je crée un nouveau tableau avec seulement les données dont l'id est dans $finalClusters. Ou alors j'ai mal compris ce que tu voulais dire.

[djibxav]

boucle1 sur indice1 = 0 a sizeof
boucle2 sur indice2 = indice1+1 à sizeof
//boucle d'or dans la maison des ours
fin boucle2
fin boucle1

avec ça il est impossible que tu ai les doublon a:b et b:a
as-tu var_dump() ton tableau de résultat et vu des doublons ?

Ca devrait pas être plus compliqué que ça

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
<?php
$finalClusters = array();
foreach ($clusters as $keycluster => $cluster) {
    for ($keyotherCluster = $keycluster + 1; $keyotherCluster < count($clusters); $keyotherCluster++) {
        $otherCluster = $clusters[$keyotherCluster];
        if ($keycluster != $keyotherCluster && distance < à un certain nombre) {
            $finalClusters[] = array($clusters[$keycluster]['data'],$clusters[$keyotherCluster]['data']);      
        }
}
return $finalClusters