Python, diferencia en la lista de cálculo

En Python, ¿cuál es la mejor manera de calcular la diferencia entre dos listas?

ejemplo

A = [1,2,3,4] B = [2,5] A - B = [1,3,4] B - A = [5] 

Use set si no le importa el orden o la repetición de los artículos. Use la lista de comprensión si lo hace:

 >>> def diff(first, second): second = set(second) return [item for item in first if item not in second] >>> diff(A, B) [1, 3, 4] >>> diff(B, A) [5] >>> 

Si el orden no importa, simplemente puede calcular la diferencia establecida:

 >>> set([1,2,3,4]) - set([2,5]) set([1, 4, 3]) >>> set([2,5]) - set([1,2,3,4]) set([5]) 

Puedes hacer un

 list(set(A)-set(B)) 

y

 list(set(B)-set(A)) 

Un trazador de líneas:

 diff = lambda l1,l2: [x for x in l1 if x not in l2] diff(A,B) diff(B,A) 

O:

 diff = lambda l1,l2: filter(lambda x: x not in l2, l1) diff(A,B) diff(B,A) 

Los ejemplos anteriores trivializaron el problema de calcular diferencias. Suponiendo que la clasificación o la deduplicación definitivamente hacen que sea más fácil calcular la diferencia, pero si su comparación no puede permitirse esas suposiciones, necesitará una implementación no trivial de un algoritmo de diferencias. Ver difflib en la biblioteca estándar de python.

 from difflib import SequenceMatcher squeeze=SequenceMatcher( None, A, B ) print "A - B = [%s]"%( reduce( lambda p,q: p+q, map( lambda t: squeeze.a[t[1]:t[2]], filter(lambda x:x[0]!='equal', squeeze.get_opcodes() ) ) ) ) 

A – B = [[1, 3, 4]]

Python 2.7.3 (predeterminado, 27 de febrero de 2014, 19:58:35) – IPython 1.1.0 – timeit: (github gist)

 def diff(a, b): b = set(b) return [aa for aa in a if aa not in b] def set_diff(a, b): return list(set(a) - set(b)) diff_lamb_hension = lambda l1,l2: [x for x in l1 if x not in l2] diff_lamb_filter = lambda l1,l2: filter(lambda x: x not in l2, l1) from difflib import SequenceMatcher def squeezer(a, b): squeeze = SequenceMatcher(None, a, b) return reduce(lambda p,q: p+q, map( lambda t: squeeze.a[t[1]:t[2]], filter(lambda x:x[0]!='equal', squeeze.get_opcodes()))) 

Resultados:

 # Small a = range(10) b = range(10/2) timeit[diff(a, b)] 100000 loops, best of 3: 1.97 µs per loop timeit[set_diff(a, b)] 100000 loops, best of 3: 2.71 µs per loop timeit[diff_lamb_hension(a, b)] 100000 loops, best of 3: 2.1 µs per loop timeit[diff_lamb_filter(a, b)] 100000 loops, best of 3: 3.58 µs per loop timeit[squeezer(a, b)] 10000 loops, best of 3: 36 µs per loop # Medium a = range(10**4) b = range(10**4/2) timeit[diff(a, b)] 1000 loops, best of 3: 1.17 ms per loop timeit[set_diff(a, b)] 1000 loops, best of 3: 1.27 ms per loop timeit[diff_lamb_hension(a, b)] 1 loops, best of 3: 736 ms per loop timeit[diff_lamb_filter(a, b)] 1 loops, best of 3: 732 ms per loop timeit[squeezer(a, b)] 100 loops, best of 3: 12.8 ms per loop # Big a = xrange(10**7) b = xrange(10**7/2) timeit[diff(a, b)] 1 loops, best of 3: 1.74 s per loop timeit[set_diff(a, b)] 1 loops, best of 3: 2.57 s per loop timeit[diff_lamb_filter(a, b)] # too long to wait for timeit[diff_lamb_filter(a, b)] # too long to wait for timeit[diff_lamb_filter(a, b)] # TypeError: sequence index must be integer, not 'slice' 

