Qual è la complessità di runtime delle funzioni di elenco Python?

Question

Stavo scrivendo una funzione Python che sembrava qualcosa di simile

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

in modo che è stato chiamato con

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

ho dato per scontato che l'accesso indice delle liste era O(1), ma è stato sorpreso di scoprire che per le liste di grandi dimensioni questo è stato significativamente più lento di quanto mi aspettassi.

La mia domanda, allora, è come sono liste di Python sono implementati, e qual è la complessità di esecuzione dei seguenti

• indicizzazione: list[x]
• Popping dalla fine: list.pop()
• Popping dal inizio: list.pop(0)
• Estendere la lista: list.append(x)

Per crediti extra, splicing o pop arbitrari.

Answer 1

c'è a very detailed table on python wiki che risponde alla tua domanda.

Tuttavia, nell'esempio in particolare, è necessario utilizzare enumerate per ottenere un indice di un iterabile all'interno di un ciclo. in questo modo:

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

Answer 2

La risposta è "indefinita". Il linguaggio Python non definisce l'implementazione sottostante. Qui ci sono alcuni link a una mailing list Thread potreste essere interessati a

• 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.

Inoltre, il modo più Pythonic di scrivere il ciclo sarebbe questo.:

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

Answer 3

Non posso ancora commentare, quindi

se avete bisogno di indice e il valore quindi utilizzare enumerare:

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

Answer 4

liste sono infatti O (1) all'indice - sono implementate come un vettore con sovrassegnazione proporzionale, in modo da eseguire quanto ci si aspetterebbe. La probabile ragione per cui hai trovato questo codice più lento del previsto è la chiamata a "range(0, len(some_list))".

range() crea un nuovo elenco delle dimensioni specificate, quindi se some_list ha 1.000.000 articoli, verrà creato un nuovo elenco di milioni di elementi in primo piano. Questo comportamento cambia in python3 (l'intervallo è un iteratore), a cui l'equivalente python2 è xrange, o meglio ancora per il tuo caso, enumerate

Answer 5

Python elenca in realtà nient'altro che gli array.Così,

indicizzazione prende O (1)

per il pop e di aggiunta di nuovo dovrebbe essere O (1) secondo la documentazione

Partenza seguente link per i dettagli:

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