Wstawianie i usuwanie do/z posortowanej listy w Pythonie

Question

Mam posortowaną listę liczb całkowitych, L, a ja mam wartość X, którą chcę wstawić do listy, tak aby kolejność L była zachowywana. Podobnie, życzę, aby szybko znaleźć i usunąć pierwsze wystąpienie X.

Pytania:

1. W jaki sposób korzystać z modułu przepoławiać zrobić pierwszą część, jeśli jest to możliwe?
2. Czy L.remove (X) będzie najskuteczniejszym sposobem na wykonanie drugiej części? Czy Python wykryje, że lista została posortowana i automatycznie korzysta z logarytmicznego procesu usuwania?

przykładowy kod próby:

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. użyć bisect.insort() function:

   bisect.insort(L, X) 
   

2. L.remove(X) skanuje całą listę, dopóki nie znajdzie X. Zamiast tego należy użyć del L[bisect.bisect_left(L, X)] (pod warunkiem, że X rzeczywiście znajduje się w L).

Należy pamiętać, że usunięcie ze środka listy nadal będzie ponosić kosztów jako elementów z tej pozycji począwszy wszyscy muszą być przesunięte w lewo jednym kroku. Drzewo binarne może być lepszym rozwiązaniem, jeśli będzie to wąskie gardło wydajności.

Answer 2

Możesz użyć Raymonda Hettingera: IndexableSkiplist. Wykonuje 3 operacje w O(ln n) czas:

• wartość wkładka
• cena Usuń
wartość
• wyszukiwanie według rangi

---

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]