@ roman-bodnarchuk lista comprensiones función def diff (a, b) parece ser más rápida.

 A = [1,2,3,4] B = [2,5] #A - B x = list(set(A) - set(B)) #B - A y = list(set(B) - set(A)) print x print y 

Usted querría utilizar un set lugar de una list .

En caso de que desee que la diferencia recursivamente profundice en los elementos de su lista, he escrito un paquete para python: https://github.com/erasmose/deepdiff

Instalación

Instalar desde PyPi:

 pip install deepdiff 

Si eres Python3 necesitas instalar también:

 pip install future six 

Ejemplo de uso

 >>> from deepdiff import DeepDiff >>> from pprint import pprint >>> from __future__ import print_function 

El mismo objeto devuelve vacío

 >>> t1 = {1:1, 2:2, 3:3} >>> t2 = t1 >>> ddiff = DeepDiff(t1, t2) >>> print (ddiff.changes) {} 

El tipo de un artículo ha cambiado

 >>> t1 = {1:1, 2:2, 3:3} >>> t2 = {1:1, 2:"2", 3:3} >>> ddiff = DeepDiff(t1, t2) >>> print (ddiff.changes) {'type_changes': ["root[2]: 2= vs. 2="]} 

El valor de un artículo ha cambiado

 >>> t1 = {1:1, 2:2, 3:3} >>> t2 = {1:1, 2:4, 3:3} >>> ddiff = DeepDiff(t1, t2) >>> print (ddiff.changes) {'values_changed': ['root[2]: 2 ====>> 4']} 

Artículo añadido y / o eliminado

 >>> t1 = {1:1, 2:2, 3:3, 4:4} >>> t2 = {1:1, 2:4, 3:3, 5:5, 6:6} >>> ddiff = DeepDiff(t1, t2) >>> pprint (ddiff.changes) {'dic_item_added': ['root[5, 6]'], 'dic_item_removed': ['root[4]'], 'values_changed': ['root[2]: 2 ====>> 4']} 

Diferencia de cadena

 >>> t1 = {1:1, 2:2, 3:3, 4:{"a":"hello", "b":"world"}} >>> t2 = {1:1, 2:4, 3:3, 4:{"a":"hello", "b":"world!"}} >>> ddiff = DeepDiff(t1, t2) >>> pprint (ddiff.changes, indent = 2) { 'values_changed': [ 'root[2]: 2 ====>> 4', "root[4]['b']:\n--- \n+++ \n@@ -1 +1 @@\n-world\n+world!"]} >>> >>> print (ddiff.changes['values_changed'][1]) root[4]['b']: --- +++ @@ -1 +1 @@ -world +world! 

Diferencia de cadena 2

 >>> t1 = {1:1, 2:2, 3:3, 4:{"a":"hello", "b":"world!\nGoodbye!\n1\n2\nEnd"}} >>> t2 = {1:1, 2:2, 3:3, 4:{"a":"hello", "b":"world\n1\n2\nEnd"}} >>> ddiff = DeepDiff(t1, t2) >>> pprint (ddiff.changes, indent = 2) { 'values_changed': [ "root[4]['b']:\n--- \n+++ \n@@ -1,5 +1,4 @@\n-world!\n-Goodbye!\n+world\n 1\n 2\n End"]} >>> >>> print (ddiff.changes['values_changed'][0]) root[4]['b']: --- +++ @@ -1,5 +1,4 @@ -world! -Goodbye! +world 1 2 End 

Cambio de tipo

 >>> t1 = {1:1, 2:2, 3:3, 4:{"a":"hello", "b":[1, 2, 3]}} >>> t2 = {1:1, 2:2, 3:3, 4:{"a":"hello", "b":"world\n\n\nEnd"}} >>> ddiff = DeepDiff(t1, t2) >>> pprint (ddiff.changes, indent = 2) { 'type_changes': [ "root[4]['b']: [1, 2, 3]= vs. world\n\n\nEnd="]} 

