Discussion :

[kisame]

Bonjour,

J'ai fait quelques recherches sur le net avant de poster mais je dois mal les faire car je n'arrive jamais à trouver ce que je cherche (et je n'aime pas trop faire du déterrage de topic pour une question proche d'un sujet existant).

Soit 2 listes contenant uniquement des chaines de caractères:
my @a=( "zz", "ab", "ka", "bb");
my @b=( "bb", "ab","cd");

Et je voudrais savoir si le contenu de ces listes est identique.

Je pensais faire de la bête comparaison item par item après avoir trié les 2 listes avec un simple "for" (dans mon cas elles auront au maximum 50 éléments, mais raisonnons avec une taille quelconque).

Mais dans plusieurs sujets de conversation, les développeurs les plus avertis semblent toujours proposer des solutions à base de hash temporaire.

exemple : http://www.developpez.net/forums/d33...on-2-tableaux/

Dans chacun des cas cités plus haut, la raison de l'utilisation d'un hash intermédiaire n'est pas fournie et les gens qui posent les questions n'ont pas la curiosité de demander pourquoi passer par ça.

Mes questions sont donc les suivantes :
- Est-ce que dans les exemples ci-dessus l'utilisation d'un hash est juste un truc de simplification de code ou y a-t-il un réel intérêt derrière ?
- Est-il plus coûteux, moins propre, ou autre de trier les listes et de comparer les valeurs item par item ?

[Gardyen]

l'intérêt d'utiliser un hash c'est l'accès direct à ton élément, pas besoin de parcourir toute une liste pour savoir si un élément particulier y est (enfin tu ne parcours qu'une liste au lieu des 2), d'où un gain de temps.

sinon je suis du genre à utiliser des modules pour ne pas réinventer la roue
List::Compare

[kisame]

Merci Gardyen pour cette réponse.

J'avais bien intuité qu'on jouait sur les accès directs, donc tu me confirmes

Le problème (dans les 2 exemples que j'ai donnés et que j'ai testés), c'est que ça ne marche que si le second tableau n'a une taille inférieure ou égale.

Sinon :
- dans l'exemple 1, il faut refaire la même boucle avec le second tableaux (donc malgré les accès direct, on fait 2 parcours de boucle)
- dans l'exemple 2, il faut faire un check sur la taille du tableau en sortie (est-ce qu'elle est égale aux 2 tableaux).

Tu me confirmes ?

Mais je reconnais que ce n'est qu'un détail car de toute façon, pour comparer 2 listes, le premier check à faire en entrée de fonction est de savoir si les 2 listes ont la même taille

Pour ce qui est de l'utilisation des modules, j'adopte cette réfléxion:
- ne pas utiliser tout un module quand je ne dois utiliser qu'une ou deux fonctions de celui-ci et que je peux recoder en 5 secondes (bon ok, là typiquement je me pose des questions métaphysiques pour une fonction toute bête ).
- Sinon => on ne réinvente pas la roue. Surtout que ça doit être des gens bien plus compétents que moi qui les ont codé.


Au boulot, on m'a un peu forcé à utiliser cet adage:
- N'utilise un module que si celui-ci est totalement indispensable au projet
- Sinon => tu le codes ou tu fais autrement (et fait moi 50 pompes pour avoir eu une telle idée petit con!)

La question étant pour mon taf et List::Compare n'étant pas installé (test fait à l'instant), on rentre dans la case "sinon" du second adage


Encore merci.

edit : dans l'exemple de Jedai, c'est l"inverse. Ca ne marche pas si scalar($liste1) > scalar($liste2)

[Lolo78]

Sinon :
- dans l'exemple 1, il faut refaire la même boucle avec le second tableaux (donc malgré les accès direct, on fait 2 parcours de boucle)

Oui, si tu veux déterminer si les deux tableaux sont égaux. En général, la question est plutôt de trouver les éléments du second tableau qui sont (ou ne sont pas) dans le premier tableau.

