Salut tout le monde,

En divaguant d'exos en exos, j'essaie de comprendre le comportement interne des méthodes in et not in.

On les connaît toutes les 2 avec 2 exemples simples :

liste =  [10,20,30]
10 in liste # True
20 not in liste # False

J'ai voulu faire le pseudo code de ces méthodes. Que voici :

FONCTION est_dans(élément_à_chercher, liste):
  drapeau = Faux
  POUR chaque élément de la liste FAIRE:
    SI élément == élément_à_cherher ALORS:
      drapeau = Vrai
      ARRÊTER POUR
    FIN SI
  FIN POUR
  RETOURNER drapeau
FIN FONCTION

FONCTION n_est_pas_dans(élément_à_chercher, liste):
  drapeau = Vrai
  POUR chaque élément de la liste FAIRE:
    SI élément == élément_à_chercher ALORS:
      drapeau = Faux
      # l'arrêt est inutile : élément_à_chercher pourrait 
      # se trouver en dernière position
    FIN SI
  FIN POUR
  retourner drapeau
FIN FONCTION

Je constate dans mes fonctions que la seconde va forcément au bout de la liste.
Voir le commentaire que je fais.

Je me suis posé la question. Pourquoi avoir une méthode not in alors que logiquement la méthode in est au pire aussi lente que la méthode not in si l'élément à chercher est en dernière position. Dans ce cas, on parcourt toute la liste.

Mais, en y réfléchissant car je n'ai pas de réponse, je pense que ces méthodes natives de Python font bien plus que de la vérification.
Je pense qu'à un moment (en amont, ou à l'appel de la méthode), la liste est triée, et une recherche dichotomique est effectuée.

Le fait, depuis quelques années, qu'un dictionnaire (je sais on sort de la liste, mais ça reste un collecteur) est trié corrobore avec mon idée.

Êtes-vous du même avis ? Qu'en pensez-vous ? Pensez-vous que le fait d'apprendre des algos de tri en cours d'algo prouvent leurs intérêts même si de prime abord leurs utilités ne sautent pas aux yeux ?

Bon, après vérif', in et not in sont des opérateurs équivalant à la méthode __contains__ et à la méthode __not__ (pas certains pour celle-ci : https://docs.python.org/fr/3/library/operator.html#operator.__not__)

-
Edité par CristianoRolando 23 septembre 2021 à 2:35:08

Ça me semble peu vraisemblable que la liste soit triée avant la recherche.
D'accord, le tri prend un peu plus de la moitié du temps.
Mais une recherche dichotomique sur 10 millions se fait en 24 étapes au maximum. Ça se ferait en moins d'une milliseconde.
-
from time import perf_counter
n = 10_000_000
L = [n-i for i in range(n)]   # Placés en ordre inverse.
begin=perf_counter()
if n+1 not in L: pass
print('not', round(perf_counter()-begin, 3), 'secondes')
begin=perf_counter()
if 1 in L: pass
print('in', round(perf_counter()-begin, 3), 'secondes')
begin=perf_counter()
L.sort()
print('sort', round(perf_counter()-begin, 3), 'secondes')
-
not 0.103 secondes                                                                                                      
in 0.107 secondes                                                                                                       
sort 0.064 secondes

Bonjour.

Le plus simple pour avoir les réponses ne sserait-il pas d'aller directement voir le code de cette fonction ?

not in ce n'est pas un opérateur mais une imbrication de deux, not(in ...)

PB68 a écrit:

Bonjour.

Le plus simple pour avoir les réponses ne sserait-il pas d'aller directement voir le code de cette fonction ?

Effectivement et elle est ICI et c'est une bête recherche séquentielle. Le tri était improbable car une liste peut contenir des éléments non comparables. Pour des objets comme des chaînes, l'opérateur in utilise un algorithme beaucoup plus sophistiqué (Boyer-Moore je pense)

Plus généralement (quelque soit le type d'objet), "a in b" c'est équivalent à "b.__contains__(a)".
Et "a not in b" c'est "not b.__contains__(a)", donc c'est effectivement le même algo.

Pour revenir aux listes, en supposant que les éléments sont comparables, l'algo serait moins performant avec un tri.
Par ce que list.sort a une complexité de O(n.log(n)), et list.__contains__ c'est O(n).

Pour les dictionnaires, je n'ai pas bien compris ce que tu veux dire,  mais ils ne sont pas triés, ils sont ordonnés.

josmiley a écrit:

not in ce n'est pas un opérateur mais une imbrication de deux, not(in ...)

Presque : not in est un véritable opérateur du langage Python avec sa priorité, différente de not mais la même que celle de in. Mais effectivement la sémantique de a not in L est not a in L (sans parenthèses nécessaires puisque le priorité de in est plus forte) comme la doc le dit (d'ailleurs, deux fois dans le même paragraphe).

Dans certaines circonstances, in peut être utilisé sans que __contains__ le soit, cf. la même section de la doc référencée ci-dessus.

Ah oui tiens avec getitem . Mais du coup ça ne cherche pas dans les index négatifs.

-
Edité par thelinekioubeur 23 septembre 2021 à 15:20:44

PascalOrtiz a écrit:

josmiley a écrit:

not in ce n'est pas un opérateur mais une imbrication de deux, not(in ...)

Presque : not in est un véritable opérateur du langage Python avec sa priorité, différente de not mais la même que celle de in. Mais effectivement la sémantique de a not in L est not a in L (sans parenthèses nécessaires puisque le priorité de in est plus forte) comme la doc le dit (d'ailleurs, deux fois dans le même paragraphe).

Dans certaines circonstances, in peut être utilisé sans que __contains__ le soit, cf. la même section de la doc référencée ci-dessus.

En ce moment j'en apprends tous les jours. Par exemple, je viens de découvrir que __class__ contient la class de la méthode. ainsi, en utilisant __class__ au lieu de nom de la class dans les méthodes, si un jour je change le nom de la class, j'ai pas besoin de modifier les méthodes.

Ouais fin perso je préfère utiliser type plutôt que __class__, par ex :

class Foo:
    def __init__(self, a):
        self.a = a
    def __repr__(self):
        return f"{type(self).__name__}({self.a})"

type(self) retourne la class de self, alors que __class__ donne la class dans le scope en cours ... de ce que j'en ai déduit.

class A:
	def foo(self):
		print('__class__',__class__)
		print('self type',type(self))

class B(A):
	...


bar = B()
bar.foo()

-
Edité par josmiley 24 septembre 2021 à 11:37:24

Ah oui, je pensais que tu parlais de l'attribut self.__class__

Franchement, merci à tous pour vos réponses. Je vais bien les relire mieux concentré, car vos niveaux sont supérieurs au mien.