Operación de resta de lista de Python

Quiero hacer algo similar a esto:

>>> x = [1,2,3,4,5,6,7,8,9,0]  
>>> x  
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]  
>>> y = [1,3,5,7,9]  
>>> y  
[1, 3, 5, 7, 9]  
>>> y - x   # (should return [2,4,6,8,0])

Pero esto no es compatible con las listas de Python. ¿Cuál es la mejor manera de hacerlo?

Use una lista de comprensión:

[item for item in x if item not in y]

Si desea utilizar la -sintaxis infija, simplemente puede hacer:

class MyList(list):
    def __init__(self, *args):
        super(MyList, self).__init__(args)

    def __sub__(self, other):
        return self.__class__(*[item for item in self if item not in other])

entonces puedes usarlo como:

x = MyList(1, 2, 3, 4)
y = MyList(2, 5, 2)
z = x - y   

Pero si no necesita absolutamente las propiedades de la lista (por ejemplo, ordenar), simplemente use conjuntos como recomiendan las otras respuestas.

Usar diferencia de conjunto

>>> z = list(set(x) - set(y))
>>> z
[0, 8, 2, 4, 6]

O puede que solo se establezcan x e y para que no tenga que hacer ninguna conversión.

Esa es una operación de "resta de conjuntos". Use la estructura de datos establecida para eso.

En Python 2.7:

x = {1,2,3,4,5,6,7,8,9,0}
y = {1,3,5,7,9}
print x - y

Salida:

>>> print x - y
set([0, 8, 2, 4, 6])

Si los artículos duplicados y pedidos son un problema:

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

a = [1,2,3,3,3,3,4]
b = [1,3]
result: [2, 3, 3, 3, 4]

Para muchos casos de uso, la respuesta que desea es:

ys = set(y)
[item for item in x if item not in ys]

Este es un híbrido entre la respuesta de aaronasterling y la respuesta de quantumSoup .

La versión de aaronasterling hace len(y)comparaciones de elementos para cada elemento x, por lo que lleva tiempo cuadrático. La versión de quantumSoup usa conjuntos, por lo que realiza una sola búsqueda de conjuntos de tiempo constante para cada elemento en x, pero porque convierte ambos x yy en conjuntos, pierde el orden de sus elementos.

Al convertir solo yen un conjunto e iterar xen orden, obtienes lo mejor de ambos mundos: tiempo lineal y preservación del orden. *

Sin embargo, esto todavía tiene un problema con la versión de quantumSoup: requiere que sus elementos sean hashable. Eso está más o menos integrado en la naturaleza de los conjuntos. ** Si está tratando de restar, por ejemplo, una lista de dictos de otra lista de dictos, pero la lista para restar es grande, ¿qué debe hacer?

Si puede decorar sus valores de alguna manera para que se puedan compartir, eso resuelve el problema. Por ejemplo, con un diccionario plano cuyos valores son en sí mismos hashables:

ys = {tuple(item.items()) for item in y}
[item for item in x if tuple(item.items()) not in ys]

Si sus tipos son un poco más complicados (por ejemplo, a menudo se trata de valores compatibles con JSON, que son hashable, o listas o dictados cuyos valores son recursivamente del mismo tipo), aún puede usar esta solución. Pero algunos tipos simplemente no se pueden convertir en algo hashaable.

Si sus elementos no son, y no se pueden hacer, hashables, pero son comparables, al menos puede obtener un tiempo de registro lineal ( O(N*log M)que es mucho mejor que el O(N*M)tiempo de la solución de la lista, pero no tan bueno como el O(N+M)tiempo de la solución establecida) ordenando y usando bisect:

ys = sorted(y)
def bisect_contains(seq, item):
    index = bisect.bisect(seq, item)
    return index < len(seq) and seq[index] == item
[item for item in x if bisect_contains(ys, item)]

Si sus artículos no son hashables ni comparables, entonces está atrapado con la solución cuadrática.

_{* Tenga en cuenta que también puede hacerlo utilizando un par de OrderedSetobjetos, para los cuales puede encontrar recetas y módulos de terceros. Pero creo que esto es más simple.}

_{** La razón por la que las búsquedas de conjuntos son de tiempo constante es que todo lo que tiene que hacer es calcular el valor hash y ver si hay una entrada para ese hash. Si no puede cambiar el valor, esto no funcionará.}

Buscar valores en conjuntos es más rápido que buscarlos en listas:

[item for item in x if item not in set(y)]

Creo que esto escalará un poco mejor que:

[item for item in x if item not in y]

Ambos preservan el orden de las listas.

Si las listas permiten elementos duplicados, puede usar Contador de colecciones:

