Discussion :

[lechewal]

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

[pseudocode]

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 :

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

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

[lechewal]

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

[pseudocode]

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.

[lechewal]

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..

[Jean-Marc.Bourguet]

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).

[pseudocode]

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