[OK]を

Question

は、私は二つのリストがあります：

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

基本的には考えている：私は、このような方法でそれらを比較

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

をので、私は次の出力を得ます各リストを通って比較してください。彼らが共通の要素を持っている場合、その要素を削除します。しかし、その要素のうちの1つだけがそのすべてではありません。彼らが共通の要素を持っていない場合、それを残す。 2つの同一のリストは、x = []、y = []

となります。私は他の人がこれを行うためにより良い、そして/またはもっと無愛想な方法を勧めてくれることを望んでいます。 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}) 

の場合

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

Answer 2

かなり厄介な：P

あなたは多重度のリストに戻って Counterオブジェクトを変換したい、あなたは elementsメソッドを使用することができます

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：オリジナルとgnibblerは、リストの長さが約35以上で、gnibbler（とCounter）の方が速い場合は同じです。

Answer 5

あなたは1行でそれを行うには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

だけを使用してので、私は、これは範囲（またはxrangeの）よりも優れている見つけるの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] 

を動作する数回の繰り返しが大きな

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