from collections import Counter
result = list((Counter(x)-Counter(y)).elements())

Si necesita preservar el orden de los elementos de x:

result = [ v for c in [Counter(y)] for v in x if not c[v] or c.subtract([v]) ]

Creo que la forma más fácil de lograr esto es usando set ().

>>> x = [1,2,3,4,5,6,7,8,9,0]  
>>> y = [1,3,5,7,9]  
>>> list(set(x)- set(y))
[0, 2, 4, 6, 8]

Las otras soluciones tienen uno de los pocos problemas:

1. No preservan el orden, o
2. No eliminan un recuento preciso de elementos, por ejemplo, for x = [1, 2, 2, 2]y y = [2, 2]se convierten en ya set, y eliminan todos los elementos coincidentes (dejando [1]solo) o eliminan uno de cada elemento único (salir [1, 2, 2]), cuando el comportamiento adecuado sería eliminar 2dos veces, dejando[1, 2] o
3. Funcionan O(m * n), donde una solución óptima puede O(m + n)funcionar

Alain estaba en el camino correctoCounter para resolver el # 2 y el # 3, pero esa solución perderá el orden. La solución que conserva el orden (eliminando las primeras ncopias de cada valor para las nrepeticiones en los listvalores a eliminar) es:

from collections import Counter

x = [1,2,3,4,3,2,1]  
y = [1,2,2]  
remaining = Counter(y)

out = []
for val in x:
    if remaining[val]:
        remaining[val] -= 1
    else:
        out.append(val)
# out is now [3, 4, 3, 1], having removed the first 1 and both 2s.

Pruébalo en línea!

Para que elimine las últimas copias de cada elemento, simplemente cambie el forbucle for val in reversed(x):y agréguelo out.reverse()inmediatamente después de salir delfor ciclo.

La construcción de Counteres O(n)en términos de ylongitud, la iteración xes O(n)en términos de xlongitud, y Counterlas pruebas de membresía y la mutación son O(1), mientras que list.appendse amortiza O(1)(un hecho appendpuede ser O(n), pero para muchos appends, los promedios generales de Big-O O(1)ya que cada vez menos de ellos requieren una reasignación), por lo que el trabajo general realizado esO(m + n) .

También puede probar para determinar si había algún elemento yque no se eliminó xmediante la prueba:

remaining = +remaining  # Removes all keys with zero counts from Counter
if remaining:
    # remaining contained elements with non-zero counts

Prueba esto.

def subtract_lists(a, b):
    """ Subtracts two lists. Throws ValueError if b contains items not in a """
    # Terminate if b is empty, otherwise remove b[0] from a and recurse
    return a if len(b) == 0 else [a[:i] + subtract_lists(a[i+1:], b[1:]) 
                                  for i in [a.index(b[0])]][0]

>>> x = [1,2,3,4,5,6,7,8,9,0]
>>> y = [1,3,5,7,9]
>>> subtract_lists(x,y)
[2, 4, 6, 8, 0]
>>> x = [1,2,3,4,5,6,7,8,9,0,9]
>>> subtract_lists(x,y)
[2, 4, 6, 8, 0, 9]     #9 is only deleted once
>>>

La respuesta proporcionada por @aaronasterling se ve bien, sin embargo, no es compatible con la interfaz por defecto de la lista: x = MyList(1, 2, 3, 4)vs x = MyList([1, 2, 3, 4]). Por lo tanto, el siguiente código se puede usar como una lista más amigable para python:

class MyList(list):
    def __init__(self, *args):
        super(MyList, self).__init__(*args)

    def __sub__(self, other):
        return self.__class__([item for item in self if item not in other])

Ejemplo:

x = MyList([1, 2, 3, 4])
y = MyList([2, 5, 2])
z = x - y

Creo que esto es más rápido:

In [1]: a = [1,2,3,4,5]

In [2]: b = [2,3,4,5]

In [3]: c = set(a) ^ set(b)

In [4]: c
Out[4]: {1}

Este ejemplo resta dos listas:

# List of pairs of points
list = []
list.append([(602, 336), (624, 365)])
list.append([(635, 336), (654, 365)])
list.append([(642, 342), (648, 358)])
list.append([(644, 344), (646, 356)])
list.append([(653, 337), (671, 365)])
list.append([(728, 13), (739, 32)])
list.append([(756, 59), (767, 79)])

itens_to_remove = []
itens_to_remove.append([(642, 342), (648, 358)])
itens_to_remove.append([(644, 344), (646, 356)])

print("Initial List Size: ", len(list))

for a in itens_to_remove:
    for b in list:
        if a == b :
            list.remove(b)

print("Final List Size: ", len(list))