una - Restando dos listas en Python

recorrer dos listas a la vez python

Question

En Python, ¿cómo se pueden restar dos listas desordenadas no exclusivas? Digamos que tenemos a = [0,1,2,1,0] b = [0, 1, 1] Me gustaría hacer algo como c = a - b y tener c ser [2, 0] o [0, 2] orden no me importa. Esto debería arrojar una excepción si a no contiene todos los elementos en b.

Tenga en cuenta que esto es diferente de los conjuntos! No estoy interesado en encontrar la diferencia de los conjuntos de elementos en a y b, me interesa la diferencia entre las colecciones reales de elementos en a y b.

Puedo hacer esto con un bucle for, buscando el primer elemento de b en a y luego eliminando el elemento de b y de a, etc. Pero esto no me atrae, sería muy ineficiente (orden de O(n^2) tiempo), aunque no debería ser un problema hacer esto en el tiempo O(n log n) .

Answer 1

Aquí hay una solución relativamente larga pero eficiente y legible. Esta encendido).

def list_diff(list1, list2):
    counts = {}
    for x in list1:
        try:
            counts[x] += 1
        except:
            counts[x] = 1
    for x in list2:
        try:
            counts[x] -= 1
            if counts[x] < 0:
                raise ValueError(''All elements of list2 not in list2'')
        except:
            raise ValueError(''All elements of list2 not in list1'') 
    result = []
    for k, v in counts.iteritems():
        result += v*[k] 
    return result

a = [0, 1, 1, 2, 0]
b = [0, 1, 1]
%timeit list_diff(a, b)
%timeit list_diff(1000*a, 1000*b)
%timeit list_diff(1000000*a, 1000000*b)
100000 loops, best of 3: 4.8 µs per loop
1000 loops, best of 3: 1.18 ms per loop
1 loops, best of 3: 1.21 s per loop

Answer 2

Intenté encontrar una solución más elegante, pero lo mejor que pude hacer fue básicamente lo mismo que Dyno Fu dijo:

from copy import copy

def subtract_lists(a, b):
    """
    >>> a = [0, 1, 2, 1, 0]
    >>> b = [0, 1, 1]
    >>> subtract_lists(a, b)
    [2, 0]

    >>> import random
    >>> size = 10000
    >>> a = [random.randrange(100) for _ in range(size)]
    >>> b = [random.randrange(100) for _ in range(size)]
    >>> c = subtract_lists(a, b)
    >>> assert all((x in a) for x in c)
    """
    a = copy(a)
    for x in b:
        if x in a:
            a.remove(x)
    return a

Answer 3

No estoy seguro de cuál es la objeción a un bucle for: no hay multiset en Python, por lo que no puede usar un contenedor integrado para ayudarlo.

Me parece que cualquier cosa en una línea (si es posible) será probablemente muy difícil de entender. Ve por la legibilidad y KISS. Python no es C :)

Answer 4

Para demostrar el punto de jkp de que "cualquier cosa en una línea probablemente sea complejo de entender", creé una línea. Por favor, no me modifiquen porque entiendo que esta no es una solución que realmente deberían usar. Es solo para propósitos de demostración.

La idea es agregar los valores en uno por uno, siempre que el total de veces que haya agregado ese valor sea menor que el número total de veces que este valor está en un valor menos el número de veces que está en b:

[ value for counter,value in enumerate(a) if a.count(value) >= b.count(value) + a[counter:].count(value) ]

¡El horror! Pero tal vez alguien puede mejorarlo? ¿Está incluso libre de errores?

Editar: Al ver a Devin Jeanpierre comentar sobre el uso de una estructura de datos del diccionario, se me ocurrió este delineador:

sum([ [value]*count for value,count in {value:a.count(value)-b.count(value) for value in set(a)}.items() ], [])

Mejor, pero aún ilegible.

Answer 5

Puedes probar algo como esto:

class mylist(list):

    def __sub__(self, b):
        result = self[:]
        b = b[:]
        while b:
            try:
                result.remove(b.pop())
            except ValueError:
                raise Exception("Not all elements found during subtraction")
        return result


a = mylist([0, 1, 2, 1, 0] )
b = mylist([0, 1, 1])

>>> a - b
[2, 0]

Sin embargo, debe definir qué [1, 2, 3] - [5, 6] debería dar salida, supongo que quiere [1, 2, 3] por eso ignoro el ValueError.

