Pertanyaan Python "disetel" dengan elemen duplikat / berulang


Apakah ada cara standar untuk mewakili "set" yang dapat berisi elemen duplikat.

Seperti yang saya pahami, satu set memiliki tepat satu atau nol elemen. Saya ingin fungsi memiliki nomor.

Saat ini saya menggunakan kamus dengan elemen sebagai kunci, dan kuantitas sebagai nilai, tetapi ini kelihatannya salah karena banyak alasan.

Motivasi: Saya yakin ada banyak aplikasi untuk koleksi semacam itu. Misalnya, survei warna favorit dapat diwakili oleh:     survei = ['biru', 'merah', 'biru', 'hijau']

Di sini, saya tidak peduli dengan pesanannya, tapi saya lakukan tentang kuantitas. Saya ingin melakukan hal-hal seperti:

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

... dan mungkin bahkan

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

Catatan: Ya, set bukanlah istilah yang tepat untuk koleksi semacam ini. Apakah ada yang lebih benar?

Daftar tentu saja bisa berfungsi, tetapi koleksi yang dibutuhkan tidak diurutkan. Belum lagi bahwa metode penamaan set tampaknya bagi saya lebih tepat.


32
2018-04-16 14:28


asal


Jawaban:


Anda mencari a multiset.

Python datatype terdekat adalah collections.Counter:

SEBUAH Counter adalah dict subkelas untuk menghitung objek yang dapat didaur ulang. Ini adalah sebuah   koleksi tak beraturan di mana elemen disimpan sebagai kunci kamus dan   jumlah mereka disimpan sebagai nilai kamus. Hitungan diizinkan   nilai integer apa pun termasuk nol atau jumlah negatif. Itu Counter kelas   mirip dengan tas atau multiset dalam bahasa lain.

Untuk implementasi aktual multiset, gunakan bag kelas dari paket data-struktur pada pypi. Perhatikan bahwa ini hanya untuk Python 3. Jika Anda membutuhkan Python 2, sini adalah resep untuk bag ditulis untuk Python 2.4.


32
2018-04-16 14:43



Pendekatan Anda dengan dict dengan elemen / hitungan tampaknya baik bagi saya. Anda mungkin membutuhkan lebih banyak fungsi. Silahkan lihat collections.Counter.

  • O (1) menguji apakah suatu elemen ada dan pengambilan hitungan saat ini (lebih cepat daripada dengan element in list dan list.count(element))
  • counter.elements() tampak seperti daftar dengan semua duplikat
  • serikat manipulasi mudah / perbedaan dengan Penghitung lainnya

12
2018-04-16 14:34



Anda bisa menggunakan polos list dan digunakan list.count(element) kapan pun Anda ingin mengakses "angka" elemen.

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

my_list.count(1) # will return 2

0
2018-04-16 14:36



Implementasi multiset Python alternatif menggunakan struktur data daftar yang diurutkan. Ada beberapa implementasi pada PyPI. Salah satu opsi adalah sortcontainers modul yang mengimplementasikan a SortedList tipe data yang efisien mengimplementasikan metode set-suka seperti add, remove, dan contains. Modul contactcontainers diimplementasikan dalam Python murni, implementasi cepat-as-C (bahkan lebih cepat), memiliki cakupan uji unit 100%, dan jam pengujian tegangan.

Instalasi mudah dari PyPI:

pip install sortedcontainers

Jika kamu tidak bisa pip install maka cukup tarik file yang diurutkan list.py dari bawah open-source repository.

Gunakan itu seperti yang Anda mau:

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

Modul contactcontainers juga memelihara a perbandingan kinerja dengan implementasi populer lainnya.


0
2017-09-23 06:59



Apa yang Anda cari memang sebuah multiset (atau tas), kumpulan elemen yang tidak harus berbeda (sedangkan a set tidak mengandung duplikat).

Ada implementasi untuk multiset di sini: https://github.com/mlenzen/collections-extended (Pypy's koleksi diperpanjang modul).

Struktur data untuk multisets dipanggil bag. SEBUAH bag adalah subkelas dari Set kelas dari collections modul dengan kamus ekstra untuk melacak banyaknya elemen.

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)

Metode yang bagus untuk bag aku s nlargest (mirip dengan Counter untuk daftar), yang mengembalikan multiplisitas semua elemen yang sangat cepat karena jumlah kemunculan setiap elemen tetap diperbarui dalam kamus tas:

>>> 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}) 

0
2017-10-16 12:14



Jika Anda membutuhkan duplikat, gunakan daftar, dan ubah ke satu set saat Anda perlu beroperasi sebagai satu set.


-2
2018-04-16 14:34