Rendimento della lista (...). Insert (...)

Question

Ho pensato alla seguente domanda sull'architettura del computer. Supponiamo che io faccio in Python

from bisect import bisect 
index = bisect(x, a)  # O(log n) (also, shouldn't it be a standard list function?) 
x.insert(index, a)  # O(1) + memcpy() 

che prende log n, più, se ho ben capito, un'operazione di copia della memoria per x[index:]. Recentemente ho letto che il collo di bottiglia si trova di solito nella comunicazione tra il processore e la memoria, quindi la copia della memoria potrebbe essere eseguita dalla RAM abbastanza velocemente con la. È così che funziona?

Answer 1

Python è una lingua. Multiple implementations exist e possono avere diverse implementazioni per gli elenchi. Quindi, senza guardare il codice di un'implementazione reale, non si può sapere con certezza come vengono implementati gli elenchi e come si comportano in determinate circostanze.

La mia scommessa sarebbe che i riferimenti agli oggetti in una lista sono memorizzati in una memoria contigua (certamente non come una lista collegata ...). Se ciò è vero, l'inserimento utilizzando x.insert causerà lo spostamento di tutti gli elementi dietro l'elemento inserito. Questo può essere fatto in modo efficiente dall'hardware, ma la complessità sarebbe comunque O (n).

Per le piccole liste l'operazione bisect può richiedere più tempo di quanto x.insert, anche se il primo è O (log n) mentre il secondo è O (n). Per lunghi elenchi, tuttavia, azzarderei l'ipotesi che il collo di bottiglia sia lo x.insert. In questi casi è necessario considerare l'utilizzo di una diversa struttura dei dati.

Answer 2

Gli elenchi CPython sono array contigui. Quale uno degli inserti O (log n) bisect e O (n) domina il profilo delle prestazioni dipende dalla dimensione dell'elenco e anche i fattori costanti all'interno di O(). In particolare, la funzione di confronto invocata dal bisect può essere qualcosa di costoso a seconda del tipo di oggetti nell'elenco.

Se è necessario mantenere sequenze ordinate mutabili di grandi dimensioni, l'array lineare sottostante al tipo di elenco Python non è una buona scelta. A seconda dei requisiti, gli heap, gli alberi o gli skip-list potrebbero essere appropriati.

Answer 3

Utilizzare lo blist module se è necessario un elenco con prestazioni di inserimento migliori.