Editar: Ahora veo que quería una excepción si a no contiene todos los elementos, la agregó en lugar de pasar el ValueError.

Answer 6

Puedes usar la construcción del map para hacer esto. Se ve bastante bien, pero ten en cuenta que la línea del map sí devolverá una lista de None s.

a = [1, 2, 3]
b = [2, 3]

map(lambda x:a.remove(x), b)
a

Answer 7

Python 2.7 y 3.2 agregarán las collections.Counter Clase de contador que es un diccionario que mapea elementos con el número de ocurrencias del elemento. Esto se puede usar como multiset.

De acuerdo con los documentos, debería poder hacer algo como esto (no probado, ya que no tengo ninguna versión instalada).

from collections import Counter
a = Counter(0,1,2,1)
b = Counter(0,1,1)

print a - b  # ignores items in b missing in a

# check every element in a is in b
# a[key] returns 0 if key not in a, instead of raising an exception
assert all(a[key] > b[key] for key in b)

Editar :

Como tiene 2,5, puede intentar importarlo y definir su propia versión si falla. De esa manera, se asegurará de obtener la última versión si está disponible, y volver a una versión funcional si no es así. También se beneficiará de las mejoras de velocidad si se convierte en una implementación de C en el futuro.

es decir

try:
   from collections import Counter
except ImportError:
    class Counter(dict):
       ...

Puede encontrar la fuente actual de Python here .

Answer 8

Python 2.7+ y 3.0 tienen collections.Counter (también conocido como multiset). La documentación se vincula a la receta 576611: clase de contador para Python 2.5:

from operator import itemgetter
from heapq import nlargest
from itertools import repeat, ifilter

