¿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 parecía algo como esto

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

de modo que se ha llamado con

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

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

Mi pregunta es, entonces, cómo son se implementan las listas de Python, y cuál es la complejidad de tiempo de ejecución de las siguientes

• Indexación: list[x]
• Apareciendo desde el final: list.pop()
• Apareciendo de la comenzando: list.pop(0)
• ampliación de la lista: list.append(x)

Para crédito adicional, empalme o saltos arbitrarios.

Answer 1

hay a very detailed table on python wiki que responde a su pregunta.

Sin embargo, en el ejemplo particular se debe utilizar enumerate para obtener un índice de un iterable dentro de un bucle. de este modo:

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

Answer 2

La respuesta es "indefinido". El lenguaje Python no define la implementación subyacente. Aquí hay algunos enlaces a una lista de correo hilo que puede estar interesado en

• It is true that Python's lists have been implemented as contiguous vectors in the C implementations of Python so far.

• I'm not saying that the O() behaviours of these things should be kept a secret or anything. But you need to interpret them in the context of how Python works generally.

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

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

Answer 3

no puede hacer comentarios todavía, así

si necesita valor índice y luego usar enumerar:

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

Answer 4

Las listas son de hecho O (1) al índice - se implementan como un vector con sobreasignación proporcional, por lo que funcionan mucho como era de esperar. La razón probable es que encontraras este código más lento de lo esperado es el llamado 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 de elementos, creará una nueva lista de millones de elementos 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 5

Python enumera en realidad nada más que matrices.Por lo tanto,

indexación toma O (1)

de pop y anexar de nuevo debe ser O (1) de acuerdo con los documentos

Salida siguiente enlace para más detalles:

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