Python "set" con elementi duplicati/ripetuti

Question

Esiste un modo standard per rappresentare un "set" che può contenere elementi duplicati.

Come ho capito, un set ha esattamente uno o zero di un elemento. Voglio che la funzionalità abbia un numero qualsiasi.

Attualmente sto usando un dizionario con elementi come chiavi e quantità come valori, ma questo sembra sbagliato per molte ragioni.

Motivazione: Credo ci siano molte applicazioni per tale raccolta. Ad esempio, un sondaggio di colori preferiti potrebbe essere rappresentata da: sondaggio = [ 'blu',, 'blu' 'rosso', 'verde']

Ecco, non mi interessa circa l'ordine, ma lo faccio sulle quantità Voglio fare le cose come:

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

... e forse anche

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

Note: Sì, impostato non è il termine corretto per questo tipo di raccolta. C'è uno più corretto?

Un elenco di corso funzionerebbe, ma la raccolta richiesta non è ordinata. Per non parlare del fatto che la denominazione dei metodi per gli insiemi mi sembra più appropriata.

Answer 1

Stai cercando un multiset.

tipo di dati più vicino di Python è collections.Counter:

Un Counter è una sottoclasse dict per contare gli oggetti hashable. È una collezione non ordinata in cui gli elementi sono memorizzati come chiavi del dizionario e i loro conteggi vengono memorizzati come valori del dizionario. I conteggi possono essere qualsiasi valore intero compresi i conteggi zero o negativi. La classe Counter è simile a borse o multiset in altre lingue.

Per una effettiva attuazione di un multiset, utilizzare la classe bag dal pacchetto strutture dati su pypi. Nota che questo è solo per Python 3. Se hai bisogno di Python 2, here è una ricetta per un bag scritto per Python 2.4.

Answer 2

Il tuo approccio con dict con elemento/conteggio sembra ok per me. Probabilmente hai bisogno di più funzionalità. Dai un'occhiata a collections.Counter.

• O (1) verificare se un elemento è presente e attuale il recupero count (più velocemente che con element in list e list.count(element))
• counter.elements() si presenta come un elenco con tutti i duplicati
• facile manipolazione unione/differenza con altri contatori

Answer 3

Se sono necessari duplicati, utilizzare un elenco e trasformarlo in un set quando è necessario operare come un set.

Answer 4

È possibile utilizzare un semplice list e utilizzare list.count(element) ogni volta che si desidera accedere al "numero" di elementi.

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

my_list.count(1) # will return 2 

Answer 5

Un'implementazione multiset Python alternativa utilizza una struttura di dati dell'elenco ordinato. Ci sono un paio di implementazioni su PyPI. Un'opzione è il modulo sortedcontainers che implementa un tipo di dati SortedList che implementa in modo efficiente metodi set-like come add, remove e contains. Il modulo ordinati container è implementato in pure-Python, implementazioni veloci-come-C (ancora più veloce), ha una copertura del 100% di test unitario e ore di stress test.

L'installazione è facile da PyPI:

pip install sortedcontainers 

Se non pip install può poi semplicemente tirare il file sortedlist.py giù dal open-source repository.

Usarlo come si farebbe con un set:

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

Il modulo sortedcontainers mantiene anche un performance comparison con altre implementazioni popolari.

Answer 6

Quello che stai cercando è davvero un multiset (o bag), una raccolta di non necessariamente elementi distinti (mentre un set non contiene i duplicati).

Qui è disponibile un'implementazione per i multiset: https://github.com/mlenzen/collections-extended (modulo collections extended di Pypy).

La struttura dati per multiset è denominata bag. Un bag è una sottoclasse della classe Set dal modulo collections con un dizionario aggiuntivo per tenere traccia delle molteplicità di elementi.

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) 

Un bel metodo per bag è nlargest (simile a Counter per gli elenchi), che restituisce le molteplicità di tutti gli elementi incredibilmente veloce dal momento che il numero di occorrenze di ogni elemento è mantenuto up-to-date nel dizionario del sacchetto :

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