Discussion :

[harris_macken]

bonjour

existe t il un algorithme pour trouver :
l intersection et l'union de 2 listes L1 et L2

et aussi pour trouver les elements qui sont uniquement dans L1 et uniquement dans L2

merci

[FrancisSourd]

La liste n'est pas la structure de donnée la plus appropriée pour faire ces opérations. Le plus simple est certainement de passer par des listes triées. En adaptant l'algorithme de fusion de listes triées, on peut faire ces opérations en O(n1+n2) (n1 et n2 sont les longueurs de L1 et L2).

Si le nombre d'objets différents pouvant être inclus dans chaque liste est petit , on peut travailler avec un représentation en tableau de bits.
Exemple: On a au plus 16 objets. Une liste comportant les objets 2 et 9 s'écrit 0100000010000000.
On fait alors l'union et l'intersection en utilisant les opérateurs logiques.

[harris_macken]

oui suis tout a fait d accord
sauf que j ai la contrainte d utiliser des listes lineaires

[Jedai]

Tu peux insérer tous tes éléments dans un arbre binaire de recherche puis reconstituer une liste, ainsi tu devrais avoir une moyenne en O(n log n). (En "marquant" les éléments, tu peux te faire ainsi un arbre qui peut servir à extraire l'intersection, l'union ou la différence, mais tout dépend de tes besoins).
Je ne pense pas qu'on puisse faire mieux que du O(n log n) à partir de listes non-triées au départ (ça doit même être assez facile à prouver), mais on peut peut-être améliorer légèrement la méthode proposée ci-dessus. Par contre trier tes listes auparavant peut-être une bonne idée si tu as de gros besoins, et répétitifs. (en fait si tu disposes réellement de listes chaînées, le mieux est sans doute d'adapter l'algorithme du tri fusion)

--
Jedaï

[Trap D]

Salut
Tes listes sont-elles triées ?
Comment les obtiens-tu ?
Car si elles sont triées, celà va assez vite, car aussi bien pour l'union que pour l'intersection un seul parcours de chaque liste en parallèle est suffisant.
Sinon, il faut parcourir une liste et pour chaque élément de cette liste, parcourir en entier la deuxième liste.
[edit] grillé par jedaï et en plus sa méthode d'arbre de recherche me paraît bien meilleure que la mienne
[/edit]

[harris_macken]

nan elle ne sont pas triees

[harris_macken]

jeday

Tu peux insérer tous tes éléments dans un arbre binaire de recherche puis reconstituer une liste, ainsi tu devrais avoir une moyenne en O(n log n).

tu peut expliciter ta methode elle me parait pas mal pour ma sollution

[Trap D]

Tu peux regarder ici pour avoir une idée des algos, c'est en C, mais assez facilement compréhensible.

[harris_macken]

Oui j ai vu mais sa m aide pas trop

cependant l idee de Jervais m interesse bien

Tu peux insérer tous tes éléments dans un arbre binaire de recherche puis reconstituer une liste, ainsi tu devrais avoir une moyenne en O(n log n). (En "marquant" les éléments, tu peux te faire ainsi un arbre qui peut servir à extraire l'intersection, l'union ou la différence, mais tout dépend de tes besoins).
Je ne pense pas qu'on puisse faire mieux que du O(n log n) à partir de listes non-triées au départ (ça doit même être assez facile à prouver), mais on peut peut-être améliorer

Peut tu me l expliciter

[Trap D]

Dans un arbre binaire de recherche a une structure de ce type :

Code :

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

1
2
3
4
5
6
7
8
// en C
typedef struct noeud
{
  int cle; // la valeur du noeud
  int nb; // le nombre d'occurences ou apparait cette clé 'pour l'intersection des liste
  struct noeud *fg; // le fils gauche 
  struct noeud *fd; // le fils droit
}  noeud;

L'insertion se fait de cette manière, en utilisant la récursivité

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
procedure insertion(valeur, noeud)
  si valeur = noeud.cle alors
     noeud.nb <- noeud.nb + 1
  sinonsi valeur < noeud.cle alors
     si noeud.fg = NULL alors
        noeud.fg <- nouveau_noeud(valeur)
     sinon
          insertion(valeur, noeud.fg)
     finsi
  sinon
      si noeud.fd = NULL alors
         noeud.fd <- nouveau_noeud(valeur)
      sinon
         insertion(valeur, noeud.fd);
      finsi
  finsi
finprocedure

Il y a un cas particulier à traiter, c'est l'initialisation de l'arbre.
Il faut écrire bien sur la fonction nouveau_noeud(valeur)

[Jedai]

Oui j ai vu mais sa m aide pas trop

cependant l idee de Jervais m interesse bien

Peut tu me l expliciter

Jedaï pas Jervais !!
Après réflexion, le plus cohérent me semble un simili-tri fusion SI tu as bien des listes chaînées, est-ce le cas ? (Par ailleurs, quelles sont les tailles de tes listes en moyenne et au pire ?)

--
Jedaï

[harris_macken]

En fait mes listes sont lineaires

et la taille des listes est elevee et inconnue au prealable

[Jedai]

Que de précision ! Que signifie "linéaire" dans ton cas : veux-tu dire qu'il s'agit de tableau (donnée stockée contigument en mémoire) ? Par ailleurs tu dois bien avoir un ordre d'idée du "élevé" : de l'ordre du million, du milliard ?

--
Jedaï