Qual è il costo/la complessità dell'inserimento nell'elenco in qualche luogo?

Question

In Python, un list ha list.insert(i, x) in "Inserire un elemento in una determinata posizione". In C++, c'è anche list. In C++, il costo/la complessità di inserire un elemento ovunque è O (1). È lo stesso per una lista Python? Se no, può essere usato qualcos'altro per ottenere O (1) inserire il tempo in Python?

Answer 1

Il linguaggio Python non specifica l'attuazione di tali operazioni, così diverse implementazioni possono avere un comportamento diverso. Per CPython, la complessità di list.insert è O (n), come mostrato su this useful wiki page. Non sono a conoscenza di alcuna struttura ad elenco che fornisce prestazioni O (1) per l'inserimento in un indice arbitrario. (Un Dt dà O (1) inserire le prestazioni nel caso medio, ma non è ordinato e non impone una sequenza contigua di indici.) La libreria blist fornisce un tipo di elenco ottimizzato che ha un inserto O (log n).

Answer 2

Python è una lingua. Esistono implementazioni multiple e possono avere implementazioni diverse 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 è così, allora l'inserimento usando x.insert farà sì che tutti gli elementi dietro l'elemento inserito vengano spostati. Questo può essere fatto in modo efficiente dall'hardware, ma la complessità sarebbe comunque O (n).

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

Answer 3

No, non è la stessa complessità. In base alla pagina ufficiale Time Complexity di Python , l'utilizzo di list.insert ha sempre la complessità O(n) (lineare).

Inoltre, un elenco Python non è esattamente lo stesso di un elenco C++. In effetti, una lista Python è più confrontabile con un C++ std::vector se non altro.

---

_{Beh, pagina ufficiale di CPython. Non conosco altre implementazioni come IronPython o Jython.}

Answer 4

lista

caso medio assume parametri generati in modo uniforme a caso.

Internamente, una lista è rappresentata come una matrice; i maggiori costi derivano dalla crescita oltre l'attuale dimensione di allocazione (perché tutto deve muoversi), o dall'inserimento o eliminazione da qualche parte vicino all'inizio (perché tutto dopo deve muoversi). Se è necessario aggiungere/rimuovere da entrambe le estremità, prendere in considerazione l'uso di collections.deque.

Così inserito un elemento alla posizione indicata avrà sempre la complessità temporale di O (n) sia come inserto metodo e affettare ha complessità temporale di O (n) e O (k). Solo append quali inserti alla fine dell'elenco hanno O (1) complessità temporale. Da Python Wiki

Lists: 
           Complexity 
Operation  | Example  | Class   | Notes 
--------------+--------------+---------------+------------------------------- 
Index   | l[i]   | O(1)   | 
Store   | l[i] = 0  | O(1)   | 
Length  | len(l)  | O(1)   | 
Append  | l.append(5) | O(1)   | 
Clear   | l.clear() | O(1)   | similar to l = [] 

Slice   | l[a:b]  | O(b-a)  | l[1:5]:O(l)/l[:]:O(len(l)-0)=O(N) 
Extend  | l.extend(...)| O(len(...)) | depends only on len of extension 
Construction | list(...) | len(...)  | depends on lenghth of argument 

check ==, != | l1 == l2  | O(N)   | 
Insert  | l[a:b] = ... | O(N)   | 
Delete  | del l[i]  | O(N)   | 
Remove  | l.remove(...)| O(N)   | 
Containment | x in/not in l| O(N)   | searches list 
Copy   | l.copy()  | O(N)   | Same as l[:] which is O(N) 
Pop   | l.pop(...) | O(N)   | 
Pop   | l.pop()  | O(1)   | same as l.pop(-1), popping at end 
Extreme value | min(l)/max(l)| O(N)   | 
Reverse  | l.reverse() | O(N)   | 
Iteration  | for v in l: | O(N)   | 

Sort   | l.sort()  | O(N Log N) | key/reverse doesn't change this 
Multiply  | k*l   | O(k N)  | 5*l is O(N): len(l)*l is O(N**2) 

Da here