Tôi đang chuyển một số mã C++ sang Python và một trong các cấu trúc dữ liệu là một đa điểm, nhưng tôi không chắc chắn làm thế nào để mô hình hóa điều này bằng Python.Có tương đương Python cho C++ "multiset <int>" không?
Hãy ms là C++ multiset<int>
Làm thế nào ms được sử dụng (đăng một số ví dụ)
multiset<int>::iterator it = ms.find(x)
ms.erase(it)
ms.insert(x)
ms.end()
ms.lower_bound(x)
ms.clear()
Không có. Xem Python's standard library - is there a module for balanced binary tree? để có một cuộc thảo luận chung về các thùng tương đương của các thùng chứa C++ (map, set, multimap, multiset) bằng Python.
Điều gần nhất tôi có thể nghĩ là sử dụng số nguyên ánh xạ từ điển cho số đếm (cũng là số nguyên). Tuy nhiên, điều này không giúp bạn có được chìa khóa theo thứ tự, vì vậy bạn không thể tìm kiếm bằng cách sử dụng lower_bound. Một cách khác là sử dụng danh sách có thứ tự, như đề xuất của những người khác, có thể là một danh sách các bộ (số nguyên)? Nếu bạn chỉ cần tìm kiếm sau khi đã thực hiện tất cả các chèn, bạn có thể sử dụng từ điển làm cấu trúc tạm thời để xây dựng, xây dựng danh sách sau khi bạn đã thực hiện tất cả các chèn, sau đó sử dụng danh sách để tìm kiếm.
Có, mã thực hiện rất nhiều lần chèn đầu tiên, sau đó tìm kiếm/xóa các mục khác nhau sau đó. Cả hai quy trình đều sử dụng rất nhiều cuộc gọi lower_bound. – MrP
@MrP Bạn có biết tại sao có các cuộc gọi 'lower_bound' trong quá trình chèn không? Gọi lại 'lower_bound' trong quá trình xóa, nếu bạn có danh sách' tuples '(số nguyên), bạn có thể xóa các mục bằng cách giảm số lượng và nếu số đếm bằng 0, bạn có thể để mục đó ở đó và dọn sạch đôi khi sau đó. (Việc chèn các số nguyên hoàn toàn mới sẽ là vấn đề lớn hơn!) – TooTone
Bạn có thể giữ một danh sách ra lệnh bằng cách sử dụng chức năng bisect. Ví dụ: find sẽ trở thành
def index(a, x):
'Locate the leftmost value exactly equal to x'
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
raise ValueError
Bạn sẽ tìm thấy các tài liệu tương đương khác trong tài liệu. Thay vì kiểm tra chống lại end, bạn sẽ nhận được một ValueError
Hoặc sử dụng một heapq, có thể. – Marcin
Có một vài triển khai về các loại dữ liệu danh sách được sắp xếp phù hợp với tiêu chí của bạn. Hai lựa chọn phổ biến là SortedContainers và blist mô-đun. Mỗi mô-đun này cung cấp loại dữ liệu SortedList tự động duy trì các yếu tố theo thứ tự được sắp xếp và cho phép chèn nhanh và tìm kiếm giới hạn dưới/trên. Có một số performance comparison cũng hữu ích.
Mã tương đương sử dụng loại SortedList từ các module SortedContainers sẽ là:
from sortedcontainers import SortedList
sl = SortedList()
# Start index of `x` values
start = sl.bisect_left(x)
# End index of `x` values
end = sl.bisect_right(x)
# Iterator for those values
iter(sl[start:end])
# Erase an element
del sl[start:end]
# Insert an element
sl.add(x)
# Iterate from lower bound
start = sl.bisect_left(x)
iter(sl[x] for x in range(start, len(sl)))
# Clear elements
sl.clear()
Tất cả những hoạt động nên làm việc một cách hiệu quả trên một loại danh sách dữ liệu được sắp xếp.
Có một vài cấu trúc dữ liệu đến gần.
bộ sưu tập trăn:
cung cấp bởi khuôn khổ django:
Bạn có thể kiểm tra lớp 'Counter' trong python: http://docs.python.org/2/library/collections.html#collections.Counter – taocp
Có tương đương với các hàm/phương thức mà tôi đã liệt kê không? – MrP
'Số lần truy cập' không tương đương với' std :: multiset'. – juanchopanza