Petite question d'optimisation sur les tableaux

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:

---

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:

---

1 2 3

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

---

Code:

---

1 2 3

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

---

Code:

---

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 ?

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

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.

Bonjour,

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

Code:

---

1 2 3 4

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

---

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 :wow:") 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 :applo:

Citation:

---

Envoyé par 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 ??? :

---

Ben, non

Code:

---

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

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:

---

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.

Salut,

Citation:

---

Envoyé par Sve@r

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 :wow:") 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:

---

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

Citation:

---

Envoyé par VinsS

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à :whistle2:

Citation:

---

Envoyé par tyrtamos

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.

Citation:

---

Envoyé par tyrtamos

Mais j'aime bien celle-là aussi:

Code:

---

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 :applo:

Citation:

---

Envoyé par wiztricks

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

Citation:

---

Envoyé par wiztricks

Donc:

Code:

---

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

Citation:

---

Envoyé par wiztricks

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

Citation:

---

Envoyé par Sve@r

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:

---

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

---

serait plus rapide que:

Code:

---

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

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.

Citation:

---

Envoyé par josmiley

Je pense même que frozenset serait plus rapide.

---

Qu'est ce qui vous fait penser çà?

- W

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

Citation:

---

Envoyé par 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...

---

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

Citation:

---

Envoyé par wiztricks

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

---

Tu as un million de fois raison :applo:

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

Code:

---

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:

---

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

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:

---

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:

---

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:

---

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

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.

Avec un peu plus de données :

Code:

---

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:

---

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 !