Python "establecer" con elementos duplicados/repetidos

Question

¿Existe una forma estándar de representar un "conjunto" que puede contener elementos duplicados.

Según tengo entendido, un conjunto tiene exactamente uno o cero elementos. Quiero que la funcionalidad tenga cualquier número.

Actualmente estoy usando un diccionario con elementos como claves, y cantidad como valores, pero esto parece incorrecto por muchas razones.

Motivo: Creo que hay muchas aplicaciones para tal colección. Por ejemplo, una encuesta de colores favoritos podría representarse por: encuesta = ['azul', 'rojo', 'azul', 'verde']

Aquí, no me importa el orden, pero lo hago sobre cantidades. Quiero hacer cosas como:

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

... y tal vez incluso

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

Notas: Sí, establece que no es el término correcto para este tipo de colección. ¿Hay uno más correcto?

Una lista de curso funcionaría, pero la colección requerida no está ordenada. Sin mencionar que el método de nombrar conjuntos parece ser más apropiado.

Answer 1

Está buscando multiset.

tipo de datos más cercano de Python es collections.Counter:

Un Counter es una subclase dict para contar objetos hashable. Es una colección no ordenada donde los elementos se almacenan como claves de diccionario y sus recuentos se almacenan como valores de diccionario. Los recuentos pueden ser cualquier valor entero que incluya recuentos cero o negativos. La clase Counter es similar a las bolsas o multiestratos en otros idiomas.

Para una implementación real de un conjunto múltiple, utilice la clase bag del paquete de estructuras de datos en PyPI. Tenga en cuenta que esto es solo para Python 3. Si necesita Python 2, here es una receta para bag escrita para Python 2.4.

Answer 2

Su enfoque con dict con elemento/recuento me parece bien. Probablemente necesites más funcionalidades. Eche un vistazo al collections.Counter.

• O (1) prueba si un elemento es la recuperación presente y recuento actual (más rápido que con element in list y list.count(element))
• counter.elements() se ve como una lista con todos los duplicados
• unión fácil manipulación/diferencia con otros contadores

Answer 3

Si necesita duplicados, use una lista y transfórmelos a un conjunto cuando necesite operar como un conjunto.

Answer 4

Puede usar un list simple y usar list.count(element) siempre que quiera acceder al "número" de elementos.

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

my_list.count(1) # will return 2 

Answer 5

Una implementación de Python multiset alternativa utiliza una estructura de datos de lista ordenada. Hay un par de implementaciones en PyPI. Una opción es el módulo sortedcontainers que implementa un tipo de datos SortedList que implementa eficazmente métodos similares a los conjuntos como add, remove y contains. El módulo de contenedores ordenados se implementa en Python puro, implementaciones rápidas como C (incluso más rápido), tiene una cobertura de prueba unitaria del 100% y horas de pruebas de estrés.

La instalación es fácil de PyPI:

pip install sortedcontainers 

Si no pip install continuación, puede simplemente tirar del archivo sortedlist.py hacia abajo desde la open-source repository.

Úselo como lo haría un conjunto:

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

El módulo sortedcontainers también mantiene una performance comparison con otras implementaciones populares.

Answer 6

Lo que estamos buscando es de hecho un multiset (o bolsa de ), una colección de elementos no necesariamente distintos (mientras que un conjunto no contiene duplicados).

Hay una implementación para multisedes aquí: https://github.com/mlenzen/collections-extended (módulo collections extended de Pypy).

La estructura de datos para multisedes se llama bag. A bag es una subclase de la clase Set del módulo collections con un diccionario extra para realizar un seguimiento de las multiplicidades de elementos.

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 buen método para bag es nlargest (similar a Counter para las listas), que devuelve las multiplicidades de todos los elementos extraordinariamente rápido ya que el número de ocurrencias de cada elemento se mantiene hasta a la fecha en el Diccionario de la bolsa :

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