¿Cuál es la complejidad del tiempo de ejecución de las funciones de la lista de python?

Estaba escribiendo una función de python que se parecía a esto

def foo(some_list): for i in range(0, len(some_list)): bar(some_list[i], i) 

para que se llamara con

 x = [0, 1, 2, 3, ... ] foo(x) 

Yo había asumido que el acceso al índice de las listas era O(1) , pero me sorprendió descubrir que para las listas grandes esto era significativamente más lento de lo que esperaba.

Mi pregunta, entonces, es cómo se implementan las listas de python y cuál es la complejidad en tiempo de ejecución de lo siguiente

  • Indexación: list[x]
  • Popping desde el final: list.pop()
  • Popping desde el principio: list.pop(0)
  • Ampliando la lista: list.append(x)

Para crédito extra, empalmes o pops arbitrarios.

Hay una tabla muy detallada en la wiki de python que responde a su pregunta.

Sin embargo, en su ejemplo particular, debe usar enumerate para obtener un índice de un iterable dentro de un bucle. al igual que:

 for i, item in enumerate(some_seq): bar(item, i) 

La respuesta es “indefinido”. El lenguaje Python no define la implementación subyacente. Aquí hay algunos enlaces a un hilo de la lista de correo en los que podría estar interesado.

  • Es cierto que las listas de Python se han implementado como vectores contiguos en las implementaciones en C de Python hasta el momento.

  • No estoy diciendo que los comportamientos O () de estas cosas deban mantenerse en secreto ni nada. Pero debes interpretarlos en el contexto de cómo funciona Python en general.

Además, la forma más Pythonic de escribir su bucle sería esta:

 def foo(some_list): for item in some_list: bar(item) 

De hecho, las listas son O (1) para indexar; se implementan como un vector con una ubicación proporcional, por lo que se desempeñan de la forma que esperaría. La razón más probable por la que encontró este código más lento de lo que esperaba es la llamada a ” range(0, len(some_list)) “.

range() crea una nueva lista del tamaño especificado, por lo que si some_list tiene 1,000,000 artículos, creará una nueva lista de millones de artículos por adelantado. Este comportamiento cambia en python3 (el rango es un iterador), para el cual el equivalente de python2 es xrange , o incluso mejor para su caso, enumere

No puedo comentar aún, así que

Si necesita índice y valor, utilice enumerar:

 for idx, item in enumerate(range(10, 100, 10)): print idx, item 

Lista de Python en realidad nada más que matrices. Así,

la indexación toma O (1)

para pop y adjuntar nuevamente debe ser O (1) según los documentos

Echa un vistazo a siguiente enlace para más detalles:

http://dustycodes.wordpress.com/2012/03/31/pythons-data-structures-complexity-analysis/