尋找更Python列表進行比較，解決

Question

好了，所以我有兩個列表：

x = [1, 2, 3, 4] 
y = [1, 1, 2, 5, 6] 

我以這樣的方式對它們進行比較，所以我得到了以下的輸出：

x = [3, 4] 
y = [1, 5, 6] 

基本是思路瀏覽每個列表並進行比較。如果他們有一個共同的元素刪除該元素。但只有其中一個元素不是全部。如果他們沒有一個共同的假期它。兩個相同的列表將變爲x = []，y = []

這是我相當黑客和相當跛腳的解決方案。我希望其他人可以推薦一個更好和/或更pythonic這樣做的方式。 3循環似乎過度...

done = True 

    while not done: 
     done = False 
     for x in xlist: 
      for y in ylist: 
       if x == y: 
        xlist.remove(x) 
        ylist.remove(y) 
        done = False 
     print xlist, ylist 

感謝一直花時間來閱讀這個問題。 XOXO

Answer 1

這有可能是你正在尋找的數據結構是multiset（或「袋」），如果是這樣，來實現它在Python的好方法是使用collections.Counter：

>>> from collections import Counter 
>>> x = Counter([1, 2, 3, 4]) 
>>> y = Counter([1, 1, 2, 5, 6]) 
>>> x - y 
Counter({3: 1, 4: 1}) 
>>> y - x 
Counter({1: 1, 5: 1, 6: 1}) 

如果要在Counter對象轉換回了多重性列表，你可以使用elements方法：

>>> list((x - y).elements()) 
[3, 4] 
>>> list((y - x).elements()) 
[1, 5, 6] 

Answer 2

很討厭：P

a = sum(([i]*(x.count(i)-y.count(i)) for i in set(x)),[]) 
b = sum(([i]*(y.count(i)-x.count(i)) for i in set(y)),[]) 

x,y = a,b 

Answer 3

如果你不計較重複這很簡單：

>>> x=[1,2,3,4] 
>>> y=[1,1,2,5,6] 
>>> list(set(x).difference(set(y))) 
[3, 4] 
>>> list(set(y).difference(set(x))) 
[5, 6] 

Answer 4

要建立在加雷思的答案：

>>> a = Counter([1, 2, 3, 4]) 
>>> b = Counter([1, 1, 2, 5, 6]) 
>>> (a - b).elements() 
[3, 4] 
>>> (b - a).elements() 
[1, 5, 6] 

基準代碼：

from collections import Counter 
from collections import defaultdict 
import random 

# short lists 
#a = [1, 2, 3, 4, 7, 8, 9] 
#b = [1, 1, 2, 5, 6, 8, 8, 10] 

# long lists 
a = [] 
b = [] 

for i in range(0, 1000): 
    q = random.choice((1, 2, 3, 4)) 
    if q == 1: 
     a.append(i) 
    elif q == 2: 
     b.append(i) 
    elif q == 3: 
     a.append(i) 
     b.append(i) 
    else: 
     a.append(i) 
     b.append(i) 
     b.append(i) 

# Modifies the lists in-place! Naughty! And it doesn't actually work, to boot. 
def original(xlist, ylist): 
    done = False 

    while not done: 
     done = True 
     for x in xlist: 
      for y in ylist: 
       if x == y: 
        xlist.remove(x) 
        ylist.remove(y) 
        done = False 
    return xlist, ylist # not strictly necessary, see above 


def counter(xlist, ylist): 
    x = Counter(xlist) 
    y = Counter(ylist) 
    return ((x-y).elements(), (y-x).elements()) 


def nasty(xlist, ylist): 
    x = sum(([i]*(xlist.count(i)-ylist.count(i)) for i in set(xlist)),[]) 
    y = sum(([i]*(ylist.count(i)-xlist.count(i)) for i in set(ylist)),[]) 

    return x, y 


def gnibbler(xlist, ylist): 
    d = defaultdict(int) 
    for i in xlist: d[i] += 1 
    for i in ylist: d[i] -= 1 
    return [k for k,v in d.items() for i in range(v)], [k for k,v in d.items() for i in range(-v)] 

# substitute algorithm to test in the call 
for x in range(0, 100000): 
    original(list(a), list(b)) 

運行不夠嚴格，基準[tm]（短名單是原始名單，長名單是大約隨機生成的名單長期在原算法的乘數給比賽和重複，時間的混合）1000個條目：

100K iterations, short lists 1K iterations, long lists 
Original  1.0       1.0 
Counter  9.3       0.06 
Nasty  2.9       1.4 
Gnibbler  2.4       0.02 

注1：計數器對象的創建似乎掩蓋在小尺寸列表的實際算法。注2：在列表長度大約爲35時，原始和gnibbler是相同的，高於gnibbler（和Counter）的速度更快。

Answer 5

如果你不關心順序，使用collections.Counter做一個行：

>>> Counter(x)-Counter(y) 
Counter({3: 1, 4: 1}) 

>>> Counter(y)-Counter(x) 
Counter({1: 1, 5: 1, 6: 1}) 

如果你關心順序，你也許可以通過你的名單抓住從上面的字典元素迭代：

def prune(seq, toPrune): 
    """Prunes elements from front of seq in O(N) time""" 
    remainder = Counter(seq)-Counter(toPrune) 
    R = [] 
    for x in reversed(seq): 
     if remainder.get(x): 
      remainder[x] -= 1 
      R.insert(0,x) 
    return R 

演示：

>>> prune(x,y) 
[3, 4] 
>>> prune(y,x) 
[1, 1, 5, 6] 

Answer 6

只需使用collections.defaultdict所以將工作的python2.5上+

>>> x = [1, 2, 3, 4] 
>>> y = [1, 1, 2, 5, 6] 
>>> from collections import defaultdict 
>>> d = defaultdict(int) 
>>> for i in x: 
... d[i] += 1 
... 
>>> for i in y: 
... d[i] -= 1 
... 
>>> [k for k,v in d.items() for i in range(v)] 
[3, 4] 
>>> [k for k,v in d.items() for i in range(-v)] 
[1, 5, 6] 

，我覺得這是比範圍（或x範圍）更好，如果重複次數得到大

>>> from itertools import repeat 
>>> [k for k,v in d.items() for i in repeat(None, v)]