読者です 読者をやめる 読者になる 読者になる

破棄されたブログ

このブログは破棄されました。

Python におけるリストの引き算色々

例によって StackOverflow からのネタ。

リストの引き算とは

あるリストから、別のリストに含まれない要素を削除する

擬似コード

# pseudocode
x = [1, 2, 3, 4, 5]
y = [2, 4]

assert (x - y) == [1, 3, 5]

フィルターによるアプローチ

定義をそのまま受け取った純粋なアプローチ。 ただし、listin 演算子を使う際 (item in l) の平均計算量は、O(n) となる。場合によっては、効率が悪いかもしれない。

x = [1, 2, 3, 4, 5]
y = [2, 4]

assert [item for item in x if item not in y] == [1, 3, 5]

set を使うアプローチ

set は、引き算ができるので、一度 set に変換してから list に戻すアプローチ。 setin 演算子の平均計算量は O(1) なので、単純にフィルターするよりも効率がいいかもしれない。 ただし、 set は、重複要素を削除し、また順序を持たない。その点が問題となりうる。

# This works
x = [1, 2, 3, 4, 5]
y = [2, 4]

assert list(set(x) - set(y)) == [1, 3, 5]


# This not work
x = [5, 2, 3, 1, 4, 3]
y = [2, 4]

assert list(set(x) - set(y)) == [1, 3, 5] # invalid
assert list(set(x) - set(y)) != [5, 3, 1, 3] # expected

set とフィルターを組み合わせたアプローチ

x - yy 側のみを set にするアプローチ。 そもそも、 set の減算 sx - sy の計算量は O(len(sx)) なので、両方を set にしてしまうメリットはないのかもしない。 また、 x 側を set にしないため、重複要素が削除されたり、順序が崩れることもない。

# This works
x = [1, 2, 3, 4, 5]
y = [2, 4]

sy = set(y)
assert [item for item in x if item not in sy] == [1, 3, 5]

# This also works
x = [5, 2, 3, 1, 4, 3]
y = [2, 4]

sy = set(y)
assert [item for item in x if item not in sy] == [5, 3, 1, 3]

元ネタと参考資料

広告を非表示にする