class Counter(dict):
    ''''''Dict subclass for counting hashable objects.  Sometimes called a bag
    or multiset.  Elements are stored as dictionary keys and their counts
    are stored as dictionary values.

    >>> Counter(''zyzygy'')
    Counter({''y'': 3, ''z'': 2, ''g'': 1})

    ''''''

    def __init__(self, iterable=None, **kwds):
        ''''''Create a new, empty Counter object.  And if given, count elements
        from an input iterable.  Or, initialize the count from another mapping
        of elements to their counts.

        >>> c = Counter()                           # a new, empty counter
        >>> c = Counter(''gallahad'')                 # a new counter from an iterable
        >>> c = Counter({''a'': 4, ''b'': 2})           # a new counter from a mapping
        >>> c = Counter(a=4, b=2)                   # a new counter from keyword args

        ''''''        
        self.update(iterable, **kwds)

    def __missing__(self, key):
        return 0

    def most_common(self, n=None):
        ''''''List the n most common elements and their counts from the most
        common to the least.  If n is None, then list all element counts.

        >>> Counter(''abracadabra'').most_common(3)
        [(''a'', 5), (''r'', 2), (''b'', 2)]

        ''''''        
        if n is None:
            return sorted(self.iteritems(), key=itemgetter(1), reverse=True)
        return nlargest(n, self.iteritems(), key=itemgetter(1))

    def elements(self):
        ''''''Iterator over elements repeating each as many times as its count.

        >>> c = Counter(''ABCABC'')
        >>> sorted(c.elements())
        [''A'', ''A'', ''B'', ''B'', ''C'', ''C'']

        If an element''s count has been set to zero or is a negative number,
        elements() will ignore it.

        ''''''
        for elem, count in self.iteritems():
            for _ in repeat(None, count):
                yield elem

    # Override dict methods where the meaning changes for Counter objects.

    @classmethod
    def fromkeys(cls, iterable, v=None):
        raise NotImplementedError(
            ''Counter.fromkeys() is undefined.  Use Counter(iterable) instead.'')

    def update(self, iterable=None, **kwds):
        ''''''Like dict.update() but add counts instead of replacing them.

        Source can be an iterable, a dictionary, or another Counter instance.

        >>> c = Counter(''which'')
        >>> c.update(''witch'')           # add elements from another iterable
        >>> d = Counter(''watch'')
        >>> c.update(d)                 # add elements from another counter
        >>> c[''h'']                      # four ''h'' in which, witch, and watch
        4

        ''''''        
        if iterable is not None:
            if hasattr(iterable, ''iteritems''):
                if self:
                    self_get = self.get
                    for elem, count in iterable.iteritems():
                        self[elem] = self_get(elem, 0) + count
                else:
                    dict.update(self, iterable) # fast path when counter is empty
            else:
                self_get = self.get
                for elem in iterable:
                    self[elem] = self_get(elem, 0) + 1
        if kwds:
            self.update(kwds)

    def copy(self):
        ''Like dict.copy() but returns a Counter instance instead of a dict.''
        return Counter(self)

    def __delitem__(self, elem):
        ''Like dict.__delitem__() but does not raise KeyError for missing values.''
        if elem in self:
            dict.__delitem__(self, elem)

    def __repr__(self):
        if not self:
            return ''%s()'' % self.__class__.__name__
        items = '', ''.join(map(''%r: %r''.__mod__, self.most_common()))
        return ''%s({%s})'' % (self.__class__.__name__, items)

    # Multiset-style mathematical operations discussed in:
    #       Knuth TAOCP Volume II section 4.6.3 exercise 19
    #       and at http://en.wikipedia.org/wiki/Multiset
    #
    # Outputs guaranteed to only include positive counts.
    #
    # To strip negative and zero counts, add-in an empty counter:
    #       c += Counter()

    def __add__(self, other):
        ''''''Add counts from two counters.

        >>> Counter(''abbb'') + Counter(''bcc'')
        Counter({''b'': 4, ''c'': 2, ''a'': 1})


        ''''''
        if not isinstance(other, Counter):
            return NotImplemented
        result = Counter()
        for elem in set(self) | set(other):
            newcount = self[elem] + other[elem]
            if newcount > 0:
                result[elem] = newcount
        return result

    def __sub__(self, other):
        '''''' Subtract count, but keep only results with positive counts.

        >>> Counter(''abbbc'') - Counter(''bccd'')
        Counter({''b'': 2, ''a'': 1})

        ''''''
        if not isinstance(other, Counter):
            return NotImplemented
        result = Counter()
        for elem in set(self) | set(other):
            newcount = self[elem] - other[elem]
            if newcount > 0:
                result[elem] = newcount
        return result

    def __or__(self, other):
        ''''''Union is the maximum of value in either of the input counters.

        >>> Counter(''abbb'') | Counter(''bcc'')
        Counter({''b'': 3, ''c'': 2, ''a'': 1})

        ''''''
        if not isinstance(other, Counter):
            return NotImplemented
        _max = max
        result = Counter()
        for elem in set(self) | set(other):
            newcount = _max(self[elem], other[elem])
            if newcount > 0:
                result[elem] = newcount
        return result

    def __and__(self, other):
        '''''' Intersection is the minimum of corresponding counts.

        >>> Counter(''abbb'') & Counter(''bcc'')
        Counter({''b'': 1})

        ''''''
        if not isinstance(other, Counter):
            return NotImplemented
        _min = min
        result = Counter()
        if len(self) < len(other):
            self, other = other, self
        for elem in ifilter(self.__contains__, other):
            newcount = _min(self[elem], other[elem])
            if newcount > 0:
                result[elem] = newcount
        return result


if __name__ == ''__main__'':
    import doctest
    print doctest.testmod()

Entonces puedes escribir

 a = Counter([0,1,2,1,0])
 b = Counter([0, 1, 1])
 c = a - b
 print list(c.elements())  # [0, 2]

Answer 9

Sé que "para" no es lo que quieres, pero es simple y claro:

for x in b:
  a.remove(x)

O si los miembros de b pueden no estar en a uso entonces:

for x in b:
  if x in a:
    a.remove(x)

Answer 10

para usar la comprensión de la lista:

[i for i in a if not i in b or b.remove(i)]

Haría el truco. Sin embargo, cambiaría b en el proceso. Pero estoy de acuerdo con jkp y Dyno Fu en que usar un bucle for sería mejor.

Tal vez alguien puede crear un mejor ejemplo que utiliza la comprensión de la lista, pero todavía es KISS?

Answer 11

Lo haría de una manera más fácil:

a_b = [e for e in a if not e in b ]

..as que escribió, esto está mal, solo funciona si los artículos son únicos en las listas. Y si lo son, es mejor usar

a_b = list(set(a) - set(b))

Answer 12

c = [i for i in b if i not in a]

Answer 13

list(set([x for x in a if x not in b]))

• Deja a y b intactos.
• Es un conjunto único de "a - b".
• Hecho.