Coût de la fonction len ()

Quel est le coût de la len()fonction des modules intégrés Python? (liste / tuple / chaîne / dictionnaire)

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 setet d'autres tels que array.array.

L'appel de len () sur ces types de données est O (1) dans CPython , l'implémentation 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 TimeComplexity Python

Tous ces objets gardent une trace de leur propre longueur. Le temps pour extraire la longueur est petit (O (1) en notation big-O) et consiste principalement en [description grossière, écrite en termes Python, pas en termes C]: recherchez "len" dans un dictionnaire et envoyez-le au Built_in len fonction qui recherchera la __len__méthode de l'objet et appellera cela ... tout ce qu'il a à faire estreturn self.length

Les mesures ci-dessous fournissent une preuve qui len()est O (1) pour les structures de données souvent utilisées.

Une note concernant timeit: Lorsque l' -sindicateur est utilisé et que deux chaînes sont passées à timeitla première chaîne, elle n'est exécutée qu'une seule fois et n'est pas chronométrée.

Liste:

$ python -m timeit -s "l = range(10);" "len(l)"
10000000 loops, best of 3: 0.0677 usec per loop

$ python -m timeit -s "l = range(1000000);" "len(l)"
10000000 loops, best of 3: 0.0688 usec per loop

Tuple:

$ python -m timeit -s "t = (1,)*10;" "len(t)"
10000000 loops, best of 3: 0.0712 usec per loop

$ python -m timeit -s "t = (1,)*1000000;" "len(t)"
10000000 loops, best of 3: 0.0699 usec per loop

Chaîne:

$ python -m timeit -s "s = '1'*10;" "len(s)"
10000000 loops, best of 3: 0.0713 usec per loop

$ python -m timeit -s "s = '1'*1000000;" "len(s)"
10000000 loops, best of 3: 0.0686 usec per loop

Dictionnaire (dictionnaire-compréhension disponible en 2.7+):

$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(10))};" "len(d)"
10000000 loops, best of 3: 0.0711 usec per loop

$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(1000000))};" "len(d)"
10000000 loops, best of 3: 0.0727 usec per loop

Tableau:

$ python -mtimeit -s"import array;a=array.array('i',range(10));" "len(a)"
10000000 loops, best of 3: 0.0682 usec per loop

$ python -mtimeit -s"import array;a=array.array('i',range(1000000));" "len(a)"
10000000 loops, best of 3: 0.0753 usec per loop

Set (set-comprehension disponible en 2.7+):

$ python -mtimeit -s"s = {i for i in range(10)};" "len(s)"
10000000 loops, best of 3: 0.0754 usec per loop

$ python -mtimeit -s"s = {i for i in range(1000000)};" "len(s)"
10000000 loops, best of 3: 0.0713 usec per loop

Deque:

$ python -mtimeit -s"from collections import deque;d=deque(range(10));" "len(d)"
100000000 loops, best of 3: 0.0163 usec per loop

$ python -mtimeit -s"from collections import deque;d=deque(range(1000000));" "len(d)"
100000000 loops, best of 3: 0.0163 usec per loop

len est un O (1) car dans votre RAM, les listes sont stockées sous forme de tables (série 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 n'a donc qu'à la rechercher.

J'ai pensé que len () en Python dépend de la taille de la liste, donc je stocke toujours la longueur dans une variable si j'utilise plusieurs fois. Mais aujourd'hui, lors du débogage, j'ai remarqué l'attribut __len__ dans l'objet liste, donc len () doit simplement le récupérer, ce qui rend la complexité O (1). Je viens donc de googler si quelqu'un l'a déjà demandé et est tombé sur ce post.