Qual é a complexidade de tempo de execução de funções de lista de python?

Question

Eu estava escrevendo uma função de python que parecia algo como isto

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

para que ele foi chamado com

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

Eu tinha assumido que o acesso índice de listas era O(1), mas foi surpreendido ao descobrir que para grandes listas esta foi significativamente mais lento do que eu esperava.

A minha pergunta, então, é como são listas Python são implementados, e que é a complexidade de tempo de execução dos seguintes

• Indexação: list[x]
• Popping a partir do final: list.pop()
• Popping desde o início: list.pop(0)
• Estendendo a lista: list.append(x)

Para o crédito extra, splicing ou pops arbitrárias.

Answer 1

uma tabela muito detalhada em python wiki que responde a sua pergunta.

No entanto, no seu exemplo particular, você deve usar enumerate para obter um índice de um iterable dentro de um loop. como assim:

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

Answer 2

A resposta é "indefinido". A linguagem Python não define a implementação subjacente. Aqui estão alguns links para uma linha lista de discussão que você pode estar interessado em.

• É verdade que as listas do Python têm foi implementado como contígua vectores nas implementações C de Python até agora.

• eu não estou dizendo que o O ( ) comportamentos dessas coisas devem ser mantido em segredo nem nada. Mas você preciso interpretá-los no contexto de como Python funciona em geral.

Além disso, a maneira mais Pythonic de escrever seu loop seria esta:

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

Answer 3

As listas são de fato O (1) para o índice - eles são implementados como um vetor com overallocation proporcional, então realizar muito como seria de esperar. A razão provável é que você estavam encontrando este código mais lento do que o esperado é a chamada para "range(0, len(some_list))".

range() cria uma nova lista do tamanho especificado, por isso, se some_list tem 1.000.000 itens, você vai criar uma nova lista milhões item para cima frente. Essas mudanças de comportamento em python3 (intervalo é uma iteração), para que o equivalente python2 é xrange , ou ainda melhor para o seu caso, enumerate

Answer 4

Não posso comentar ainda, então

Se você precisa de índice e valor, em seguida, uso enumerar:

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

Answer 5

lista Python realmente nada além de matrizes. Assim,

indexação leva O (1)

para pop e acrescentar mais uma vez, deve ser O (1) de acordo com os docs

Confira seguinte link para mais detalhes:

http://dustycodes.wordpress.com / 2012/03/31 / jibóias-data-estruturas de complexidade-análise /