Intersection d'ensemble trié

Hello,

j'ai deux ensemble triés.

J'aimerai faire leur intersection, c'est à dire le nombre d'éléments qu'ils ont en commun.

En utilisant des listes, j'ai fait un algo qui avance dans la liste qui a l'élément le plus petit.

J'accèlère grandement le traitement si j'utilise des set (avec hachage donc).

Seulement, je n'utilise plus le fait que mes ensemble sont déjà triés (par construction en fait)

Je me demande s'il n'y a pas un moyen d'accélerer encore le traitement (cette fonction occupe 80% du temps de mon algo :s)

merci

1. Tu places un curseur au début de chaque liste
2. Tu compares les valeurs pointées par les curseurs
3. Tu avances le curseur qui pointe sur la plus petite valeur (ou les 2 en cas de match)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

L1 = 1 5 7 11 13 L2 = 2 5 6 10 13   (^,^) --> avancer dans L1 et L2 (1,2) --> avancer dans L1 (5,2) --> avancer dans L2 (5,5) --> [MATCH] avancer dans L1 et L2 (7,6) --> avancer dans L2 (7,10) --> avancer dans L1 (11,10) --> avancer dans L2 (11,13) --> avancer dans L1 (13,13) --> [MATCH] avancer dans L1 et L2 ($,$) --> fini

---

Ouep, c'était mon premier algo.
Mais il est plus lent que en utilisant les hash set

Ah ok. Pour des optimisations plus poussées il faut utiliser la forme de tes ensembles: taille, densité, etendue de l'intersection, ...

Si les HashSet sont plus rapide, je suppose que c'est parceque tu as bcp de données dans tes ensembles.

C'est très hétérogène.

La moyenne est d'environ 50, mais il y en a beaucoup avec un seul élement (la moitié) et donc quelques uns avec beaucoup d'éléments..

Citation:

---

Envoyé par pseudocode

Si les HashSet sont plus rapide, je suppose que c'est parceque tu as bcp de données dans tes ensembles.

---

Quel est ton raisonnement?

(Perso, je n'ai pas assez de renseignements pour emettre une opinion).

Citation:

---

Envoyé par Jean-Marc.Bourguet

Quel est ton raisonnement?

---

Les hashset accelerent la recherche d'un element parmis n. Si c'est plus rapide que l'algo sweep, c'est surement qu'il y a peu d'element commun par rapport au nombre total d'elements. Enfin bon, c'est un peu du pif aussi :aie:

Citation:

---

Envoyé par pseudocode

Les hashset accelerent la recherche d'un element parmis n. Si c'est plus rapide que l'algo sweep, c'est surement qu'il y a peu d'element commun par rapport au nombre total d'elements. Enfin bon, c'est un peu du pif aussi :aie:

---

La recherche est a priori toujours plus compliquee que l'acces a une valeur deja fixee.

Ton raisonnement par contre me semble plus valide si il y a un ensemble qui a peu d'elements par rapport a l'autre et qu'on ne considere pas le temps de construction des ensembles (si on le considere, on est en n+m de toutes facons avec vraisemblablement une constante plus faible pour la liste chainee).

Pour en revenir au PO, tu dois trouver les elements communs entre les N listes, ou les elements communs entre les listes 2 a 2 ?

Les listes 2 à 2

En fait, pour chacune des listes, je fais plusieurs intersections à la suite

Je ne vois pas trop de solution algorithmique pour optimiser la comparaison de 2 listes.

Il faut voir si on peut gagner du temps sur le nombre de comparaison a faire, par exemple en evitant de comparer des listes telles que Last(L1)<First(L2)

Après on peut aller plus loin en faisant des clusters (sous listes), mais ca va finir par prendre plus de temps que la comparaison NxN

Il faut savoir que j'ai environ 200.000 listes

Et que pour chacune d'elle, je fais en moyenne 50*40 intersections :s

Dans ce cas le decoupage des listes en sous-liste + les criteres de non chevauchement peuvent arranger les choses.

Mh, faut savoir que je suis déjà très limite en place mémoire (surtout quand j'utilise des set qui prennent plus de place)

Qu'entends tu par "sous-listes" ?

Pour l'histoire du chevauchement, ca suppose d'utiliser les listes et non les set. J'ai des doutes quant au gain global (vu que c'est clairement beaucoup plus lent une intersection "classique" entre deux listes qu'entre deux sets)

Mais bon, a tester ;)

Citation:

---

Envoyé par lechewal

Mh, faut savoir que je suis déjà très limite en place mémoire (surtout quand j'utilise des set qui prennent plus de place)

---

Faut faire des choix. Quand on veut optimiser le CPU, generalement ca consomme de la mémoire. :P

Citation:

---

Qu'entends tu par "sous-listes" ?

---

Tu decoupes une grande liste en X petites listes. En utilisant les regles de chevauchement ca te fais des listes moins grandes a comparer... mais plus de comparaisons a faire (a noter qu'on peut les paralleliser). Il faut voir si ca vaut le coup:

Code:

---

1 2 3 4 5 6 7 8

L1=[1 2 4 5 6 9 10 11] L2=[1 2 3 4 8 9 12] -> 1 intersection 8x8   L1=[1 2] [4 5 6] [9 10 11] L2=[1 2 3 4] [8 9] [12] -> 1 intersection 2x4 + 1 intersection 3x4 + 1 intersection 3x2

---

Citation:

---

J'ai des doutes quant au gain global

---

oui, moi aussi. A tester donc.