7

2 つのリストの違いを計算する方法を探しているときに、別のユーザーの質問を読みました。

Python、リストの差を計算

私の質問は、なぜ私はそうするのですか

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

編集: 2 番目の diff 関数が実際に類似点を返したことに気付きました。今は正しいはずです。

4

5 に答える 5

8

アルゴリズムの観点から言えばO(n)、セットを構築O(n)し、リストの理解を行う必要があります (要素がセットに含まれているかどうかのテストは であるためO(1))。ただし、2 番目の例では、O(n^2)両方のリストをループする必要があります。したがって、プログラミング言語に関係なく、最初のアプローチが優れています。

また、Python のリスト内包表記は、本質的に for ループよりも高速です。これにより、定数係数がさらに削減されます (大幅に削減されます)。その理由は、ここで引用するこの投稿に要約できます。

リスト内包表記はステートメントではなく式のみで構成できるという事実は、各反復の舞台裏で必要な作業がはるかに少ないため、かなりの要因です。もう 1 つの要因は、リスト内包表記の基礎となる反復メカニズムが、for ループの実行よりも C ループにはるかに近いことです。

于 2012-05-09T17:20:30.910 に答える
5

2 つのオプションの主な違いは、 を使用するset方が漸近的にはるかに効率的であるということです。

適度に有利な条件の下では、セット内のアイテムの検索はO(1)時間内に実行できます。リスト内の項目を検索するにはO(n)時間がかかります。

2 つ目の重要ではない違いは、一方のバージョンではリスト内包表記を使用し、もう一方のバージョンではforループを使用することです。リスト内包表記は、よりコンパクトなコードを生成する傾向があります。また、より効率的である傾向があります (ただし、パフォーマンスが懸念される場合、正確な全体像を把握する唯一の方法はベンチマークを実行することです)。

于 2012-05-09T17:19:50.240 に答える
2

私はいくつかのテストを行いました：

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-10T11:21:53.177 に答える
2

リストを作成するとき、リスト内包表記は通常のリスト操作を使用するよりも効率的であると一般に見なされています。メモリが問題になる場合は、代わりにジェネレーターを使用することをお勧めします。

これforにより、 -loopsmapおよびのパフォーマンスに関する情報が少し提供されますlist comprehension。@benhoyt は、ループとリストの理解を比較する便利なリンクも提供しました。

ただし、パフォーマンスが特定の懸念事項である場合は、特定の要件に最適なオプションを選択するために、さまざまなオプションの時間を測定/ベンチマークすることをお勧めします。

于 2012-05-09T17:17:46.200 に答える
2

セットを使用すると、1回だけ反復する必要があるため、通常は高速になりbますが、例ではbの各要素に対して1回反復する必要がありますa。

于 2012-05-09T17:19:25.013 に答える