Complejidad de len () con respecto a conjuntos y listas

La complejidad de len() con respecto a conjuntos y listas es igualmente O (1). ¿Por qué 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 índice de referencia en particular, ya que lleva más tiempo construir conjuntos que listas y el índice de referencia también lo tiene en cuenta?

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

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

Usa 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 statement bastante rápida. El proceso de medición de su velocidad puede estar sujeto a “ruido”. Considere que el código ejecutado (y medido) por timeit es equivalente a lo 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, es mejor medir len(a); len(a); ...; len(a) len(a); len(a); ...; len(a) len(a); len(a); ...; len(a) (se repite 100 veces aproximadamente) para que el cuerpo del bucle for tome una cantidad de tiempo considerablemente mayor que la del 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 indican 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 cuánto tiempo sea la lista a , len(a) realiza el mismo número asintótico de pasos. Y no importa cuánto tiempo sea el conjunto b , len(b) realiza el mismo número asintótico de pasos. Sin embargo, el algoritmo para calcular el tamaño de las listas y los conjuntos puede ser diferente, lo que da como resultado diferentes actuaciones (timeit muestra que este no es el caso, sin embargo, esto puede ser una posibilidad).

Por último,

Si la creación de un objeto establecido toma 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 asegurar una inserción y búsqueda O (1) promedio): 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 los hashes, construir la tabla hash, buscarla para evitar la inserción de eventos duplicados, etc. Por el contrario, las listas en CPython se implementan como un conjunto simple de punteros que son malloc() ed y realloc() ed según sea necesario.

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 preguntar. También se mide la creación de los objetos. Y es un poco más lento crear un conjunto que una lista.

Use esto con la marca -s para cronometrar 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 se considera la función len , y los resultados son prácticamente iguales ya que no tomamos en cuenta el tiempo de creación del conjunto / lista.

Sí, tienes razón, es más debido al diferente tiempo requerido para crear los objetos de set y list de python. Como un punto de referencia más justo, puede usar el módulo timeit y pasar los objetos utilizando 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í, pasemos por el mundo de los pitones. En realidad, el objeto establecido utiliza una tabla hash y una tabla hash utiliza 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 llevarán mucho tiempo . Mientras que para crear una lista de python, simplemente cree una secuencia de objetos a los que pueda acceder con indexación.

Puede consultar más detalles sobre la función set_lookkey desde el código fuente de Cpython .

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


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 y f(x)=4x+20 es O (1) y significa que ambas son ecuaciones lineales bur, como se puede ver, la primera función tiene un tamaño bastante mayor Pendiente, y para una misma entrada darán un resultado diferente.

Permítame 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.1 s, 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 del tamaño 1 que en procesar la lista del tamaño 1000 ; de manera similar, toma el mismo tiempo para procesar un diccionario de tamaño 1 que para procesar un diccionario de tamaño 1000 .

No se da ninguna 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 hacia abajo en la stack de llamadas puede variar según el tipo de datos.

Incidentalmente, esta ambigüedad se elimina en idiomas tipificados estáticamente en los que ClassA.size() y ClassB.size() son para todos los propósitos y propósitos, dos métodos diferentes.

Eliminar la statement len(a) . El resultado es prácticamente el mismo. Un conjunto debe estar marcado para conservar solo elementos distintos para que sea más lento.

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ás tratando de probar la O (1) -ness, estarías 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 poca data, el tiempo empleado es bastante similar. Por otras publicaciones, esto separa el tiempo de configuración del tiempo de prueba, pero no llega tan lejos como para reducir el ruido de tiempo de len vs tiempo de bucle.