wake-up-neo.net

Python, Listenunterschied berechnen

Wie kann man in Python den Unterschied zwischen zwei Listen am besten berechnen?

beispiel

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

A - B = [1,3,4]
B - A = [5]
147
Mike

Verwenden Sie set, wenn Sie sich nicht für die Bestellung oder Wiederholung von Artikeln interessieren. Verwenden Sie Listenverständnisse wenn Sie Folgendes tun:

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

Wenn die Reihenfolge keine Rolle spielt, können Sie einfach die eingestellte Differenz berechnen:

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

Sie können ein tun 

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

und

list(set(B)-set(A))
58
Senthil Kumaran

Einzeiler:

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

Oder:

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

Die obigen Beispiele trivialisierten das Problem der Differenzberechnung. Wenn Sie davon ausgehen, dass die Sortierung oder Deduplizierung definitiv einfacher ist, wird die Differenz berechnet. Wenn sich Ihr Vergleich diese Annahmen jedoch nicht leisten kann, benötigen Sie eine nicht triviale Implementierung eines Diff-Algorithmus. Siehe difflib in der Python-Standardbibliothek.

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

13
Kevin

Python 2.7.3 (Standard, 27.02.2014, 19:58:35) - IPython 1.1.0 - Zeit: (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())))

Ergebnisse:

# 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 Liste Verständnis Funktionen def diff (a, b) scheint schneller zu sein.

12
Moreno
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 
9
Saksham Varma

Sie möchten eine set anstelle einer list verwenden.

8

einfachste weise,

verwenden Sie set (). difference (set ())

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

antwort ist set([1])

Falls Sie möchten, dass der Unterschied rekursiv in die Elemente Ihrer Liste eingeht, habe ich ein Paket für Python geschrieben: https://github.com/erasmose/deepdiff

Installation

Installieren Sie von PyPi:

pip install deepdiff

Wenn Sie Python3 sind, müssen Sie auch Folgendes installieren:

pip install future six

Verwendungsbeispiel

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

Das gleiche Objekt wird leer zurückgegeben

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

Der Typ eines Elements hat sich geändert

>>> 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=<type 'int'> vs. 2=<type 'str'>"]}

Der Wert eines Artikels hat sich geändert

>>> 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']}

Element hinzugefügt und/oder entfernt

>>> 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']}

String-Unterschied

>>> 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+++ \[email protected]@ -1 +1 @@\n-world\n+world!"]}
>>>
>>> print (ddiff.changes['values_changed'][1])
    root[4]['b']:
    --- 
    +++ 
    @@ -1 +1 @@
    -world
    +world!

Saitenunterschied 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+++ \[email protected]@ -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

Typänderung

>>> 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]=<type 'list'> vs. world\n\n\nEnd=<type 'str'>"]}

Unterschied auflisten

>>> 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]"]}

Listendifferenz 2: Beachten Sie, dass die Bestellung NICHT berücksichtigt wird

>>> # 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)
    { }

Liste mit Wörterbuch:

>>> 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"]}
3
Seperman

Im Falle einer Liste von Wörterbüchern funktioniert die vollständige Listenverständnislösung, während sich die set-Lösung erhöht

TypeError: unhashable type: 'dict'

Testfall

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}]
1
joao

Beim Betrachten von TimeComplexity von In-Operator funktioniert es im schlimmsten Fall mit O (n). Auch für Sets.

Beim Vergleich zweier Arrays haben wir im besten Fall eine TimeComplexity von O(n) und im ungünstigsten Fall O (n ^ 2).

Eine alternative (aber leider komplexere) Lösung, die im besten und im schlechtesten Fall mit O(n) funktioniert, ist diese:

# 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

z.B.

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

Einfacher Code, der Ihnen den Unterschied zu mehreren Elementen gibt, wenn Sie das möchten: 

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)
0
A.M.