optimisation if item est dans list

Bonjour

je viens de lire cet article "les anti-patterns en python"

Bad

Code:

---

1 2 3 4 5

l = [1, 2, 3, 4] if 4 in l: print("The number 4 is in the list.") else: print("The number 4 is NOT in the list.")

---

Good

Code:

---

1 2 3 4 5

s = {1, 2, 3, 4} if 4 in s: print("The number 4 is in the list.") else: print("The number 4 is NOT in the list.")

---

Puisque je ne fais jamais de if id in set(ma_liste): je me suis demandé si cela était vraiement un anti-pattern et surtout si cette optimisation était si bonne que l'on pouvais parler d"anti-pattern"

Mon petit test :
- liste longue / liste courte
- elements str / int
- item à trouver en fin ou début de liste (oui, cela compte :lol:)

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

import timeit   tests = ( (10000, lambda x: x), (10000, lambda x: str(x)), (100, lambda x: x), (100, lambda x: str(x)), (10, lambda x: x), (10, lambda x: str(x)), )   def get_by_list(id, conteneur): if id in conteneur: return True return False   def resultats(time_list, time_set, liste, find): msg = f'recherche "{find}" sur "{len(liste)}" items {type(liste[0])}' calcul = time_list / time_set print("\033[1;30;40mlist:", time_list) print("set :", time_set, "\033[0m") print(f"-> {calcul:.1f} fois plus rapide {msg}")     for test in tests: # liste = tuple(test[1](x) for x in range(test[0])) liste = [test[1](x) for x in range(test[0])] liste_set = set(liste)   find = str((len(liste)//100)+2) time_list = timeit.timeit(lambda: get_by_list(find, liste), number=1000) time_set = timeit.timeit(lambda: get_by_list(find, liste_set), number=1000) resultats(time_list, time_set, liste, find)   find = str(len(liste)-len(liste)//10) time_list = timeit.timeit(lambda: get_by_list(find, liste), number=1000) time_set = timeit.timeit(lambda: get_by_list(find, liste_set), number=1000) resultats(time_list, time_set, liste, find) print()

---

resultat... IL FAUT TESTER :ptdr:

sur une "petite" liste, ok il y a un gain de 2x, mais avec des valeurs si petites que j'ai du mal à parler d'anti-pattern et même d'optimisation
Pour une grande liste, ok la différence est claire

ps: dans son exemple, il écrit l = [1, 2, 3, 4] et moi, par défaut je fais toujours par défaut un tuple ... donc il illustre un antipattern avec un anti-pattern (du même type) :roll: ?
J'ai donc refait le test avec un tuple à la place de la liste, pas de différence avec la liste

Salut,

Citation:

---

Envoyé par papajoker

Puisque je ne fais jamais de if id in set(ma_liste):

---

Vous n'allez pas convertir la liste en set pour faire un seul test d'appartenance: la recherche dans la liste simple aura une complexité O(n/2) alors qu'il faudra balayer toute la liste pour fabriquer le set pour ensuite avoir une complexité en O(1).

La structure de donnée choisie doit être "pertinente" par rapport aux opérations qu'on fera dessus (et si on aura plusieurs "in", un "set" ou un "dict" seront plus efficaces).

- W

Bonjour,

A noter que si la liste est longue et déjà triée, une recherche par dichotomie sera très rapide Par exemple, une telle recherche sur 1024 éléments ne nécessitera que 10 tests puisque 2**10=1024 (au lieu d'une moyenne de 512 tests). En plus du résultat présent/absent, cette recherche donnera l'emplacement de l'élément recherché s'il est présent, ou l'emplacement où il devrait être s'il est absent. Voir le module bisect.

A part ça, merci pour l'article qui est très intéressant.

Bonjour

Citation:

---

Envoyé par tyrtamos

cette recherche donnera l'emplacement de l'élément recherché s'il est présent, ou l'emplacement où il devrait être s'il est absent

---

Ca je trouve ça hyper classe :D (bon je n'en vois pas l'utilité mais j'adore :mouarf:)

Citation:

---

Envoyé par tyrtamos

merci pour l'article qui est très intéressant.

---

Euh là moins. Quand je vois "Good" pour le test if flag is True...:weird: Pour moi c'est if flag simplement. Surtout que tester spécifiquement True peut amener des erreurs...

Code:

---

1 2 3 4 5

>>> result=123 >>> print("ok" if result is True else "bad") bad >>> print("ok" if result else "bad") ok

---

Et pour le reste c'est plutôt rempli de platitudes et de lieux communs (style ne pas faire exec("print(truc)") mais simplement print(truc)) bon ben oui c'est vrai mais de là à faire un article là desus... :?

Bonjour Sve@r

Citation:

---

Envoyé par Sve@r

bon je n'en vois pas l'utilité mais j'adore :mouarf:

---

Par exemple, pour insérer un nouvel élément en gardant la liste triée (mais pas pour trier toute la liste, car .sort(...) est plus rapide qu'un tri par insertion).

Citation:

---

Envoyé par Sve@r

Et pour le reste c'est plutôt rempli de platitudes et de lieux communs...

---

C'est vrai que j'applique déjà la grande majorité des recommandations, mais ce n'est pas mal qu'un tel document existe pour ceux qui démarrent.