Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1351 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  Recherche d'une liste de valeurs dans une autre

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Recherche d'une liste de valeurs dans une autre

n°2054581
charlebakh​tovsky
Posté le 05-02-2011 à 21:18:27  profilanswer
 

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


 
P.S. Les valeurs des tableau ne sont pas forcément des nombres, c'est des chaines de caractères dans n'importe quel ordre.


Message édité par charlebakhtovsky le 05-02-2011 à 22:51:37
mood
Publicité
Posté le 05-02-2011 à 21:18:27  profilanswer
 

n°2054978
billgatesa​nonym
Posté le 07-02-2011 à 23:19:03  profilanswer
 

Oui, il y a plus rapide que ces deux boucles imbriquées.
 
Mais d'abord, il faut que les deux listes soient triées.
Vous trouverez facilement des algorithmes de tri performants.
 
Puis, on fait une seule boucle sur les deux ensembles jusqu'à ce que l'on ait plus d'éléments.
C'est l'équivalent de deux boucles qui se suivent (au lieu d'être imbriquées).
 
Dans cette grande boucle, on va prendre un élément de chaque ensemble.
On les compare. On garde le plus petit, et on avance au prochain élément de l'ensemble où se trouvait le plus petit.
Si il n'y a pas de plus petit, c'est donc que les deux éléments sont égaux. Alors, on n'en garde qu'un seul, et on fait avancer les deux listes.
C'est ça l'astuce.
 
Si les listes sont très petites, le tri initial peut être handicapant. Mais dès que les listes commencent à avoir plus d'une vingtaine d'éléments environ, cela vaut le coup.
 
D'ailleurs, si vous voulez le faire manuellement, vous allez vite penser à la solution du tri initial des listes.


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  Recherche d'une liste de valeurs dans une autre

 

Sujets relatifs
[AJAX] Afficher données d'une BDD avec filtrage via liste déroulanteRecherche module commandes groupées
Somme des valeurs Algo quand la saisie est terminécomment ajouter une liste de url dans les favoris
[VBA WORD] Liste deroulante avec source Excelrecherche programmeur pour jeu
Jointure et choix de valeurs par defaut (pour traduction)Création d'un filtre de recherche
Prgm VBA et ou Excel - RechercheV ... recherche du nom le plus long 
Plus de sujets relatifs à : Recherche d'une liste de valeurs dans une autre


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR