爲什麼使用一組進行列表比較？

我剛剛閱讀另一個用戶問題，同時尋找一種方法來計算兩個列表中的差異。爲什麼使用一組進行列表比較？

我的問題是，爲什麼我會做

def diff(a,b): 
    b = set(b) 
    return [aa for aa in a if aa not in b]

，而不是做

def diff(a,b): 
    tmp = [] 
    for i in a: 
     if(i not in b): 
      tmp.append(i) 
return tmp

編輯：剛纔注意到第二DIFF函數實際上返回的相似之處。現在應該是正確的。

來源

2012-05-09 Jake

剛剛從算法的角度來看，它需要O(n)構建集和O(n)做列表理解（因爲測試如果一個元素包含在一組是O(1)）。然而在第二個例子中，需要O(n^2)循環兩個列表。所以不管編程語言如何，第一種方法都是優越的。

此外，python中的列表解析本質上比for循環更快。這更多地降低了常數因素（並且也是如此）。之所以能在this post總結，我在這裏引用：

該列表內涵只能由表達，而不是陳述的事實，是一個相當大的因素，儘可能少工作需要做幕後爲每個迭代。的另一個因素是列表解析的基本迭代機制是比執行for循環更接近C循環。

來源

2012-05-09 17:20:30 tskuzzy

爲什麼後者是O（n^2）的好解釋。另外，下面是列表理解vs循環方法的一些'timeit'時間表（列表解析速度大約是我的示例中的兩倍）：https：//gist.github.com/2647005 –

哇......這是一些打亂證據。我確實實施了第一個。 – Jake

在創建列表時，列表理解通常被認爲比使用常規列表操作更高效。如果內存是一個問題，您可能需要使用生成器。

This提供for -loops，map和list comprehension的一些信息重新性能。 @benhoyt還提供了一個有用的link比較循環與列表理解。

但是請注意，如果性能是一個特定的問題，那麼可能需要您花時間/基準測試您的各種選項，以根據您的特定要求選擇最佳選項。

來源

2012-05-09 17:17:46 Levon

快多少是在這種情況下列表理解？ – Gabe

列表理解可能會比使用append創建列表稍快*但速度並不快。如果'container'是一個列表，那麼在這裏設置列表的真正收益是'容器中的elem'是O（len（容器）），但是如果'container'是一個集合，則O（1）。 –

@Gabe我添加了一個鏈接到我的文章，談論的for循環vs地圖vs列表解析可能有幫助。 – Levon

使用該集合通常會更快，因爲它只需重複執行b一次，而您的示例必須對a中的每個元素重複執行b一次。

來源

2012-05-09 17:19:25 Gabe

這兩個選項之間的主要區別在於，使用set的方法漸近效率更高。

在合理有利的條件下，查找一套中的物品可以在O(1)時間內完成;查找列表中的項目需要O(n)時間。

第二個不太顯着的區別是一個版本使用列表理解而另一個版本使用for循環。列表理解傾向於產生更緊湊的代碼。他們也往往更有效率（如果性能是一個問題，獲得準確圖片的唯一方法是運行基準測試）。

來源

2012-05-09 17:19:50 NPE

我已經做了一些測試：

test_lists.py

a = range(1, 1000) 
b = range(2, 1002) 

tmp = [] 
for i in a: 
    if(i not in b): 
     tmp.append(i)

test_set_list_comprehensions.py

a = range(1, 1000) 
b = range(2, 1002) 

b = set(b) 
[aa for aa in a if aa not in b]

test_set.py

a = range(1, 1000) 
b = range(2, 1002) 
list(set(a).difference(set(b)))

而這正是timeit說：

~$ python -m timeit 'import test_lists' 
1000000 loops, best of 3: 0.671 usec per loop 
~$ python -m timeit 'import test_set_list_comprehension' 
1000000 loops, best of 3: 0.766 usec per loop 
~$ python -m timeit 'import test_set' 
1000000 loops, best of 3: 0.656 usec per loop

所以最好的似乎是：

test_set.py

a = range(1, 1000) 
b = range(2, 1002) 
list(set(a).difference(set(b)))

來源

2012-05-10 11:21:53 raulcumplido

爲什麼使用一組進行列表比較？

回答

相關問題