Par ailleurs, si tu fais des boucles imbriquées, tu parcours une fois le premier tableau et n fois le second (s'il y a n éléments dans le premier tableau). Si tes tableaux ont des milliers d'éléments, il y a une très grosse différence entre parcourir une fois chaque tableau (et même une deuxième fois le premier tableau) et parcourir une fois un tableau et n fois l'autre.

Voici un exemple sous le debugger:

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
  DB<1> @a=( "zz", "ab", "ka", "bb");
  DB<2> @b=( "bb", "ab","cd");
  DB<3> %hash = map {$_, 1} @a
  DB<4> x %hash
0  'ab'
1  1
2  'bb'
3  1
4  'ka'
5  1
6  'zz'
7  1
  DB<5>
 print "$_ missing\n" for grep {! defined $hash{$_}} @b
cd missing

Si tes tableaux ont des milliers ou des millions d'éléments, il est bien plus rapide de parcourir une première fois un tableau pour remplir un hash et une fois le second pour détecter les éléments manquants, puis de refaire l'opération en sens inverse, que de trier tes deux tableaux.

Par ailleurs, on peut trouver une solution assez simple pour ne parcourir qu'une fois chaque tableau: je remplis mon hash avec mon premier tableau, je lis le second tableau, imprime les éléments non présents dans le hash (orphelins 2) et flague dans le hash ceux qui sont dans le second tableau. A la fin, mon hash contient en non flagué les éléments absents du second tableau et en flagué les éléments présents. En continuant l'exemple ci-dessus:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
  DB<6> defined  $hash{$_} ?  $hash{$_} = 2 :  print "$_ missing\n" foreach @b
cd missing
  DB<7> x %hash
0  'ab'
1  2
2  'bb'
3  2
4  'ka'
5  1
6  'zz'
7  1
  DB<8>

Dans le hash, les éléments de @a présents dans $b sont à 2, les autres à 1.

[kisame]

En général, la question est plutôt de trouver les éléments du second tableau qui sont (ou ne sont pas) dans le premier tableau.

Oui, c'est surement souvent le cas, mais pas le mien . J'ai vraiment besoin de savoir si 2 listes ont leur contenu identiques (si je devais écrire un mini test sur la fonction en pseudo code ça donnerait):

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
@liste1=(1,2,3,4);
@liste2=(1,2,3,4,5,6);
 
sub compare
{
...
}
 
unless (&compare(@liste1,@liste2) eq &compare(@liste2,@liste1))
{
  print "ne doit jamais s'imprimer\n";
}

Par ailleurs, si tu fais des boucles imbriquées, tu parcours une fois le premier tableau et n fois le second (s'il y a n éléments dans le premier tableau). Si tes tableaux ont des milliers d'éléments, il y a une très grosse différence entre parcourir une fois chaque tableau (et même une deuxième fois le premier tableau) et parcourir une fois un tableau et n fois l'autre.

C'est justement pour éviter ça que je parlais de faire un sort des 2 tableaux avant de lancer la comparaison item par item.
Une fois les 2 tableaux triés, avec une bête boucle avec indice tout ce qu'il y a de plus classique si ($liste1[i] ne $liste2) alors les 2 listes ne sont pas identiques.

=> 1 seul parcours de boucle
mais ça impose que les éléments soient triés (et faire 2 sorts en entrée de fonction ou, dans mon cas, obliger de faire des ajouts ordonnés ... c'est pas top du tout).

Du coup, au final j'ai juste rajouté une petite modif dans le code de Jedai pour que ça soit 100% nickel pour mon petit besoin

Par ailleurs, on peut trouver une solution assez simple pour ne parcourir qu'une fois chaque tableau: je remplis mon hash avec mon premier tableau, je lis le second tableau, imprime les éléments non présents dans le hash (orphelins 2) et flague dans le hash ceux qui sont dans le second tableau. A la fin, mon hash contient en non flagué les éléments absents du second tableau et en flagué les éléments présents. En continuant l'exemple ci-dessus:

j'aime bien. A voir si je ne vais pas modifier la petite fonction que je me suis faite ce matin du coup.

Merci beaucoup pour ta réponse et le détail que tu y as apporté

[Lolo78]

Tu ne sembles pas avoir vu une phrase de ma réponse:

Si tes tableaux ont des milliers ou des millions d'éléments, il est bien plus rapide de parcourir une première fois un tableau pour remplir un hash et une fois le second pour détecter les éléments manquants, puis de refaire l'opération en sens inverse, que de trier tes deux tableaux.

Cela dit, j'ai écrit un module pour comparer de très très gros fichiers, trop gros pour les mettre dans un hash (pas assez de mémoire vive), je commence par trier mes fichiers pour les compare ligne à ligne. Comme quoi, dans certains cas, ce peut être la bonne solution.