Costo de la función len()
¿ Cuál es el costo de la len()función para las funciones integradas de Python? (lista/tupla/cadena/diccionario)
Es O(1) (tiempo constante, que no depende de la longitud real del elemento, muy rápido) en cada tipo que ha mencionado, además setde otros como array.array.
Llamar len()a esos tipos de datos es O(1) en CPython , la implementación oficial y 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 realizan un seguimiento de su propia longitud. El tiempo para extraer la longitud es pequeño (O(1) en notación O grande) y consiste principalmente en [descripción aproximada, escrita en términos de Python, no en términos de C]: buscar "len" en un diccionario y enviarlo al función len incorporada 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 de uso frecuente.
Una nota sobre timeit: Cuando -sse usa la bandera y se pasan dos cadenas, timeitla primera cadena se ejecuta solo una vez y no está cronometrada.
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
Cadena:
$ 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 (diccionario-comprensión 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 (comprensión de conjuntos 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
