Inserimento e rimozione in/da lista ordinata in Python

Question

Ho una lista ordinata di numeri interi, L e I ho un valore X che desidero inserire nella lista in modo tale che l'ordine di L'sia mantenuto. Allo stesso modo, desidero trovare rapidamente e rimuovere la prima istanza di X.

Domande:

1. Come si usa il modulo bisect a fare la prima parte, se possibile?
2. L.remove (X) sarà il modo più efficiente per eseguire la seconda parte? Python rileva che l'elenco è stato ordinato e utilizza automaticamente un processo di rimozione logaritmica?

tentativi codice di esempio:

i = bisect_left(L, y) 

L.pop(i)     #works 
del L[bisect_left(L, i)] #doesn't work if I use this instead of pop 

Answer 1

1. si utilizza il bisect.insort() function:

   bisect.insort(L, X) 
   

2. L.remove(X) esplorerà l'intero elenco fino a trovare X. Utilizzare invece del L[bisect.bisect_left(L, X)] (a condizione che X sia effettivamente in L).

nota che la rimozione dal centro di una lista è ancora in corso per sostenere un costo come gli elementi di tale posizione in poi tutti devono essere spostati sinistra un passo. Un albero binario potrebbe essere una soluzione migliore se questo sarà un collo di bottiglia delle prestazioni.

Answer 2

È possibile utilizzare lo IndexableSkiplist di Raymond Hettinger. Si esegue 3 operazioni in O(ln n) tempo:

• valore inserto
• valore remove
valore
• ricerca per rango

---

import skiplist 
import random 
random.seed(2013) 

N = 10 
skip = skiplist.IndexableSkiplist(N) 
data = range(N) 
random.shuffle(data) 
for num in data: 
    skip.insert(num) 

print(list(skip)) 
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 

for num in data[:N//2]: 
    skip.remove(num) 

print(list(skip)) 
# [0, 3, 4, 6, 9]