2つのリストの違いを計算する方法を探している間に、別のユーザーの質問を読みました。なぜリスト比較にセットを使用するのですか？
Python, compute list difference
私の質問は、なぜ私は
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
編集を行うことをするだろうされています。ちょうど二差分機能は、実際の類似点を返さ気づきました。今は正しいはずです。
アルゴリズムの観点からすれば、セットを構成するにはO(n)、要素がセットに含まれているかどうかをテストするのはO(1)であるため、リストの理解を行うにはO(n)が必要です。しかし、2番目の例では、両方のリストをループするにはO(n^2)が必要です。したがって、プログラミング言語に関係なく、最初のアプローチは優れています。
また、Pythonでのリストの補完は、forループよりも本質的に高速です。これにより、定数係数はさらに大きく（かなり大きく）減少します。私はここに引用this postにまとめることができる理由：
リストの内包表記のみ 式、ではない文で構成することができるという事実は、かなりの要因である、などはるかに少ない 作業は舞台裏で必要とされます各反復ごとに。もう1つの要因 は、リスト内包の根底にある反復メカニズムが、forループの実行よりもCループに非常に近い であるということです。
このセットを使用すると、通常、bを1回だけ反復する必要があるため、のすべての要素に対して1回ずつbを反復する必要があります。
2つのオプションの主な違いは、setを使用するものが漸近的にはるかに効率的であることです。
合理的に有利な条件の下では、セット内のアイテムを探すことは、O(1)時に行うことができます。リスト内のアイテムを検索するには、O(n)時間が必要です。
2番目の重要性の低い違いは、一方のバージョンがリスト内包を使用し、他方がforループを使用することです。リスト内包表記は、よりコンパクトなコードを生成する傾向があります。また、パフォーマンスが懸念される場合は、正確な画像を取得する唯一の方法は、ベンチマークを実行することです。
私はいくつかのテストを行ってきた：
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)))
後者がなぜO（n^2）であるかの良い説明。また、リストの解説とループのアプローチ（リストの解説は私の例では約2倍速い）で行ったいくつかの 'timeit'タイミングを以下に示します：https://gist.github.com/2647005 –
wow ...それはいくつかです怒っている証拠。私は確かに最初のものを実装しています。 – Jake