Hiệu suất của danh sách (...). Chèn (...)

Question

Tôi đã nghĩ về câu hỏi sau đây về kiến ​​trúc của máy tính. Giả sử tôi làm trong Python

from bisect import bisect 
index = bisect(x, a)  # O(log n) (also, shouldn't it be a standard list function?) 
x.insert(index, a)  # O(1) + memcpy() 

mà mất log n, cộng thêm, nếu tôi một cách chính xác hiểu nó, một hoạt động bộ nhớ bản sao cho x[index:]. Bây giờ tôi đọc gần đây rằng nút cổ chai thường là trong giao tiếp giữa bộ xử lý và bộ nhớ để bản sao bộ nhớ có thể được thực hiện bằng RAM khá nhanh. Nó hoạt động như thế nào?

Answer 1

Python là ngôn ngữ. Multiple implementations exist và họ có thể có các triển khai khác nhau cho danh sách. Vì vậy, mà không cần nhìn vào mã của một triển khai thực tế, bạn không thể biết chắc chắn các danh sách được triển khai như thế nào và chúng hoạt động như thế nào trong một số trường hợp nhất định.

Đặt cược của tôi sẽ là tham chiếu đến các đối tượng trong danh sách được lưu trữ trong bộ nhớ liền kề (chắc chắn không phải là danh sách được liên kết ...). Nếu điều đó thực sự là như vậy, thì việc chèn bằng cách sử dụng x.insert sẽ khiến tất cả các phần tử phía sau phần tử được chèn sẽ được di chuyển. Điều này có thể được thực hiện hiệu quả bởi phần cứng, nhưng độ phức tạp vẫn là O (n).

Đối với danh sách nhỏ các hoạt động bisect thể mất thời gian hơn x.insert, mặc dù trước đây là O (log n) trong khi sau này là O (n). Tuy nhiên, đối với các danh sách dài, tôi sẽ nguy hiểm khi đoán rằng x.insert là nút cổ chai. Trong những trường hợp như vậy, bạn phải xem xét sử dụng một cấu trúc dữ liệu khác.

Answer 2

Danh sách CPython là các mảng liền nhau. Mà một trong những O (log n) bisect và O (n) chèn chi phối hồ sơ hiệu suất của bạn phụ thuộc vào kích thước của danh sách của bạn và cũng là yếu tố không đổi bên trong O(). Đặc biệt, hàm so sánh được gọi bởi bisect có thể là một cái gì đó đắt tiền tùy thuộc vào loại đối tượng trong danh sách.

Nếu bạn cần giữ các chuỗi sắp xếp có thể thay đổi lớn có thể xảy ra thì mảng tuyến tính nằm dưới loại danh sách Pythons không phải là lựa chọn tốt. Tùy thuộc vào yêu cầu của bạn đống, cây hoặc bỏ qua danh sách có thể là thích hợp.

Answer 3

Sử dụng blist module nếu bạn cần danh sách có hiệu suất chèn tốt hơn.