Python, разность списков рассылки

В Python, каков наилучший способ вычислить разницу между двумя списками?

пример

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

  • Как изменить цвет фона?
  • Как использовать QTimer внутри QThread, который использует QWaitCondition? (PySide)
  • Вложенные классы python
  • НастройкаWithCopyWarning при создании столбцов
  • Numpy - нарезание 2d строк или столбцов из массива
  • Используя понимание списков в Python, чтобы сделать что-то похожее на zip ()?
  • Параметрическая проверка подлинности
  • Crontab не запускает скрипт python
  • 11 Solutions collect form web for “Python, разность списков рассылки”

    Используйте 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] >>> 
     >>> set([1,2,3,4]) - set([2,5]) set([1, 3, 4]) >>> set([2,5]) - set([1,2,3,4]) set([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. См. Difflib в стандартной библиотеке 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 (по умолчанию, 27 февраля 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()))) 

    Результаты:

     # 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 список понимает функцию def diff (a, b), кажется, быстрее.

    Вы бы хотели использовать set вместо list .

     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 

    Если вы хотите, чтобы разница рекурсивно переходила в элементы вашего списка, я написал пакет для 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 решение поднимается

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

    Когда вы смотрите на TimeComplexity In-operator, в худшем случае он работает с O (n). Даже для наборов.

    Поэтому при сравнении двух массивов мы будем иметь TimeComplexity O (n) в лучшем случае и O (n ^ 2) в худшем случае.

    Альтернативным (но, к сожалению, более сложным) решением, которое работает с 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] 
    Python - лучший язык программирования в мире.