Liệu python có một danh sách được sắp xếp?

Question

Bằng mà tôi có nghĩa là một cấu trúc với:

• O (log n) tính phức tạp cho x.push() hoạt động
• O (log n) phức tạp để tìm một yếu tố
• O (n) tính phức tạp để tính list(x) mà sẽ được sắp xếp

Tôi cũng có câu hỏi liên quan về hiệu suất của list(...).insert(...) hiện là here.

Answer 1

Danh sách Python tiêu chuẩn không được sắp xếp dưới bất kỳ hình thức nào. Mô đun heapq tiêu chuẩn có thể được sử dụng để nối thêm vào O (log n) và loại bỏ nhỏ nhất trong O (log n), nhưng không phải là một danh sách được sắp xếp theo định nghĩa của bạn.

Có nhiều triển khai khác nhau về cây cân bằng cho Python đáp ứng các yêu cầu của bạn, ví dụ: rbtree, RBTree hoặc pyavl.

Answer 2

Mặc dù chưa cung cấp chức năng tìm kiếm tùy chỉnh, mô-đun heapq có thể phù hợp với nhu cầu của bạn. Nó thực hiện một hàng đợi heap bằng cách sử dụng một danh sách thường xuyên. Bạn sẽ phải viết thử nghiệm thành viên hiệu quả của riêng bạn mà làm cho việc sử dụng cấu trúc bên trong của hàng đợi (có thể được thực hiện trong O (log n), tôi muốn nói ...). Có một nhược điểm: trích xuất một danh sách được sắp xếp có độ phức tạp O (n log n).

Answer 3

Mặc dù tôi đã vẫn không bao giờ kiểm tra "O lớn" tốc độ hoạt động danh sách Python cơ bản, các bisect mô-đun chuẩn có lẽ cũng đáng nhắc đến trong bối cảnh này:

import bisect 
L = [0, 100] 

bisect.insort(L, 50) 
bisect.insort(L, 20) 
bisect.insort(L, 21) 

print L 
## [0, 20, 21, 50, 100] 

i = bisect.bisect(L, 20) 
print L[i-1], L[i] 
## 20, 21 

PS. Ah, xin lỗi, bisect được đề cập trong câu hỏi được tham chiếu. Tuy nhiên, tôi nghĩ nó sẽ không gây hại nhiều nếu thông tin này sẽ có ở đây)

PPS. Và CPython lists are actually arrays (không, nói, skiplists hoặc vv). Vâng, tôi đoán họ phải là một cái gì đó đơn giản, nhưng đối với tôi, tên là một chút sai lầm.

---

Vì vậy, nếu tôi không nhầm, tốc độ bisect/danh sách có lẽ là:

• cho một push(): O (n) đối với trường hợp tồi tệ nhất;
• để tìm kiếm: nếu chúng tôi xem xét tốc độ lập chỉ mục mảng là O (1), tìm kiếm phải là hoạt động O (log (n));
• để tạo ra danh sách: O (n) nên tốc độ của việc sao chép danh sách, nếu không nó là O (1) cho cùng một danh sách)

UPD. Sau khi thảo luận trong các ý kiến, hãy để tôi liên kết ở đây những câu hỏi SO: How is Python's List Implemented và What is the runtime complexity of python list functions

Answer 4

Có thể không khó để triển khai danh sách phân loại của riêng bạn trên Python.Dưới đây là một bằng chứng của khái niệm:

import bisect 

class sortlist: 
    def __init__(self, list): 
     self.list = list 
     self.sort() 
    def sort(self): 
     l = [] 
     for i in range(len(self.list)): 
      bisect.insort(l, self.list[i]) 
     self.list = l 
     self.len = i 
    def insert(self, value): 
     bisect.insort(self.list, value) 
     self.len += 1 
    def show(self): 
     print self.list 
    def search(self,value): 
     left = bisect.bisect_left(self.list, value) 
     if abs(self.list[min([left,self.len-1])] - value) >= abs(self.list[left-1] - value): 
      return self.list[left-1] 
     else: 
      return self.list[left] 

list = [101, 3, 10, 14, 23, 86, 44, 45, 45, 50, 66, 95, 17, 77, 79, 84, 85, 91, 73] 
slist = sortlist(list) 
slist.show() 
slist.insert(99) 
slist.show() 
print slist.search(100000000) 
print slist.search(0) 
print slist.search(56.7) 

========= Kết quả ============

[3, 10, 14, 17, 23 , 44, 45, 45, 50, 66, 73, 77, 79, 84, 85, 86, 91, 95, 101]

[3, 10, 14, 17, 23, 44, 45, 45, 50, 66, 73, 77, 79, 84, 85, 86, 91, 95, 99, 101]

Answer 5

Có lý do cụ thể nào cho yêu cầu Big-O của bạn không? Hay bạn chỉ muốn nó nhanh? Mô-đun sortedcontainers là tinh khiết-Python và nhanh (như trong các triển khai nhanh như C như blist và rbtree).

Các performance comparison cho thấy điểm chuẩn nhanh hơn hoặc ngang bằng với loại danh sách được sắp xếp của blist. Cũng lưu ý rằng rbtree, RBTree và PyAVL cung cấp các loại dict được sắp xếp và các loại thiết lập nhưng không có loại danh sách được sắp xếp.

Nếu hiệu suất là yêu cầu, hãy luôn nhớ điểm chuẩn. Một mô-đun chứng minh yêu cầu được nhanh chóng với ký hiệu Big-O nên nghi ngờ cho đến khi nó cũng cho thấy so sánh điểm chuẩn.

Tuyên bố từ chối trách nhiệm: Tôi là tác giả của mô-đun trình biên tập viên được phân loại Python.

---

Cài đặt:

pip install sortedcontainers 

Cách sử dụng:

>>> from sortedcontainers import SortedList 
>>> l = SortedList() 
>>> l.update([0, 4, 1, 3, 2]) 
>>> l.index(3) 
3 
>>> l.add(5) 
>>> l[-1] 
5 

Answer 6

import bisect 

class sortedlist(list): 
    '''just a list but with an insort (insert into sorted position)''' 
    def insort(self, x): 
     bisect.insort(self, x) 

Answer 7

tôi sẽ sử dụng biscect hoặc sortedcontainers mô-đun. Tôi không thực sự có kinh nghiệm, nhưng tôi nghĩ rằng mô-đun heapq hoạt động. Nó chứa một số Heap Queue