python - resueltos - tiempo de ejecucion de un algoritmo en java

¿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 pitón 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)

Había asumido que el acceso al índice de las listas era O(1) , pero me sorprendí al encontrar que para las listas grandes esto fue 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 del tiempo de ejecución de los siguientes

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

Para crédito adicional, empalme o pop arbitrario.

Answer 1

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 que podría interesarle.

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

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

Además, la manera más pitonica de escribir tu ciclo sería esta:

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

Answer 2

Las listas son de hecho O (1) para indexar: se implementan como un vector con sobreasignación proporcional, por lo que se debe realizar de la manera esperada. La razón 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 de elementos, creará una nueva lista de millones de elementos por adelantado. Este comportamiento cambia en python3 (el rango es un iterador), donde el equivalente de xrange es xrange , o incluso mejor para su caso, enumerate

Answer 3

No puedo comentar todavía, entonces

si necesita índice y valor, utilice enumerate:

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

Answer 4

Python enumera en realidad nada más que arreglos. Así,

la indexación toma O (1)

para pop y anexar de nuevo, debería ser O (1) según los documentos

Vea el siguiente enlace para más detalles:

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

Answer 5

hay una tabla muy detallada en python wiki 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)