Discussion :

[Sve@r]

Bonjour à tous

Je suis en train de me poser une question bête dans un algo: j'ai besoin de ne traiter que les éléments d'un premier tableau qui se trouvent effectifs dans un second

Exemple

Code python :

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

1
2
tab1=["toto", "titi", "tata", "tutu"]
tab2=["tata", "truc", "autre", "toto"]

Vu que seuls "tata" et "toto" sont présents dans tab2, je ne dois alors traiter que ceux-là dans tab1

J'ai 3 solutions possibles

Code python :

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

1
2
3
for x in tab1:
    if x in tab2:
        traitement de x (sur plusieurs lignes)

Code python :

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

1
2
3
for x in tab1:
    if x not in tab2: continue
    traitement de x sur plusieurs lignes

Code python :

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

1
2
for x in [y for y in tab1 if y in tab2]:
    traitement de x sur plusieurs lignes

A votre avis, quelle est la plus efficace des 3 ?

[VinsS]

Salut,

Je pense que tu peux éliminer l'option 2 puisqu'elle nécessite de parcourir entièrement la liste 2 à chaque fois.

Quand aux deux autres, difficile de les départager, éventuellement faire des tests avec timeit.

https://docs.python.org/3/library/ti...#module-timeit

[josmiley]

si les entrées sont uniques et si l'ordre n'a pas d'importance, faire une différence de set ?
D'ailleurs dans la troisième proposition je pense qu'un set de tab2 serait plus rapide.

[f-leb]

Bonjour,

NumPy est aussi équipé pour les intersections de listes : numpy.intersect1d, numpy.in1d

Code :

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

1
2
3
4
In [1]: numpy.intersect1d(tab1, tab2)
Out[1]: 
array(['tata', 'toto'], 
      dtype='<U5')

[Sve@r]

Merci à tous

Je ne comprends pas pourquoi (toi VinsS) élimine la 2 sans éliminer la 1. Effectivement cette solution balaye le second tableau à chaque itération du premier (ça je n'y avait pas pensé, ayant trop encore l'habitude du C dans lequel on n'a pas d'autre solution) mais la première fait aussi de même non ???

