python - 2 つの非常に大きなリストの違いを見つける

Question

2 つの非常に大きなリストがあります。1 つは 331991 要素の長さで、1 つは a と呼び、もう 1 つは 99171 要素の長さで、b と呼びます。a と b を比較して、b にない a の要素のリストを返したいとします。これも可能な限り効率的である必要があり、それらが表示される順序で、それはおそらく当然のことですが、そこに入れてもいいと思いました。

Answer 1

O(m + n) 時間で実行できます。ここで、m と n は 2 つのリストの長さに対応します。

exclude = set(b)  # O(m)

new_list = [x for x in a if x not in exclude]  # O(n)

ここで重要なのは、セットには一定時間の封じ込めテストがあるということです。おそらく、最初からセットであると考えることができますb。

参照:リスト内包表記

---

あなたの例を使用して：

>>> a = ['a','b','c','d','e']
>>> b = ['a','b','c','f','g']
>>> 
>>> exclude = set(b)
>>> new_list = [x for x in a if x not in exclude]
>>> 
>>> new_list
['d', 'e']