una - Restando dos listas en Python
recorrer dos listas a la vez python (13)
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
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) .
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
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 :)
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.
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.
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
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 .
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]
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)
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?
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))
c = [i for i in b if i not in a]
list(set([x for x in a if x not in b]))
- Deja
aybintactos. - Es un conjunto único de "a - b".
- Hecho.