Discussion :

[charlebakhtovsky]

Bonjour,

Supposons que j'ai deux tableaux T1 et T2 (ou deux fichiers, ou deux listes, ou peut importe) et que je veux ajouter les valeurs de T1 (qui n'existent pas déjà dans T2) à la fin de T2. Est ce qu'il peut y avoir un algorithme plus efficace que de prendre chaque valeur de T1 et parcourir T2 pour voir si elle existe déjà ou pas (algo ci-dessous) ?

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
for i de 1 à N
{
   existeDeja = false;
   for j de 1 à M
   {
      if T1[i] == T2[j]
      {
         existeDeja = true;
         break; // sortir de la boucle
      }
   }
   if existeDeja == false
      Ajouter T1[i] a la fin de T2;
}

[AuraHxC]

En gros tu veux faire l'opération Union sur deux ensembles. Je sais qu'il existe dans la STL de C++ une fonction qui fait ça : set_union. Si tu connais ce langage, tu peux peut être regarder comment ils font. Sinon en cherchant sur internet des algorithmes d'union d'ensemble, peut être que tu trouveras ton bonheur.

[Graffito]

On peut calculer un HashCode (par exemple entre 0 et n=2**24) pour tous les éléments de T1 et créer un tableau de n cellules pointant sur des listes chainées d'index dans le tableau T1. Chaque liste contenant les élements de même hascode.

Pour un élement T2[j], on calculera son Hashcode:
- si la liste correspond au Hascode est vide, T2[j] n'appertient pas à T1,
- sinon on compare T2[j] aux quelques éléments de la liste chainée.

[Nebulix]

Si T2 est trié, la recherche sera beaucoup plus rapide ( O(ln(N)) au lieu de O(N))