Discussion :

[parfait18]

Bonjour à tous
je dispose de deux tableaux A et B contenant chacun près de 100 000 valeurs et d'un tableau C vide.
je veux faire des tests simultanés sur les valeurs des tableaux A et B puis remplir le tableau C selon que le test réalisé soit vrai ou faux. Ce pendant, la grande taille des tableaux A et B font ramer mon code (alors que le code tourne plus vite lorsque ces tableaux sont de petites tailles) et je me demande s'il y aurait pas mieux.
Un exemple:

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
 
$A=array('1','2','3','8','5');
$B=array('6','7','8','3','10');
$C=array();
 
for($i=0;$i<count($b);$i++)
{
	if (($a[array_search($b[$i],$a)]==$b[$i]) && ($b[array_search($a[$i],$b)]==$a[$i]))
	{
		$c[$i]='bi';
	}
	else
	{
		$c[$i]='mono';
	}
}

Explication:
lorsque quelque part dans le tableau A on a une certaine valeur a et, à cette même position, on a une certaine valeur b dans le tableau B, si il existe une position où l'on retrouve b dans A et a dans B alors à cette position dans C on met la valeur 'bi'; autrement, on met la valeur 'mono'.
Ce code tourne bien et à la vitesse de la lumière.
Mais quand j'utilise de grands tableaux (100 000 valeurs), il met plus de 20 minutes!
Comment faire pour l'optimiser avec de grands tableaux???

Merci d'avance.

[Séb.]

Code :

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

for($i=0;$i<count($b);$i++)

Là tu appelles count( ) à chaque tour de boucle. A corriger en 1er.

Lorsque quelque part dans le tableau A on a une certaine valeur a et, à cette même position, on a une certaine valeur b dans le tableau B, si il existe une position où l'on retrouve b dans A et a dans B alors à cette position dans C on met la valeur 'bi'; autrement, on met la valeur 'mono'.

Pas très clair mais si je comprends bien, au final, tu veux savoir si les éléments à l'index $i de $B apparaissent quelque part dans $A ?
Si oui tu valorises $C[$i] à "bi" sinon "mono".
C'est bon ?
Auquel cas tu peux remplacer tes 2 array_search( ) par 1 in_array( ).

Comment faire pour l'optimiser avec de grands tableaux???

Travailler sur des tableaux triés pourrait être un bon début. Ainsi tu devrais pouvoir éviter d'appeler arrray_search( ) / in_array( ) à chaque tour de boucle.

Mais quand j'utilise de grands tableaux (100 000 valeurs), il met plus de 20 minutes!

Peux-tu transmettre un tableau valorisé et le résultat attendu ? Ainsi nous pourrions tester l'application de différents algos en PHP.

[parfait18]

Merci pour ta réponse.

Illustration de ce que je veux faire:
A|B|C
----- ---
1|5|bi
2|6|mono
5|1|bi
4|8|mono
..|..|...

j'espère que c'est assez claire. De ce fait, "in_array" ne m'aide pas!
concernant

Code :

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

for($i=0;$i<count($b);$i++)

j'ai fais la correction. Merci mais pas de changements!

Qu'entends tu par "transmettre" un tableau valorisé? mes tableaux A et près sont des tableaux contenants des entiers naturels et ayant chacun 100 000 enregistrements. peux tu utiliser cette information et l'illustration (la table) ci-dessus pour réaliser des tests?

Merci d'avance.

[Séb.]

Et quel est le résultat pour ceci :

Code :

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

1
2
3
4
5
6
7
A|B|C 
--------
1|2|?
2|5|?
4|8|?
5|1|? 
8|4|?

[parfait18]

Le résultat serait :

Code :

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

1
2
3
4
5
6
7
A|B|C 
--------
1|2|mono
2|5|mono
4|8|bi
5|1|mono 
8|4|bi

[Séb.]

OK, c'est plus compliqué que je ne l'avais compris.

Bon, il est illusoire de croire que tu pourrais t'en tirer en parcourant tes tableaux (array_search( )) à chaque tour de boucle.
Il faudrait donc les trier et les parcourir tous les 2 de manière comparative une seule et unique fois.

Tri des tableaux sans perdre l'association clef => valeur : asort( ).

[parfait18]

Bonjour,
qu'entends tu par:

Il faudrait donc les trier et les parcourir tous les 2 de manière comparative une seule et unique fois.

j'ai lu la documentation de asort et je ne vois pas comment cette fonction pourrait m'aider. Pourrais tu m'en dire plus?

Merci d'avance

[Séb.]

Pour reprendre le dernier exemple que j'ai posté :

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
A = Array
(
    [0] => 1
    [1] => 2
    [2] => 4
    [3] => 5
    [4] => 8
)
 
B = Array
(
    [0] => 2
    [1] => 5
    [2] => 8
    [3] => 1
    [4] => 4
)

Après asort( ) :

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
A = Array
(
    [0] => 1
    [1] => 2
    [2] => 4
    [3] => 5
    [4] => 8
)
 
B = Array
(
    [3] => 1
    [0] => 2
    [4] => 4
    [1] => 5
    [2] => 8
)

Maintenant que les tableaux sont triés on peut les parcourir en même temps, et comme asort( ) garde l'association index => valeur quand 2 éléments ont la même valeur on peut vérifier facilement :

Code :

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

