python - guia - qgis manual

Complejidad de len() con respecto a conjuntos y listas

Question

La complejidad de len() con respecto a conjuntos y listas es igualmente O (1). ¿Cómo es que lleva más tiempo procesar conjuntos?

~$ python -m timeit "a=[1,2,3,4,5,6,7,8,9,10];len(a)"
10000000 loops, best of 3: 0.168 usec per loop
~$ python -m timeit "a={1,2,3,4,5,6,7,8,9,10};len(a)"
1000000 loops, best of 3: 0.375 usec per loop

¿Está relacionado con el punto de referencia particular, como en, toma más tiempo construir conjuntos que listas y el punto de referencia también lo tiene en cuenta?

Si la creación de un objeto conjunto lleva más tiempo en comparación con la creación de una lista, ¿cuál sería la razón subyacente?

Answer 1

Elimine la declaración len(a) . El resultado es prácticamente el mismo. Un conjunto debe ser procesado para retener solo elementos distintos, por lo que es más lento.

Answer 2

Las líneas relevantes son http://svn.python.org/view/python/trunk/Objects/setobject.c?view=markup#l640

640 static Py_ssize_t
641 set_len(PyObject *so)
642 {
643 return ((PySetObject *)so)->used;
644 }

y http://svn.python.org/view/python/trunk/Objects/listobject.c?view=markup#l431

431 static Py_ssize_t
432 list_length(PyListObject *a)
433 {
434 return Py_SIZE(a);
435 }

Ambos son solo una búsqueda estática.

Entonces, ¿cuál es la diferencia que puede pedir? Usted también mide la creación de los objetos. Y es un poco más lento crear un conjunto que una lista.

Answer 3

Muchos han notado que O (1) no se trata de rendimiento en diferentes tipos de datos , sino de rendimiento en función de diferentes tamaños de entrada .

Si está tratando de probar O-1 -ness, estaría buscando algo más como

~$python -m timeit --setup "a=list(range(1000000))" "len(a)"
10000000 loops, best of 3: 0.198 usec per loop
~$python -m timeit --setup "a=list(range(1))" "len(a)"
10000000 loops, best of 3: 0.156 usec per loop

Big data o little data, el tiempo empleado es bastante similar. Según otras publicaciones, esto separa el tiempo de configuración del tiempo de prueba, pero no llega tan lejos como para reducir el ruido del tiempo de len frente al tiempo de bucle.

Answer 4

Permítanme componer las excelentes respuestas aquí: O(1) solo le informa sobre el orden de crecimiento con respecto al tamaño de la entrada.

O(1) en particular solo significa tiempo constante con respecto al tamaño de la entrada . Un método siempre puede tomar 0.1s, para cualquier entrada, y otro puede tomar 1000 años para cualquier entrada, y ambos serían O(1)

En este caso, si bien la documentación tiene cierto grado de ambigüedad , significa que el método tarda aproximadamente el mismo tiempo en procesar una lista de tamaño 1 que en procesar la lista de tamaño 1000 ; de manera similar, se tarda el mismo tiempo en procesar un diccionario de tamaño 1 que en procesar un diccionario de tamaño 1000 .

No se ofrece garantía con respecto a los diferentes tipos de datos .

Esto no es sorprendente ya que la implementación de len() en algún momento de la pila de llamadas puede diferir según el tipo de datos.

Por cierto, esta ambigüedad se elimina en lenguajes estáticamente tipados donde ClassA.size() y ClassB.size() son para todos los intentos y propósitos dos métodos diferentes.

Answer 5

Sí, tiene razón, es más debido al tiempo diferente requerido para crear el set y list objetos por python. Como punto de referencia más justo, puede usar el módulo timeit y pasar los objetos usando setup argumento de setup :

from timeit import timeit
print ''1st: '' ,timeit(stmt="len(a)", number=1000000,setup="a=set([1,2,3]*1000)")
print ''2nd : '',timeit(stmt="len(a)", number=1000000,setup="a=[1,2,3]*1000")

resultado:

1st: 0.04927110672
2nd : 0.0530669689178

Y si quieres saber por qué es así, veamos el mundo de Python. El objeto realmente establecido usa una tabla hash y una tabla hash usa una función hash para crear los valores hash de los elementos y asignarlos a los valores y en este acuerdo llamar a la función y calcular los valores hash y algunas otras tareas adicionales tomarán mucho tiempo . Mientras que para crear una lista de python solo cree una secuencia de objetos a los que pueda acceder con indexación.

