Coût de la fonction len()

Question

Quel est le coût de la fonction len() pour les objets intégrés Python? (liste/tuple/chaîne de caractères/dictionnaire)

Answer 1

C'est O(1) (temps constant, ne dépendant pas de la longueur réelle de l'élément - très rapide) sur chaque type que vous avez mentionné, plus set et d'autres comme array.array.

Answer 2

Appeler len() sur ces types de données est O(1) dans CPython, l'implémentation officielle et la plus courante du langage Python. Voici un lien vers un tableau qui fournit la complexité algorithmique de nombreuses fonctions différentes dans CPython :

Page Wiki Python sur la complexité temporelle

Answer 3

Tous ces objets gardent une trace de leur propre longueur. Le temps pour extraire la longueur est court (O(1) en notation big-O) et consiste principalement en [description approximative, écrite en termes de Python, pas en termes de C]: recherchez "len" dans un dictionnaire et envoyez-le à la fonction len intégrée qui recherchera la méthode __len__ de l'objet et l'appellera ... tout ce qu'il a à faire est return self.length

Answer 4

Les mesures ci-dessous fournissent des preuves que len() est O(1) pour les structures de données souvent utilisées.

Une note concernant timeit : lorsque le drapeau -s est utilisé et que deux chaînes sont passées à timeit, la première chaîne est exécutée une seule fois et n'est pas chronométrée.

Liste :

$ python -m timeit -s "l = range(10);" "len(l)"
10000000 boucles, meilleure de 3: 0,0677 usec par boucle

$ python -m timeit -s "l = range(1000000);" "len(l)"
10000000 boucles, meilleure de 3: 0,0688 usec par boucle

Tuple :

$ python -m timeit -s "t = (1,)*10;" "len(t)"
10000000 boucles, meilleure de 3: 0,0712 usec par boucle

$ python -m timeit -s "t = (1,)*1000000;" "len(t)"
10000000 boucles, meilleure de 3: 0,0699 usec par boucle

Chaîne :

$ python -m timeit -s "s = '1'*10;" "len(s)"
10000000 boucles, meilleure de 3: 0,0713 usec par boucle

$ python -m timeit -s "s = '1'*1000000;" "len(s)"
10000000 boucles, meilleure de 3: 0,0686 usec par boucle

Dictionnaire (la compréhension de dictionnaire est disponible dans 2.7+) :

$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(10))};" "len(d)"
10000000 boucles, meilleure de 3: 0,0711 usec par boucle

$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(1000000))};" "len(d)"
10000000 boucles, meilleure de 3: 0,0727 usec par boucle

Tableau :

$ python -mtimeit -s"import array;a=array.array('i',range(10));" "len(a)"
10000000 boucles, meilleure de 3: 0,0682 usec par boucle

$ python -mtimeit -s"import array;a=array.array('i',range(1000000));" "len(a)"
10000000 boucles, meilleure de 3: 0,0753 usec par boucle

Ensemble (la compréhension d'ensemble est disponible dans 2.7+) :

$ python -mtimeit -s"s = {i for i in range(10)};" "len(s)"
10000000 boucles, meilleure de 3: 0,0754 usec par boucle

$ python -mtimeit -s"s = {i for i in range(1000000)};" "len(s)"
10000000 boucles, meilleure de 3: 0,0713 usec par boucle

Deque :

$ python -mtimeit -s"from collections import deque;d=deque(range(10));" "len(d)"
100000000 boucles, meilleure de 3: 0,0163 usec par boucle

$ python -mtimeit -s"from collections import deque;d=deque(range(1000000));" "len(d)"
100000000 boucles, meilleure de 3: 0,0163 usec par boucle

Answer 5

len est un O(1) car dans votre RAM, les listes sont stockées sous forme de tables (séries d'adresses contiguës). Pour savoir quand la table s'arrête, l'ordinateur a besoin de deux choses : la longueur et le point de départ. C'est pourquoi len() est un O(1), l'ordinateur stocke la valeur, il lui suffit donc de la rechercher.