Tùy thuộc vào sự thành công của nó với tư cách là mô-đun của bên thứ ba, nó vẫn có cơ hội được đưa vào mô-đun bộ sưu tập. Tiêu chí thiết yếu cho điều đó là liệu đó có phải là lựa chọn ưu việt cho một số trường hợp sử dụng trong thế giới thực hay không. Tôi đã quét mã của riêng mình và không tìm thấy trường hợp nào trong đó BList sẽ thích hợp hơn danh sách thông thường. Tuy nhiên, bản quét đó có sai lệch lựa chọn vì nó không phản ánh những gì tôi đã viết nếu có BList. Vì vậy, sau một vài tháng, tôi dự định thăm dò ý kiến. lang thang. python cho những câu chuyện thành công của BList. Nếu chúng tồn tại, thì tôi không gặp vấn đề gì khi đưa vào mô-đun bộ sưu tập. Xét cho cùng, đường cong học tập của nó gần như bằng không – chi phí duy nhất là yếu tố lộn xộn xuất phát từ sự do dự về cấu trúc dữ liệu phù hợp nhất cho một nhiệm vụ nhất định Show
trừu tượngTrường hợp phổ biến cho các hoạt động danh sách là trên danh sách nhỏ. Việc triển khai danh sách dựa trên mảng hiện tại vượt trội ở các danh sách nhỏ do vị trí tham chiếu mạnh và tần suất của các hoạt động cấp phát bộ nhớ. Tuy nhiên, một mảng mất O(n) thời gian để chèn và xóa các phần tử, điều này có thể trở thành vấn đề khi danh sách trở nên lớn PEP này giới thiệu một kiểu dữ liệu mới, BList, có dạng mảng và dạng cây. Nó có cùng hiệu suất tốt trên các danh sách nhỏ như triển khai dựa trên mảng hiện có, nhưng cung cấp hiệu suất tiệm cận vượt trội cho hầu hết các hoạt động. PEP này đề xuất thay thế hai đề xuất loại trừ lẫn nhau để bao gồm loại BList trong Python
Động lựcBList phát triển do sự thất vọng khi cần viết lại các thuật toán trực quan hoạt động tốt cho các đầu vào nhỏ nhưng mất thời gian O(n**2) cho các đầu vào lớn do hành vi O(n) cơ bản của danh sách dựa trên mảng. Loại deque, được giới thiệu trong Python 2. 4, đã giải quyết vấn đề phổ biến nhất là cần hàng đợi FIFO nhanh. Tuy nhiên, loại deque không hữu ích nếu chúng ta cần liên tục chèn hoặc xóa các phần tử từ giữa một danh sách dài Một loạt các cấu trúc dữ liệu cung cấp hiệu suất tiệm cận tốt cho việc chèn và xóa, nhưng chúng có hiệu suất O(n) cho các hoạt động khác (e. g. , danh sách được liên kết) hoặc có hiệu suất kém hơn đối với danh sách nhỏ (e. g. , cây nhị phân và danh sách bỏ qua) Loại BList được đề xuất trong PEP này dựa trên các nguyên tắc của B+Trees, có các khía cạnh giống như mảng và giống như cây. BList cung cấp hiệu suất giống như mảng trên các danh sách nhỏ, đồng thời cung cấp hiệu suất tiệm cận O(log n) cho tất cả các thao tác chèn và xóa. Ngoài ra, BList thực hiện sao chép khi ghi dưới mui xe, do đó, ngay cả các hoạt động như getlice cũng mất thời gian O(log n). Bảng bên dưới so sánh hiệu suất tiệm cận của việc triển khai danh sách dựa trên mảng hiện tại với hiệu suất tiệm cận của BList OperationArray-based listBListCopyO(n)O(1)AppendO(1)O(log n)InsertO(n)O(log n)Get ItemO(1)O(log n)Set ItemO(1)O(log n)DelMột so sánh thực nghiệm rộng rãi về danh sách dựa trên mảng của Python và BList có sẵn tại [2] Ca sử dụng Đánh đổiBList cung cấp hiệu suất vượt trội cho nhiều hoạt động, nhưng không phải tất cả. Việc chọn đúng loại dữ liệu cho một trường hợp sử dụng cụ thể tùy thuộc vào thao tác nào được sử dụng. Việc chọn đúng loại dữ liệu dưới dạng tích hợp phụ thuộc vào việc cân bằng tầm quan trọng của các trường hợp sử dụng khác nhau và mức độ khác biệt về hiệu suất Đối với các trường hợp sử dụng phổ biến của danh sách nhỏ, danh sách dựa trên mảng và BList có các đặc điểm hiệu suất tương tự nhau Đối với trường hợp danh sách lớn ít phổ biến hơn một chút, có hai trường hợp sử dụng phổ biến trong đó danh sách dựa trên mảng hiện tại hoạt động tốt hơn triển khai tham chiếu BList hiện tại. đó là
Trong các thử nghiệm hiệu suất trên danh sách 10.000 phần tử, BLLists cho thấy thời gian thực hiện lần lượt tăng 50% và 5% cho hai trường hợp sử dụng này Hiệu suất cho trường hợp sử dụng LIFO có thể được cải thiện thành thời gian O(n), bằng cách lưu vào bộ đệm một con trỏ tới lá ngoài cùng bên phải trong nút gốc. Đối với các danh sách không thay đổi kích thước, trường hợp phổ biến của truy cập tuần tự cũng có thể được cải thiện thành thời gian O(n) thông qua bộ nhớ đệm trong nút gốc. Tuy nhiên, hiệu suất của các phương pháp này chưa được thử nghiệm thực nghiệm Nhiều hoạt động thể hiện tốc độ tăng nhanh (O(n) lên O(log n)) khi chuyển từ danh sách dựa trên mảng sang BLList. Trong các bài kiểm tra hiệu suất trên danh sách 10.000 phần tử, các thao tác như getlice, setlice và chèn và xóa kiểu FIFO trên BList chỉ chiếm 1% thời gian cần thiết trên danh sách dựa trên mảng Do tăng tốc hiệu suất lớn cho nhiều hoạt động, chi phí hiệu suất nhỏ cho một số hoạt động sẽ đáng giá đối với nhiều ứng dụng (nhưng không phải tất cả) Thực hiệnBList dựa trên cấu trúc dữ liệu B+Tree. BList là một cây rộng, rậm rạp, trong đó mỗi nút chứa một mảng lên tới 128 con trỏ tới nút con của nó. Nếu nút là một chiếc lá, thì các nút con của nó là các đối tượng mà người dùng có thể nhìn thấy mà người dùng đã đặt trong danh sách. Nếu nút không phải là lá, con của nó là các nút BList khác mà người dùng không nhìn thấy được. Nếu danh sách chỉ chứa một vài phần tử, tất cả chúng sẽ là con của một nút vừa là gốc vừa là lá. Vì một nút ít hơn một mảng các con trỏ, nên các danh sách nhỏ hoạt động hiệu quả giống như một kiểu dữ liệu dựa trên mảng và chia sẻ các đặc điểm hiệu suất tốt giống nhau BList duy trì một vài bất biến để đảm bảo hiệu suất tiệm cận (O(log n)) tốt bất kể trình tự thao tác chèn và xóa. Các bất biến nguyên tắc như sau
Nếu một lần chèn sẽ khiến một nút vượt quá 128 nút con, thì nút đó sẽ sinh ra một anh chị em và chuyển một nửa số con của nó cho anh chị em đó. Anh chị em được chèn vào cha mẹ của nút. Nếu nút là nút gốc (và do đó không có nút cha), nút cha mới được tạo và độ sâu của cây tăng thêm một Nếu việc xóa sẽ khiến một nút có ít hơn 64 nút con, thì nút đó sẽ di chuyển các phần tử từ một trong các nút anh chị em của nó nếu có thể. Nếu cả hai anh chị em của nó cũng chỉ có 64 nút con, thì hai trong số các nút hợp nhất và nút trống sẽ bị xóa khỏi nút cha của nó. Nếu nút gốc bị giảm xuống chỉ còn một nút con, nút con duy nhất của nó sẽ trở thành nút gốc mới (i. e. , độ sâu của cây giảm đi một) Ngoài hiệu suất tiệm cận giống như cây và hiệu suất giống như mảng trên danh sách nhỏ, BLList hỗ trợ sao chép trong suốt khi ghi. Nếu một nút không phải gốc cần được sao chép (như một phần của getlice, copy, setlice, v.v. ), nút được chia sẻ giữa nhiều cha mẹ thay vì được sao chép. Nếu sau này cần sửa thì copy lúc đó. Điều này hoàn toàn ở hậu trường; Sử dụng bộ nhớTrong trường hợp xấu nhất, các nút lá của BList chỉ có 64 nút con, thay vì 128 nút đầy đủ, nghĩa là mức sử dụng bộ nhớ gấp khoảng hai lần so với triển khai mảng trong trường hợp tốt nhất. Các nút không phải lá sử dụng một lượng bộ nhớ bổ sung không đáng kể, vì có ít nhất 63 lần số nút lá so với các nút không phải lá Việc triển khai danh sách dựa trên mảng hiện tại phải phát triển và thu nhỏ khi các mục được thêm và xóa. Để hiệu quả, nó chỉ tăng và giảm khi danh sách tăng hoặc giảm theo cấp số nhân. Trong trường hợp xấu nhất, nó cũng sử dụng bộ nhớ gấp đôi so với trường hợp tốt nhất Tóm lại, dung lượng bộ nhớ của BList không khác biệt đáng kể so với triển khai dựa trên mảng hiện có Khả năng tương thích ngượcNếu BList được thêm vào mô-đun bộ sưu tập, khả năng tương thích ngược không phải là vấn đề. Phần này tập trung vào tùy chọn thay thế danh sách dựa trên mảng hiện có bằng BList. Đối với người dùng trình thông dịch Python, BList có giao diện giống với cách triển khai danh sách hiện tại. Đối với hầu như tất cả các hoạt động, hành vi giống hệt nhau, ngoại trừ tốc độ thực thi Đối với API C, BList có giao diện khác với cách triển khai danh sách hiện có. Do cấu trúc phức tạp hơn của nó, BList không thích hợp để chọc và chọc bởi các nguồn bên ngoài. Rất may, việc triển khai danh sách hiện có xác định API gồm các hàm và macro để truy cập dữ liệu từ các đối tượng danh sách. Google Code Search gợi ý rằng phần lớn các mô-đun của bên thứ ba sử dụng API được xác định rõ thay vì dựa trực tiếp vào cấu trúc của danh sách. Bảng dưới đây tóm tắt các truy vấn và kết quả tìm kiếm Chuỗi tìm kiếmSố kết quảPyList_GetItem2,000PySequence_GetItem800PySequence_Fast_GET_ITEM100PyList_GET_ITEM400[^a-zA-Z_]ob_item100Điều này có thể đạt được theo một trong hai cách
Thực hiện tham khảoViệc triển khai tham chiếu của BList có sẵn cho CPython tại [1] Gói nguồn cũng bao gồm một triển khai Python thuần túy, ban đầu được phát triển làm nguyên mẫu cho phiên bản CPython. Đương nhiên, phiên bản Python thuần túy khá chậm và các cải tiến tiệm cận không thành công cho đến khi danh sách khá lớn Khi được biên dịch với Py_DEBUG, việc triển khai C sẽ kiểm tra các bất biến BList khi nhập và thoát hầu hết các chức năng Một tập hợp các trường hợp thử nghiệm phong phú cũng được bao gồm trong gói nguồn. Các trường hợp thử nghiệm bao gồm trình tự Python hiện có và liệt kê các trường hợp thử nghiệm dưới dạng tập hợp con. Khi trình thông dịch được tạo bằng Py_DEBUG, các trường hợp thử nghiệm cũng kiểm tra rò rỉ tham chiếu Chuyển sang các biến thể Python khácNếu BList được thêm vào mô-đun bộ sưu tập, các biến thể Python khác có thể hỗ trợ nó theo một trong ba cách
Thảo luậnĐề xuất này đã được thảo luận ngắn gọn trên danh sách gửi thư Python-3000 [3]. Mặc dù một số người ủng hộ đề xuất này, nhưng cũng có một số phản đối. Dưới đây tóm tắt những ưu và nhược điểm theo quan sát của người đăng đối với chủ đề Nhận xét chung
Nhận xét về việc thêm BList vào mô-đun bộ sưu tập
Nhận xét về việc thay thế danh sách dựa trên mảng bằng BList
Để đánh giá mức độ mong muốn và hiệu suất trong các ứng dụng thực tế, Raymond Hettinger đã đề xuất phát hành BList dưới dạng mô-đun mở rộng (hiện đã có tại [1]). Nếu nó tỏ ra hữu ích, anh ấy cảm thấy nó sẽ là một ứng cử viên sáng giá để đưa vào 2. 6 như một phần của mô-đun bộ sưu tập. Nếu phổ biến rộng rãi, thì nó có thể được xem xét để thay thế danh sách dựa trên mảng, nhưng ngược lại thì không Guido van Rossum nhận xét rằng ông phản đối sự phổ biến của các loại dữ liệu, nhưng ủng hộ việc thay thế danh sách dựa trên mảng nếu khả năng tương thích ngược có thể được giải quyết và hiệu suất của BList tốt hơn một cách đồng đều Bộ sưu tập nào nhanh hơn trong Python?Mảng NumPy nhanh hơn Danh sách Python vì những lý do sau. Mảng là một tập hợp các kiểu dữ liệu đồng nhất được lưu trữ trong các vị trí bộ nhớ liền kề.
Danh sách hoặc bộ dữ liệu nào nhanh hơn trong Python?Tạo bộ nhanh hơn tạo danh sách . Tạo danh sách chậm hơn vì cần truy cập hai khối bộ nhớ. Một phần tử trong bộ không thể bị xóa hoặc thay thế. Một phần tử trong danh sách có thể được loại bỏ hoặc thay thế.
Danh sách hoặc mảng nào nhanh hơn trong Python?Mảng nhanh hơn danh sách trong python vì tất cả các phần tử được lưu trữ trong một mảng đều đồng nhất i. e. , chúng có cùng kiểu dữ liệu trong khi danh sách chứa các phần tử không đồng nhất. Hơn nữa, các mảng Python được triển khai trong C, điều này làm cho nó nhanh hơn rất nhiều so với các danh sách được tích hợp sẵn trong chính Python.
Cái gì nhanh hơn NumPy?pandas cung cấp một loạt các hàm được tối ưu hóa cho C hoặc Cython có thể nhanh hơn hàm tương đương NumPy (e. g. đọc văn bản từ tệp văn bản). |
