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

Question

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 llame con

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

Supuse 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 de ejecución de lo siguiente

• Indexación: list Icono de ejemplo: xx<
• Apareciendo desde el final: list.pop()
• Saltos desde el principio: list.pop(0)
• Ampliando la lista: list.append(x)

Para crédito adicional, empalme o saltos arbitrarios.

Answer 1

hay una tabla muy detallada en el wiki de python que responde a tu pregunta.

Sin embargo, en su ejemplo particular, debe usar enumerar para obtener un índice de un iterable dentro de un bucle. como asi:

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

Answer 2

La respuesta es " indefinida " ;. 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 tienen Se ha implementado como contiguo vectores en las implementaciones en C de Python hasta ahora.

• No estoy diciendo que la O ( ) Los comportamientos de estas cosas deben ser guardado un secreto o nada Pero tu Necesito 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)

Answer 3

Las listas son de hecho O (1) para indexar: se implementan como un vector con una asignación global proporcional, por lo que se desempeñan de la manera que esperaría. La razón probable por la que encontraste este código más lento de lo que esperabas 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, enumerate

Answer 4

No puedo comentar aún, así que

si necesita índice y valor, use enumerar:

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

Answer 5

La lista de Python en realidad no es más que matrices. Por lo tanto,

la indexación toma O (1)

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

Consulte el siguiente enlace para obtener más información:

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