pythonic可迭代的差異

我已經寫了一些代碼來查找所有項目在一個迭代中，而不是另一個，反之亦然。我最初使用的是內置集合差異，但由於每組中有數百萬個項目存儲，所以計算速度相當慢。因爲我知道會有最多幾千元的差異我寫了下面的版本：pythonic可迭代的差異

def differences(a_iter, b_iter): 
    a_items, b_items = set(), set() 

    def remove_or_add_if_none(a_item, b_item, a_set, b_set): 
     if a_item is None: 
      if b_item in a_set: 
       a_set.remove(b_item) 
      else: 
       b_set.add(b) 

    def remove_or_add(a_item, b_item, a_set, b_set): 
     if a in b_set: 
      b_set.remove(a) 
      if b in a_set: 
       a_set.remove(b) 
      else: 
       b_set.add(b) 
      return True 
     return False 

    for a, b in itertools.izip_longest(a_iter, b_iter): 
     if a is None or b is None: 
      remove_or_add_if_none(a, b, a_items, b_items) 
      remove_or_add_if_none(b, a, b_items, a_items) 
      continue 

     if a != b: 
      if remove_or_add(a, b, a_items, b_items) or \ 
       remove_or_add(b, a, b_items, a_items): 
       continue 
      a_items.add(a) 
      b_items.add(b) 

    return a_items, b_items

然而，上面的代碼似乎並不十分Python的，所以我正在尋找替代品或改進建議。

來源

2011-08-14 John

你的速度比內置設置差距快多少？ –

我認爲你的代碼壞了 - 用[1,1]和[1,2]試一下，你會得到1是在一組中，但不是其他的。

> print differences([1,1],[1,2])             
(set([1]), set([2]))

你可以跟蹤這回if a != b測試的效果（這是假設有關訂購的東西是不存在於簡單的設置差異）。

沒有這個測試，這可能會丟棄很多值，我不認爲你的方法會比內置設置更快。這個論點就像這樣：你確實需要在內存中創建一組來保存所有數據（你的bug來自於不這樣做）。一套天真的方法創造了兩套。所以你所能做的最好的是節省一半的時間，而且你還必須用python來完成可能有效的c代碼的工作。

來源

2011-08-14 18:13:08

我原以爲python集合操作會是你可以從標準庫中獲得的最佳性能。

也許這是您選擇的特定實現問題，而不是數據結構和服務人員本身。這是另一個應該給你更好性能的實現。

對於序列較大的序列比較任務，儘可能避免將包含序列的對象放入用於比較的容器中 - 最好使用索引代替。如果序列中的對象是無序的，則對它們進行排序。

因此，舉例來說，我使用NumPy，數值Python庫，對於這些類型的任務：

# a, b are 'fake' index arrays of type boolean 
import numpy as NP 
a, b = NP.random.randint(0, 2, 10), NP.random.randint(0, 2, 10) 
a, b = NP.array(a, dtype=bool), NP.array(b, dtype=bool) 

# items a and b have in common: 
NP.sum(NP.logical_and(a, b)) 

# the converse (the differences) 
NP.sum(NP.logical_or(a, b))

來源

2011-08-14 18:20:06 doug

這裏是一個更Python的解決方案：

a, b = set(a_iter), set(b_iter) 

return a - b, b - a

Python化並不意味着快，但相當優雅和可讀。

下面是可能會更快的解決方案：

a, b = set(a_iter), set(b_iter) 

# Get all the candidate return values 
symdif = a.symmetric_difference(b) 

# Since symdif has much fewer elements, these might be faster 
return symdif - b, symdif - a

現在，關於用Python編寫自定義的「快速」算法，而不是使用內置的操作：這是一個非常糟糕的主意。

集合運算符經過大量優化，用C編寫，通常比Python快得多。你可以在C（或Cython）中編寫算法，但請記住，Python的集合算法是由世界級的天才編寫和優化的。除非你非常擅長優化，否則這可能是不值得的。另一方面，如果您確實能夠大幅提高速度，請分享您的代碼;我敢打賭它有可能進入Python本身。

對於更現實的方法，嘗試消除對Python代碼的調用。例如，如果你的對象有一個自定義的相等運算符，找出一個方法來刪除它。

但是不要期待你的希望。處理數百萬條數據總是需要很長時間。我不知道你在哪裏使用它，但也許最好讓計算機忙一會兒，而不是花時間優化設置算法？

來源

2011-08-14 18:33:12

pythonic可迭代的差異

回答

相關問題