1
2
3
4
Si A[ib] == B[ia]
    Bi
Sinon
    Mono

Je pense qu'en parcourant en même temps les 2 tableaux triés tu peux passer d'un temps d'exécutation de 20mn à quelques secondes.

[parfait18]

OK, je fais un test et je reviens vers toi.
A tout à l'heure!

[parfait18]

Un soucis: comment entre en oeuvre le code ci après:

Code :

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

1
2
3
4
Si A[ib] == B[ia]
    Bi
Sinon
    Mono

???

[Séb.]

ia est l'indice de l'élément de A que l'on traite
ib est l'indice de l'élément de B que l'on traite

On obtient les indices avec foreach( ) :

Code :

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

foreach ( $a as $ia => $va ) { ...

Ou list/each :

Code :

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

list($ia, $va) = each($a) ;

[parfait18]

Devrais je alors faire:

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
 
foreach ( $a as $ia => $va ) 
{
    foreach ( $b as $ib => $vb ) 
    {
      if ($va==$vb)
      {
          $c[$ia]='bi';
      }
      else
      {
          $c[$ia]='mono';
      }
     }
}

???

[Séb.]

Le problème là est que tu ne parcours pas tes 2 tableaux en même temps.
Tu parcours $b entièrement à chaque tour de boucle de $a, on retombe dans le même travers que précédemment.

Parcours simultané de 2 tableaux :

Code :

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

1
2
3
4
5
6
$ib = 0 ;
foreach ( $a as $ia => $va ) {
    $vb = $b[$ib] ;
    ...
    $ib++ ;
}

[Séb.]

IMPORTANT : pour parcourir le tableau $b trié avec asort( ) :

Code :

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

1
2
3
4
foreach ( $a as $ia => $va ) {
    list($ib, $vb) = each($b) ;
    ...
}

(autrement tu ne vas pas taper au bon endroit dans $b)

[parfait18]

Je suis largué! j'arrive même pas à mettre cette nouvelle méthode en oeuvre avec le petit tableau d'illustration ci-dessus.
Besoin d'aide!

[Séb.]

Essaie ça :

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
$a = array(1, 2, 3, 8, 5) ;
$b = array(6, 7, 8, 3, 10) ;
$c = array_fill(0, count($a), 'mono') ;
 
asort($a) ;
asort($b) ;
 
list($ib, $vb) = each($b) ;
foreach ( $a as $ia => $va ) {
    while ( $vb != NULL && $vb < $va ) {
        list($ib, $vb) = each($b) ;
    }
    if ( $va == $vb && $a[$ib] == $b[$ia] && $ia != $ib ) {
        $c[$ia] = 'bi' ;
    }
}
 
print_r($c) ;

[parfait18]

Bonjour.
Merci pour le bout de code Séb.
je suis toujours entrain de le tester. mes remarques:
1.il faut ajouter après la ligne 14 l'instruction:

Code :

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

$c[$ib] = 'bi' ;

2. il ne fonctionne pas avec mes grands tableaux.
en fait mes données sont du 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
 
A|B|C
------
1|2|
1|3|
1|4|
2|1|
2|6|
2|3|
2|5|
3|1|
3|4|
3|2|
3|6|
3|5|
4|3|
5|3|
5|6|
6|4|

et le code devrait remplir la table C de façon adéquate. mais il m'affiche (lorsque je fais un echo adéquat):

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
 
A|B|C
------
1|2|bi
1|3|mono
1|4|mono
2|1|mono
2|6|mono
2|3|bi
2|5|mono
3|1|mono
3|4|bi
3|2|mono
3|6|mono
3|5|mono
4|3|mono
5|3|bi
5|6|mono
6|4|mono

et pourtant il est sensé afficher:

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
 
A|B|C
------
1|2|bi
1|3|bi
1|4|mono
2|1|bi
2|6|mono
2|3|bi
2|5|mono
3|1|bi
3|4|bi
3|2|bi
3|6|mono
3|5|bi
4|3|bi
5|3|bi
5|6|mono
6|4|mono

depuis lors j'essaye encore de l'adapter car ce script me paraît proche du but (vu qu'il fait près de 7secondes avec des tableaux de de 100 000 enrégistrements)
Un coup de main?

Merci d'avance

[parfait18]

Séb, à quoi sert concrètement la boucle:

Code :

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

1
2
3
while ( $vb != NULL && $vb < $va ) {
        list($ib, $vb) = each($b) ;
    }

???

[rawsrc]

Salut

si le problème c'est la vitesse et pas la mémoire, est ce que ceci irait mieux ?

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
$a   = array('1', '1', '1', '2', '2', '2', '2', '3', '3', '3', '3', '3', '4', '5', '5', '6');
$b   = array('2', '3', '4', '1', '6', '3', '5', '1', '4', '2', '6', '5', '3', '3', '6', '4');
$c   = array();
$all = array();
 
foreach ($a as $k => $v)
{
    $all[] = $v.$b[$k];
    $all[] = $b[$k].$v;
}
 
$count = array_count_values($all);
 
foreach ($a as $k => $v)
{
    $c[$k] = ($count[$v.$b[$k]] > 1) ? 'bi' : 'mono';
}

[parfait18]

Très bien pensé. j'apprécie ta philosophie rawsrc. C'est tout simplement magnifique!

Grand grand merci.