Chèn và xóa vào/từ danh sách được sắp xếp trong Python

Question

Tôi có một danh sách sắp xếp các số nguyên, L và tôi có một giá trị X mà tôi muốn chèn vào danh sách sao cho thứ tự của L được duy trì. Tương tự như vậy, tôi muốn nhanh chóng tìm và loại bỏ các trường hợp đầu tiên của X.

Câu hỏi:

1. Làm thế nào để sử dụng các module bisect để làm phần đầu tiên, nếu có thể?
2. L.remove (X) có phải là cách hiệu quả nhất để thực hiện phần thứ hai không? Liệu Python có phát hiện ra rằng danh sách đã được sắp xếp và tự động sử dụng một quá trình loại bỏ logarit?

Ví dụ mã nỗ lực:

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. Bạn sử dụng bisect.insort() function:

   bisect.insort(L, X) 
   

2. L.remove(X) sẽ quét toàn bộ danh sách cho đến khi nó tìm thấy X. Sử dụng del L[bisect.bisect_left(L, X)] thay thế (miễn là X thực sự là trong L).

Lưu ý rằng việc xóa từ giữa danh sách vẫn phải chịu chi phí vì các phần tử từ vị trí đó trở đi phải chuyển sang trái một bước. Cây nhị phân có thể là giải pháp tốt hơn nếu đó là một nút cổ chai hiệu suất.

Answer 2

Bạn có thể sử dụng Raymond Hettinger IndexableSkiplist. Nó thực hiện 3 hoạt động trong O(ln n) thời gian:

• giá trị chèn
• giá trị remove
giá trị
• tra cứu bằng cấp bậc

---

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]