Python "set" với các phần tử trùng lặp/lặp lại

Question

Có cách tiêu chuẩn để đại diện cho "tập hợp" có thể chứa các phần tử trùng lặp hay không.

Như tôi đã hiểu, tập hợp có chính xác một hoặc 0 của một phần tử. Tôi muốn chức năng có bất kỳ số nào.

Tôi hiện đang sử dụng từ điển có các yếu tố làm khóa và số lượng làm giá trị, nhưng điều này có vẻ sai vì nhiều lý do.

Động lực: Tôi tin rằng có rất nhiều ứng dụng cho bộ sưu tập như vậy. Ví dụ: khảo sát màu sắc yêu thích có thể được biểu thị bằng: survey = ['blue', 'red', 'blue', 'green']

Ở đây, tôi không quan tâm đến thứ tự nhưng tôi làm về số lượng. Tôi muốn làm những việc như:

survey.add('blue') 
# would give survey == ['blue', 'red', 'blue', 'green', 'blue'] 

... và thậm chí có thể

survey.remove('blue') 
# would give survey == ['blue', 'red', 'green'] 

Ghi chú: Vâng, thiết lập không phải là thuật ngữ chính xác cho các loại hình bộ sưu tập. Có cái nào đúng hơn không?

Danh sách khóa học sẽ hoạt động nhưng yêu cầu thu thập không có thứ tự. Chưa kể rằng phương pháp đặt tên cho các bộ dường như tôi thích hợp hơn.

Answer 1

Bạn đang tìm kiếm multiset.

datatype gần Python là collections.Counter:

Một Counter là một lớp con dict cho đếm các đồ vật hashable. Đây là bộ sưu tập không có thứ tự trong đó các phần tử được lưu trữ dưới dạng khóa từ điển và số lượng của chúng được lưu trữ dưới dạng giá trị từ điển. Số lượng được phép là bất kỳ giá trị số nguyên nào bao gồm số không hoặc số âm. Counter lớp tương tự như túi hoặc nhiều bộ bằng các ngôn ngữ khác.

Để triển khai thực hiện multiset, hãy sử dụng lớp bag từ gói cấu trúc dữ liệu trên pypi. Lưu ý rằng điều này chỉ dành cho Python 3. Nếu bạn cần Python 2, here là một công thức cho một bag được viết cho Python 2.4.

Answer 2

Cách tiếp cận của bạn với dict với phần tử/số có vẻ ổn với tôi. Có thể bạn cần một số chức năng khác. Hãy xem collections.Counter.

• O (1) kiểm tra xem một yếu tố là hiện tại và hiện tại hồi count (nhanh hơn so với element in list và list.count(element))
• counter.elements() trông giống như một danh sách với tất cả các bản sao
• dễ dàng thao tác công đoàn/khác biệt với bộ đếm khác

Answer 3

Nếu bạn cần bản sao, hãy sử dụng danh sách và chuyển đổi nó thành bộ khi bạn cần thao tác làm bộ.

Answer 4

Bạn có thể sử dụng đồng bằng list và sử dụng list.count(element) bất cứ khi nào bạn muốn truy cập vào "số" phần tử.

my_list = [1, 1, 2, 3, 3, 3] 

my_list.count(1) # will return 2 

Answer 5

Một triển khai thực hiện multiset Python khác sử dụng cấu trúc dữ liệu danh sách được sắp xếp. Có một vài triển khai trên PyPI. Một tùy chọn là mô-đun sortedcontainers triển khai loại dữ liệu SortedList có hiệu quả thực hiện các phương pháp giống như kiểu như add, remove và contains. Mô đun phân vùng được thực hiện trong các triển khai thuần-Python, nhanh như C (thậm chí nhanh hơn), có phạm vi kiểm tra đơn vị 100% và số giờ thử nghiệm ứng suất.

cài đặt rất dễ dàng từ PyPI:

pip install sortedcontainers 

Nếu bạn không thể pip install sau đó chỉ cần kéo tập tin sortedlist.py xuống từ open-source repository.

Sử dụng nó như bạn làm một bộ:

from sortedcontainers import SortedList 
survey = SortedList(['blue', 'red', 'blue', 'green']] 
survey.add('blue') 
print survey.count('blue') # "3" 
survey.remove('blue') 

Module sortedcontainers cũng duy trì một performance comparison với việc triển khai phổ biến khác.

Answer 6

gì bạn đang tìm kiếm thực sự là một multiset (hoặc túi), một bộ sưu tập không nhất thiết các yếu tố khác nhau (trong khi một thiết không chứa bản sao).

Có triển khai cho nhiều trang web tại đây: https://github.com/mlenzen/collections-extended (Pypy's collections extended mô-đun).

Cấu trúc dữ liệu cho multisets được gọi là bag. A bag là một phân lớp của lớp Set từ collections mô-đun với một từ điển bổ sung để theo dõi tính đa dạng của các phần tử.

class _basebag(Set): 
    """ 
    Base class for bag and frozenbag. Is not mutable and not hashable, so there's 
    no reason to use this instead of either bag or frozenbag. 
    """ 
    # Basic object methods 

    def __init__(self, iterable=None): 
     """Create a new basebag. 

     If iterable isn't given, is None or is empty then the bag starts empty. 
     Otherwise each element from iterable will be added to the bag 
     however many times it appears. 

     This runs in O(len(iterable)) 
     """ 
     self._dict = dict() 
     self._size = 0 
     if iterable: 
      if isinstance(iterable, _basebag): 
       for elem, count in iterable._dict.items(): 
        self._inc(elem, count) 
      else: 
       for value in iterable: 
        self._inc(value) 

Một phương pháp tốt đẹp cho bag là nlargest (tương tự như Counter cho danh sách), mà trả về bội của tất cả các yếu tố tốc độ nhanh kể từ khi số lần xuất hiện của mỗi yếu tố được giữ cập nhật lên trong từ điển của túi :

>>> b=bag(random.choice(string.ascii_letters) for x in xrange(10)) 
>>> b.nlargest() 
[('p', 2), ('A', 1), ('d', 1), ('m', 1), ('J', 1), ('M', 1), ('l', 1), ('n', 1), ('W', 1)] 
>>> Counter(b) 
Counter({'p': 2, 'A': 1, 'd': 1, 'm': 1, 'J': 1, 'M': 1, 'l': 1, 'n': 1, 'W': 1})