Puede consultar más detalles sobre la función http://svn.python.org/view/python/trunk/Objects/setobject.c?view=markup#l640 desde el http://svn.python.org/view/python/trunk/Objects/setobject.c?view=markup#l640 .

También tenga en cuenta que si dos algoritmos tienen la misma complejidad, no significa que ambos algoritmos tengan exactamente el mismo tiempo de ejecución o velocidad de ejecución. ¹

_{porque big O notación big O describe el comportamiento limitante de una función y no muestra la ecuación de complejidad exacta. Por ejemplo, la complejidad de las siguientes ecuaciones f(x)=100000x+1 f(x)=4x+20 es O (1) y significa que ambas son ecuaciones lineales pero como puede ver, la primera función tiene una función bastante mayor pendiente, y para una misma entrada darán un resultado diferente.}

Answer 6

Use esto con la bandera -s para timeit sin tener en cuenta la primera cadena:

~$ python -mtimeit -s "a=range(1000);" "len(a)"
10000000 loops, best of 3: 0.0424 usec per loop
↑ 

~$ python -mtimeit -s "a={i for i in range(1000)};" "len(a)"
10000000 loops, best of 3: 0.0423 usec per loop
↑ 

Ahora solo está considerando solo la función len , y los resultados son más o menos los mismos, ya que no tomamos en cuenta el tiempo de creación del conjunto / lista.

Answer 7

En primer lugar, no ha medido la velocidad de len() , ha medido la velocidad de crear una lista / conjunto junto con la velocidad de len() .

Use el argumento timeit de timeit :

$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "len(a)"
10000000 loops, best of 3: 0.0369 usec per loop
$ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "len(a)"
10000000 loops, best of 3: 0.0372 usec per loop

Las declaraciones que pasa a --setup se ejecutan antes de medir la velocidad de len() .

En segundo lugar, debe tener en cuenta que len(a) es una declaración bastante rápida. El proceso de medir su velocidad puede estar sujeto a "ruido". Considere que el código ejecutado (y medido) por tiempo es equivalente al siguiente:

for i in itertools.repeat(None, number):
len(a)

Debido a que tanto len(a) como itertools.repeat(...).__next__() son operaciones rápidas y sus velocidades pueden ser similares, la velocidad de itertools.repeat(...).__next__() puede influir en los tiempos.

Por esta razón, será mejor que mida len(a); len(a); ...; len(a) len(a); len(a); ...; len(a) len(a); len(a); ...; len(a) (repetido 100 veces más o menos) para que el cuerpo del bucle for tome una cantidad de tiempo considerablemente mayor que el iterador:

$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "$(for i in {0..1000}; do echo "len(a)"; done)"
10000 loops, best of 3: 29.2 usec per loop
$ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "$(for i in {0..1000}; do echo "len(a)"; done)"
10000 loops, best of 3: 29.3 usec per loop

(Los resultados aún dicen que len() tiene el mismo rendimiento en listas y conjuntos, pero ahora está seguro de que el resultado es correcto).

En tercer lugar, es cierto que la "complejidad" y la "velocidad" están relacionadas, pero creo que está creando cierta confusión. El hecho de que len() tenga complejidad O (1) para listas y conjuntos no implica que deba ejecutarse con la misma velocidad en listas y conjuntos.

Significa que, en promedio, no importa qué tan larga sea la lista a , len(a) realiza el mismo número asintótico de pasos. Y no importa qué tan largo sea el conjunto b , len(b) realiza el mismo número asintótico de pasos. Pero el algoritmo para calcular el tamaño de las listas y conjuntos puede ser diferente, lo que resulta en diferentes desempeños (el tiempo muestra que este no es el caso, sin embargo, puede ser una posibilidad).

Finalmente,

Si la creación de un objeto conjunto lleva más tiempo en comparación con la creación de una lista, ¿cuál sería la razón subyacente?

Un conjunto, como sabes, no permite elementos repetidos. Los conjuntos en CPython se implementan como tablas hash (para garantizar la inserción y búsqueda promedio de O (1) ): construir y mantener una tabla hash es mucho más complejo que agregar elementos a una lista.

Específicamente, al construir un conjunto, debe calcular hash, construir la tabla hash, buscarla para evitar insertar eventos duplicados, etc. Por el contrario, las listas en CPython se implementan como una simple matriz de punteros que se malloc() ed y realloc() ed según sea necesario.