Diferencia de lista

 >>> t1 = {1:1, 2:2, 3:3, 4:{"a":"hello", "b":[1, 2, 3]}} >>> t2 = {1:1, 2:2, 3:3, 4:{"a":"hello", "b":[1, 2]}} >>> ddiff = DeepDiff(t1, t2) >>> pprint (ddiff.changes, indent = 2) { 'list_removed': ["root[4]['b']: [3]"]} 

Diferencia de lista 2: tenga en cuenta que NO tiene en cuenta el orden

 >>> # Note that it DOES NOT take order into account ... t1 = {1:1, 2:2, 3:3, 4:{"a":"hello", "b":[1, 2, 3]}} >>> t2 = {1:1, 2:2, 3:3, 4:{"a":"hello", "b":[1, 3, 2]}} >>> ddiff = DeepDiff(t1, t2) >>> pprint (ddiff.changes, indent = 2) { } 

Lista que contiene el diccionario:

 >>> t1 = {1:1, 2:2, 3:3, 4:{"a":"hello", "b":[1, 2, {1:1, 2:2}]}} >>> t2 = {1:1, 2:2, 3:3, 4:{"a":"hello", "b":[1, 2, {1:3}]}} >>> ddiff = DeepDiff(t1, t2) >>> pprint (ddiff.changes, indent = 2) { 'dic_item_removed': ["root[4]['b'][2][2]"], 'values_changed': ["root[4]['b'][2][1]: 1 ====>> 3"]} 

forma más sencilla,

usar set (). diferencia (set ())

 list_a = [1,2,3] list_b = [2,3] print set(list_a).difference(set(list_b)) 

la respuesta está set([1])

En el caso de una lista de diccionarios , la solución de comprensión de lista completa funciona mientras que la solución de set aumenta

 TypeError: unhashable type: 'dict' 

Caso de prueba

 def diff(a, b): return [aa for aa in a if aa not in b] d1 = {"a":1, "b":1} d2 = {"a":2, "b":2} d3 = {"a":3, "b":3} >>> diff([d1, d2, d3], [d2, d3]) [{'a': 1, 'b': 1}] >>> diff([d1, d2, d3], [d1]) [{'a': 2, 'b': 2}, {'a': 3, 'b': 3}] 

Al echar un vistazo a TimeComplexity of In-operator, en el peor de los casos funciona con O (n). Incluso para conjuntos.

Entonces, al comparar dos matrices, tendremos una TimeComplexity de O (n) en el mejor de los casos y O (n ^ 2) en el peor de los casos.

Una solución alternativa (pero desafortunadamente más compleja), que funciona con O (n) en el mejor y peor de los casos, es esta:

 # Compares the difference of list a and b # uses a callback function to compare items def diff(a, b, callback): a_missing_in_b = [] ai = 0 bi = 0 a = sorted(a, callback) b = sorted(b, callback) while (ai < len(a)) and (bi < len(b)): cmp = callback(a[ai], b[bi]) if cmp < 0: a_missing_in_b.append(a[ai]) ai += 1 elif cmp > 0: # Item b is missing in a bi += 1 else: # a and b intersecting on this item ai += 1 bi += 1 # if a and b are not of same length, we need to add the remaining items for ai in xrange(ai, len(a)): a_missing_in_b.append(a[ai]) return a_missing_in_b 

p.ej

 >>> a=[1,2,3] >>> b=[2,4,6] >>> diff(a, b, cmp) [1, 3] 

Código simple que te da la diferencia con varios elementos si quieres que:

 a=[1,2,3,3,4] b=[2,4] tmp = copy.deepcopy(a) for k in b: if k in tmp: tmp.remove(k) print(tmp)