계산 목록 차이

계산 목록 차이

파이톤에서, 두 목록 사이의 차이를 계산하는 가장 좋은 방법은 무엇인가?

예시

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

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

순서가 중요하지 않으면 설정 차이를 간단하게 계산할 수 있다.

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

사용하다set아이템 순서나 반복에 신경 쓰지 않는다면.다음 작업을 수행하는 경우 목록 포괄성을 사용하십시오.

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

할 수 있다.

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

그리고

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

단일 라이너:

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

또는:

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

위의 예들은 차이를 계산하는 문제를 대수롭지 않게 여겼다.정렬 또는 중복 제거가 확실히 차이를 계산하기 쉽다고 가정할 때, 비교가 그러한 가정들을 감당할 수 없다면 당신은 diff 알고리즘의 비종교적인 구현이 필요할 것이다.python 표준 라이브러리의 difflib를 참조하십시오.

#! /usr/bin/python2
from difflib import SequenceMatcher

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

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

아니면 파이썬3...

#! /usr/bin/python3
from difflib import SequenceMatcher
from functools import reduce

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

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 (기본값, 2014년 2월 27일, 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())))

결과:

# 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'

@loman-bodnarchuk list diffence(a, b) 기능이 더 빠른 것 같다.

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 

A을(를) 사용하고 싶을 것이다.seta 대신에list.

만약 당신이 그 차이를 반복해서 당신의 리스트의 항목들로 깊게 들어가고자 한다면, 나는 python을 위한 패키지를 작성했다: https://github.com/erasmose/deepdiff

설치

PyPi에서 설치:

pip install deepdiff

Python3인 경우 다음을 설치해야 한다.

pip install future six

사용 예

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

동일한 개체 반환이 비어 있음

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

품목 유형이 변경됨

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

항목의 값이 변경됨

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

추가 및/또는 제거된 항목

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

끈 차이

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

끈 차이 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

유형변경

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

리스트 차이

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

목록 차이 2: 순서를 고려하지 않는다는 점에 유의하십시오.

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

사전이 들어 있는 목록:

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

가장 간단한 방법,

set()를 사용하다.

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

답은set([1])

사전 목록의 경우 전체 목록 이해 솔루션이 작동하는 동안set해결책이 떠오르다.

TypeError: unhashable type: 'dict'

테스트 케이스

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

원하는 경우 여러 항목과의 차이를 제공하는 단순 코드:

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)

이렇게 하는 데는 세 가지 옵션이 있는데, 그 중 두 가지는 허용되고 한 가지는 실행되어서는 안 된다.

높은 수준에서 세 가지 옵션은 다음과 같다.

1. 두 세트 빼기(때로는 가장 좋음)
2. 각 목록 항목이 집합에 있는지 확인(대부분의 시간)
3. 각 목록 항목이 목록에 있는지 확인(하지 않음)

옵션 3)은 옵션 2)를 선택하여서는 안 된다.애플리케이션의 필요에 따라 옵션 1) 또는 2)를 선호할 수 있지만, 2)는 대부분의 사용 사례에서 선호되는 접근법일 수 있다.2)는 둘 다 가지고 있기 때문에 1)의 성과와 매우 유사하다.O(m + n)시의 복잡성 와는 대조적으로 2)는 1)에 걸쳐 이익을 와 모든 대조적으로 2)는 1) 이상의 공간 복잡성에서 한계적 이익을 가지며, 원래 목록의 순서와 중복성을 모두 유지한다.

중복되는 것을 제거하고 주문에 신경 쓰지 않으려면 1)이 당신에게 가장 적합할 것 같다.

import time

def fun1(l1, l2):
    # Order and duplications in l1 are both lost, O(m) + O(n)
    return set(l1) - set(l2)

def fun2(l1, l2):
    # Order and duplications in l1 are both preserved, O(m) + O(n)
    l2_set = set(l2)
    return [item for item in l1 if item not in l2_set]

def fun3(l1, l2):
    # Order and duplications in l1 are both preserved, O(m * n)
    # Don't do
    return [item for item in l1 if item not in l2]

A = list(range(7500))
B = list(range(5000, 10000))

loops = 100

start = time.time()
for _ in range(loops):
    fun1(A, B)
print(f"fun1 time: {time.time() - start}")

start = time.time()
for _ in range(loops):
    fun2(A, B)
print(f"fun2 time: {time.time() - start}")

start = time.time()
for _ in range(loops):
    fun3(A, B)
print(f"fun3 time: {time.time() - start}")

fun1 time: 0.03749704360961914
fun2 time: 0.04109621047973633
fun3 time: 32.55076885223389

반복과 엄격한 차이를 원하는 경우를 처리하기 위해 답변을 추가하는 것, 즉, 첫 번째 리스트에서 우리가 지키고자 하는 반복이 있다(예: 얻기 위해).

[1, 1, 1, 2] - [1, 1] --> [1, 2]

우리는 우아한 차이 기능을 갖기 위해 추가 카운터를 사용할 수 있다.

from collections import Counter

def diff(first, second):
    secondCntr = Counter(second)
    second = set(second)
    res = []
    for i in first:
        if i not in second:
            res.append(i)
        elif i in secondCntr:
            if secondCntr[i] > 0:
                secondCntr[i] -= 1
            else:
                res.append(i)        
    return res

이 실에는 A에서 중복을 보존하는 해결책이 보이지 않는다.A의 요소가 B의 요소와 일치할 때, 이 요소는 B에서 제거되어야 하기 때문에 A에서 동일한 요소가 다시 발생할 때, 이 요소가 B에 한 번만 나타나면 차이에 나타나야 한다.

def diff(first, second):
   l2 = list(second)
   l3 = []
   for el in first:
      if el in l2:
         l2.remove(el)
      else:
         l3 += [el]
   return l3

l1 = [1, 2, 1, 3, 4]
l2 = [1, 2, 3, 3]
diff(l1, l2)
>>> [1, 4]

In-operator의 TimeComplexity를 살펴보면 최악의 경우 O(n)와 함께 작동한다.세트까지.

따라서 두 어레이를 비교할 때 최상의 경우 O(n)와 최악의 경우 O(n^2)의 TimeComplexity가 있을 것이다.

최상의 경우와 최악의 경우 O(n)와 함께 작동하는 대안(그러나 불행히도 더 복잡한) 해결책은 다음과 같다.

# 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

예)

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

참조URL: https://stackoverflow.com/questions/6486450/compute-list-difference