Costo de la función len ()

¿Cuál es el costo de la len()función para las incorporaciones de Python? (lista / tupla / cadena / diccionario)

Es O (1) (tiempo constante, no depende de la longitud real del elemento, muy rápido) en cada tipo que ha mencionado, más sety otros como array.array.

Llamar a len () en esos tipos de datos es O (1) en CPython , la implementación más común del lenguaje Python. Aquí hay un enlace a una tabla que proporciona la complejidad algorítmica de muchas funciones diferentes en CPython:

Página Wiki de TimeComplexity Python

Todos esos objetos siguen su propia longitud. El tiempo para extraer la longitud es pequeño (O (1) en notación big-O) y consiste principalmente en [descripción aproximada, escrita en términos de Python, no en términos de C]: busque "len" en un diccionario y envíelo al función built_in len que buscará el __len__método del objeto y lo llamará ... todo lo que tiene que hacer esreturn self.length

Las siguientes mediciones proporcionan evidencia de que len()es O (1) para estructuras de datos que se utilizan con frecuencia.

Una nota con respecto a timeit: cuando -sse usa el indicador y se pasan dos cadenas a timeitla primera cadena, se ejecuta solo una vez y no se cronometra.

Lista:

$ 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

Tupla:

$ 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

Cuerda:

$ 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

Diccionario (comprensión del diccionario 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

Formación:

$ 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

Conjunto (conjunto de comprensión 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 es un O (1) porque en su RAM, las listas se almacenan como tablas (series de direcciones contiguas). Para saber cuándo se detiene la mesa, la computadora necesita dos cosas: longitud y punto de inicio. Es por eso que len () es un O (1), la computadora almacena el valor, por lo que solo necesita buscarlo.

He estado pensando en len () en Python depende del tamaño de la lista, por lo que siempre almaceno la longitud en una variable si la uso varias veces. Pero hoy durante la depuración, noté el atributo __len__ en el objeto de la lista, por lo que len () solo debe buscarlo, lo que hace que la complejidad sea O (1). Así que busqué en Google si alguien ya lo ha preguntado y me encontré con esta publicación.