¿Cómo sustraigo una lista de otra?

quiero tomar el diferencia entre listas x y y:

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

Use una lista de comprensión para calcular la diferencia manteniendo el original orden de x:

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

Si no necesita las propiedades de la lista (por ejemplo, ordenar), use un establecer diferenciacomo sugieren las otras respuestas:

list(set(x) - set(y))

Permitir x - y sintaxis infija, anular __sub__ en una clase que hereda de list:

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

Uso:

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

Usar establecer diferencia

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

O puede que simplemente tenga x e y configurados para que no tenga que hacer ninguna conversión.

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]

Esa es una operación de “resta de conjunto”. Use la estructura de datos establecida para eso.

En Pitón 2.7:

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

Producción:

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

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 sí len(y) comparaciones de artículos para cada elemento en x, entonces toma tiempo cuadrático. La versión de quantumSoup usa conjuntos, por lo que realiza una única búsqueda de conjuntos en tiempo constante para cada elemento en x—sino, porque convierte ambos x y y en conjuntos, pierde el orden de sus elementos.

Convirtiendo solo y en un conjunto, e iterando x en orden, obtiene 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á bastante integrado en la naturaleza de los conjuntos.** Si está intentando, por ejemplo, restar una lista de dictados de otra lista de dictados, pero la lista para restar es grande, ¿qué debe hacer?

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

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 se pueden modificar, 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 hashable.

Si sus elementos no son, y no se pueden hacer, hashable, pero son comparables, al menos puede obtener un tiempo logarítmico 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 elementos no se pueden modificar ni comparar, entonces está atascado con la solución cuadrática.

_{* Tenga en cuenta que también puede hacer esto usando un par de OrderedSet objetos, para los que 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 codificar el valor y ver si hay una entrada para ese hash. Si no puede codificar el valor, esto no funcionará.}

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

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

Si necesita conservar 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]) ]

Las otras soluciones tienen uno de algunos problemas:

1. No preservan el orden, o
2. No eliminan un recuento preciso de elementos, por ejemplo, para x = [1, 2, 2, 2] y y = [2, 2] se convierten y a un sety eliminar todos los elementos coincidentes (dejando [1] solamente) o quitar uno de cada elemento único (dejando [1, 2, 2]), cuando el comportamiento adecuado sería eliminar 2 dos veces, dejando [1, 2]o
3. Ellas hacen O(m * n) trabajo, donde una solución óptima puede hacer O(m + n) trabajar

Alain estaba en el camino correcto con Counter para resolver #2 y #3, pero esa solución perderá el orden. La solución que preserva el orden (quitando el primer n copias de cada valor para n repeticiones en el list de valores 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ébelo en línea!

Para hacerlo quitar el último copias de cada elemento, simplemente cambie el for bucle a for val in reversed(x): y añadir out.reverse() inmediatamente después de salir del for bucle.

Construyendo el Counter es O(n) en términos de ylongitud de , iterando x es O(n) en términos de xlongitud de , y Counter las pruebas de membresía y la mutación son O(1)mientras list.append se amortiza O(1) (un dado append puede ser O(n)pero para muchos appends, los promedios generales de O grande O(1) ya que cada vez menos de ellos requieren una reasignación), por lo que el trabajo total realizado es O(m + n).

También puede probar para determinar si había algún elemento en y que no fueron quitados de x probando:

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