Sinon je suis certain que les entrées des deux tableau sont toutes uniques (c'est moi qui les crée) donc à priori, set() ne sera pas utile. En fait, tab2 vient d'un formulaire externe qui contient la liste des éléments ayant demandés à être modifiés et tab1 est dans mon module de mise à jour et contient tous les éléments qu'il est possible de modifier. D'où mon algo où je balaye tous les éléments de tab1 tout en ne conservant que ceux qui sont écrits dans tab2 et représentants ceux qui sont réellement modifiés. Et (juste au cas où on me dirait "ben t'as qu'à ne balayer que tab2 ") je précise que tab2 provient d'un formulaire multitables donc il contient aussi des données qui ne concernent pas tab1...

Je me doutais bien que numpy avait un truc de ce genre. Mon défaut c'est que je ne m'y suis pas encore assez intéressé. Ceci dit, je viens de voir "intersect1d" et ça a l'air sympa. Surtout si (dans mon cas) on positionne le flag "assume_unique" à True

[VinsS]

Merci à tous

Je ne comprends pas pourquoi (toi VinsS) élimine la 2 sans éliminer la 1. Effectivement cette solution balaye le second tableau à chaque itération du premier (ça je n'y avait pas pensé, ayant trop encore l'habitude du C dans lequel on n'a pas d'autre solution) mais la première fait aussi de même non ??? :

Ben, non

Code :

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

1
2
3
4
 
for x in tab1:
    if x in tab2:
        traitement de x (sur plusieurs lignes)

lorsque x est trouvé dans tab2, python ne va pas plus loin, la condition est vraie et ne peut pas être "encore plus vraie".

[tyrtamos]

Bonjour,

Personnellement, je coderais spontanément la 1ère, parce qu'elle est la plus proche de mon raisonnement, et que j’attache plus d'importance à la lisibilité du code qu'à sa rapidité (sauf application critique).

Mais j'aime bien celle-là aussi:

Code :

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

1
2
3
4
for x in set(tab1) & set(tab2):
    print(x)
toto
tata

Pour le temps d'exécution, tout dépend si le traitement du "set" est codé en C ou en Python. Si c'est en C, c'est probablement rapide puisque le calcul n'a lieu qu'une seule fois en début de boucle.

[wiztricks]

Salut,

Sinon je suis certain que les entrées des deux tableau sont toutes uniques (c'est moi qui les crée) donc à priori, set() ne sera pas utile. En fait, tab2 vient d'un formulaire externe qui contient la liste des éléments ayant demandés à être modifiés et tab1 est dans mon module de mise à jour et contient tous les éléments qu'il est possible de modifier. D'où mon algo où je balaye tous les éléments de tab1 tout en ne conservant que ceux qui sont écrits dans tab2 et représentants ceux qui sont réellement modifiés. Et (juste au cas où on me dirait "ben t'as qu'à ne balayer que tab2 ") je précise que tab2 provient d'un formulaire multitables donc il contient aussi des données qui ne concernent pas tab1...

Si on s'amuse à respecter ce que le texte dit, on met à jour les éléments de tab2 qui sont dans tab1.
Donc:

Code :

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

1
2
3
for e in tab2:
     if e in tab1:
        ...update(e)

Puis on réduit le coût du "if e in tab1" en faisant de "tab1" un "set".

- W

[Sve@r]

lorsque x est trouvé dans tab2, python ne va pas plus loin, la condition est vraie et ne peut pas être "encore plus vraie".

T'as raison - J'ai vraiment pas assuré sur ce coup là

Personnellement, je coderais spontanément la 1ère, parce qu'elle est la plus proche de mon raisonnement, et que j’attache plus d'importance à la lisibilité du code qu'à sa rapidité (sauf application critique).

Si on ne regarde que la lisibilité je pense que les 3 sont tout aussi lisibles par un habitué de Python et je trouve la seconde plus agréable car elle économise un bloc d'indentation (tout comme la 3° mais j'ai toujours une petite appréhension concernant le coût d'une liste à la volée). Ceci dit, le truc n'est pas critique puisqu'il n'est appelé qu'une fois quand l'utilisateur valide son formulaire donc ça reste juste pour ma culture perso.

Mais j'aime bien celle-là aussi:

Code :

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

1
2
3
4
for x in set(tab1) & set(tab2):
    print(x)
toto
tata

Alors là c'est excellent. J'avais rapidement vu set sans y attacher plus d'importance et tu viens de m'ouvrir des perspectives. J'ai d'ailleurs immédiatement tenté un set(tab1) | set(tab2) pour comprendre la logique de ces deux opérateurs et j'aime

Si on s'amuse à respecter ce que le texte dit, on met à jour les éléments de tab2 qui sont dans tab1.

C'est tout à fait exact

Donc:

Code :

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

1
2
3
for e in tab2:
     if e in tab1:
        ...update(e)

Je l'avais aussi envisagé. Mais rien ne dit que tab1 est forcément plus petit que tab2.
De plus comme je programme en MVC j'ai un module par table dédié à l'insertion en bdd de la table en question. Donc puisque ce module traite la table je trouve alors normal de le faire commencer par balayer les éléments de la table

Puis on réduit le coût du "if e in tab1" en faisant de "tab1" un "set".

set est-il utile même si tab1 ne contient que des uniques ???

[wiztricks]

set est-il utile même si tab1 ne contient que des uniques ???

Les "set" sont construits avec des "dict": en gros les éléments d'un "set" seront les clés d'un dict.
Plutôt que balayer une liste, on utilise une fonction de "hash" et le "in" sera bien plus rapide.

Par contre est-ce que:

Code :

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

1
2
for e in set(tab1) & set(tab2):
     ... traiter(e)

serait plus rapide que:

Code :

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

1
2
3
for e in tab2:
     if e in tab1:  # tab1 étant un "set"
        ...traiter(e)

Pas si évident.
Et j'ai la flemme de prendre papier/crayon pour calculer puis faire des tests vérifier.

- W

[josmiley]

Je pense même que frozenset serait plus rapide.
Si bien sûr on reste sur des listes comme base, sinon vaut mieux utilider des set plutôt que des listes.

[wiztricks]

Je pense même que frozenset serait plus rapide.

Qu'est ce qui vous fait penser çà?

- W

[Sve@r]

Peut-être parce que frozenset génère des éléments immutables (oui, j'ai un peu regardé ces deux librairies depuis...) et qu'intuitivement on se dit que l'option "mutabilité" (qui est "en plus") prend plus de temps...

[wiztricks]

Peut-être parce que frozenset génère des éléments immutables (oui, j'ai un peu regardé ces deux librairies depuis...) et qu'intuitivement on se dit que l'option "mutabilité" (qui est "en plus") prend plus de temps...

Dans les deux cas on utilise la même fonction de lookup, "intuitivement" çà devrait prendre le même temps.
Si nous n'utilisons rien d'autre d'un "set" que la possibilité de répondre à "e in tab1" rapidement, "tab1" pourrait tout aussi bien être un "dict".
Ses clés étant les éléments de "tab2" associées à une valeur None, un truc comme { k: None for k in tab2 } devrait le faire.

Après, il faut tester pour secouer un peu les intuitions.

- W

[Sve@r]

Après, il faut tester pour secouer un peu les intuitions.

Tu as un million de fois raison

Aussitôt dit, aussitôt fait...

Code python :

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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
tab1=["toto", "titi", "tata", "tutu"]
tab2=["truc", "autre", "toto", "tutu"]
 
def f1():
	for x in tab1:
		if x in tab2: pass
# f1()
 
def f2():
	for x in tab1:
		if x not in tab2: continue
	pass
# f2()
 
def f3():
	for x in [_ for _ in tab1 if _ in tab2]:
		pass
# f3()
 
def f4():
	for x in set(tab1) & set(tab2):
		pass
# f4()
 
def f5():
	for x in frozenset(tab1) & frozenset(tab2):
		pass
# f5()
 
import timeit
for x in xrange(1, 6):
	t=timeit.Timer(
		"f%d()" % x,
		setup="from __main__ import f%d" % x,
	)
	print "f%d: %f - %s" % (
		x,
		t.timeit(number=10000000),
		t.repeat(),
	)
# for

Et le résultat

Code :

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

1
2
3
4
5
6
~/tmp$ ./test.py 
f1: 4.059510 - [0.4054081439971924, 0.40908193588256836, 0.4060049057006836]
f2: 4.048145 - [0.403331995010376, 0.404979944229126, 0.405134916305542]
f3: 5.163005 - [0.5197510719299316, 0.5157828330993652, 0.5131580829620361]
f4: 6.059178 - [0.6119029521942139, 0.6064620018005371, 0.6041991710662842]
f5: 5.965853 - [0.5934197902679443, 0.5979769229888916, 0.5958991050720215]

Et donc aussi improbable que ce que les réflexions émises ici (auxquelles j'adhérais cependant sans réserve) laissaient supposer, c'est la solution 2 (celle qui traite tout le tableau à chaque itération) qui l'emporte d'une courte tête. Et entre les deux solutions à base de set() et de frozenset(), c'est cette dernière qui l'emporte...

[wiztricks]

Salut,

Vos tests sont un peu biaisés par la petite taille de vos listes et le placement des éléments de "tab1" à la fin de "tab2".

J'ai ajouté mon idée:

Code :

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

1
2
3
4
5
xtab1 = set(tab1)
def f6():
    for e in tab2:
        if e in xtab1:
            pass

Un nouveau run chez moi donne:

Code :

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

1
2
3
4
5
6
f1: 5.252403 - [0.5245788704481891, 0.5164992808568734, 0.5184959800893463]
f2: 5.114462 - [0.5175465123215393, 0.5151782281904111, 0.513937540596789]
f3: 7.355939 - [0.7189206722165515, 0.7225366862415008, 0.7235139089571412]
f4: 8.836231 - [0.8808989620478016, 0.8940166960510112, 0.9192848834126508]
f5: 8.594571 - [0.8408473295597645, 0.8376265128517844, 0.8409919038402904]
f6: 3.586140 - [0.3599874729907029, 0.3546208259872472, 0.35752473918633854]

no comment.
Si on joue avec set, frozenset et dict: on trouve:

Code :

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

1
2
3
f6: 35.469311 - [0.35245718281480265, 0.3573478531754972, 0.35261501318981203]
f7: 35.640715 - [0.3511257738245206, 0.35495512812015306, 0.35398453345175085]
f8: 34.962465 - [0.34768581730450876, 0.3419198304545574, 0.34467544109654114]

Il n'y a pas de grandes différences entre set et frozenset.
Par contre, un dict tout nu est un peu plus rapide.

Cela étant, "tester" sur un coin de table et "jaser" sur les résultats, c'est s'amuser un peu pour passer le temps.
Ce qui n'est pas si mal mais de là à en tirer des conclusions, généralisations,...


- W

[fred1599]

On pourrait déjà commencer par manipuler les datas non pas dans des listes mais dans des tuples, où le if...in est sensiblement plus efficace.

[marco056]

Avec un peu plus de données :

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
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
tab0=[]
for i in range(1,10**2):
    chaine="t"+str(i)+"t"+str(i)
    tab0.append(chaine)
 
 
tab1=["t1t1", "t2t2", "t3t3", "t4t4"]
tab2=["truc", "autre", "t2t2", "t4t4"]
 
def f1():
	for x in tab0:
		if x in tab2: pass
# f1()
 
def f2():
	for x in tab0:
		if x not in tab2: continue
	pass
# f2()
 
def f3():
	for x in [_ for _ in tab0 if _ in tab2]:
		pass
# f3()
 
def f4():
	for x in set(tab0) & set(tab2):
		pass
# f4()
 
def f5():
	for x in frozenset(tab0) & frozenset(tab2):
		pass
# f5()
 
xtab1 = set(tab0)
def f6():
    for e in tab2:
        if e in tab0:
            pass
 
import timeit
for x in range(1, 7):
	t=timeit.Timer(
		"f%d()" % x,
		setup="from __main__ import f%d" % x,
	)
	print ("f%d: %f - %s" % (
		x,
		t.timeit(number=10),
		t.repeat(),
	))

On peut trouver :

Code :

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

1
2
3
4
5
6
f1: 0.000061 - [4.945810806006193, 4.942495821000193, 4.94170983100048]
f2: 0.000048 - [4.830011181002192, 4.8285486989989295, 4.827804414999264]
f3: 0.000053 - [4.992208224997739, 4.98677309499908, 4.98823781000101]
f4: 0.000037 - [2.747631245998491, 2.7365035340044415, 2.737330533003842]
f5: 0.000035 - [2.757735881001281, 2.7645705879986053, 2.762515408998297]
f6: 0.000016 - [1.474534033004602, 1.4727850829949602, 1.4733202879942837]

Il n'y a pas photo !