Last Updated: 2/6/2024, 5:44:57 AM

# 6.1. リストの差分

try 文が速い。

ここではリストの差分を取る関数 subtract_list について考えてみたいと思います。リストの差分を取るとは、以下のような動作をする関数です。

subtract_list([0, 1, 2], [0, 1, 2])
# []

subtract_list([0, 1, 2], [0])
# [1, 2]

subtract_list([0, 1, 2], [0, 1])
# [2]

subtract_list([0], [0, 1, 2])
# []  引かれる要素が無くても Error にはならない

subtract_list([0, 0, 1, 1, 2, 2], [0, 1, 2])
# [0, 1, 2]  重複にも対応する

この記事は以下の記事と関連しています。特に読んでいただかなくても大丈夫です。

Python でリストを比較する

# 6.1.1. 比較対象

さて、ここで問題です。以下３つの関数は、リストの差分を求める同じ動作をします。この中で最も速い関数はどれでしょうか？

# for_if_del
def subtract_list_for_if_del(lst1, lst2):
    lst = lst1.copy()
    for e2 in lst2:
        for i, e1 in enumerate(lst):
            if e1 == e2:
                del lst[i]
                break
    return lst

# if_remove
def subtract_list_if_remove(lst1, lst2):
    lst = lst1.copy()
    for e2 in lst2:
        if e2 in lst:
            lst.remove(e2)
    return lst

# try_remove
def subtract_list_try_remove(lst1, lst2):
    lst = lst1.copy()
    for e2 in lst2:
        try:
            lst.remove(e2)
        except ValueError:
            continue
    return lst

# 6.1.2. 測定結果

最も速いのは subtract_list_try_remove です。測定結果は、以下の通りです。関連記事から来られた方は、なにやってるんだコイツ？って感じだと思います。詳細は無視していただいて、雰囲気だけ伝わればと思います。また subtract_list_while_if_pop については、無視してください。

git clone https://github.com/niconico25/comparison_of_python_code/
cd comparison_of_python_code
python3 6_1_subtract_list.py

$ python3 6_1_subtract_list.py 

# Case 0
# ([i for i in range(0, 1000)], [i for i in range(0, 1000)])
subtract_list_try_remove                 :   0.2473 [msec]
subtract_list_if_remove                  :   0.2616 [msec]
subtract_list_for_if_del                 :   0.5584 [msec]
subtract_list_while_if_pop               :   0.4129 [msec]

# Case 1
# ([i for i in range(0, 1000)], [i for i in range(999, -1, -1)])
subtract_list_try_remove                 :   9.1577 [msec]
subtract_list_if_remove                  :  18.1051 [msec]
subtract_list_for_if_del                 :  34.6071 [msec]
subtract_list_while_if_pop               :  80.4362 [msec]

# Case 2
# ([i for i in range(0, 1000)], [i for i in range(1000, 2000)])
subtract_list_try_remove                 :  19.6872 [msec]
subtract_list_if_remove                  :  17.7516 [msec]
subtract_list_for_if_del                 :  72.0139 [msec]
subtract_list_while_if_pop               : 158.1244 [msec]

# Case 3
# ([random.randint(0, 1000) for _ in range(1000)],[random.randint(0, 1000) for _ in range(1000, 2000)])
subtract_list_try_remove                 :   9.9173 [msec]
subtract_list_if_remove                  :  12.6358 [msec]
subtract_list_for_if_del                 :  35.6174 [msec]
subtract_list_while_if_pop               :  84.6340 [msec]

# 6.1.3. なんで for_if_del より if_remove が速いの？

順を追って見ていきたいと思います。 subtract_list_for_if_del は、一番わかりやすい書き方だと思います。

def subtract_list_for_if_del(lst1, lst2):
    lst = lst1.copy()
    for e2 in lst2:
        for i, e1 in enumerate(lst):
            if e1 == e2:
                del lst[i]
                break
    return lst

なぜなら list.remove なんてメソッドはそうは滅多に使わないメソッドだからです。いきなり見せつけられると、なんだこれ？みたいな気持ちになるわけです。

def subtract_list_if_remove(lst1, lst2):
    lst = lst1.copy()
    for e2 in lst2:
        if e2 in lst:
            lst.remove(e2)
    return lst

しかもなんで if e2 in lst なんてしてるんだ？ってことになります。これは e2 が lst の中になかった時に lst.remove(e2) が ValueError を投げ返してくるので、それを避けるためにしています。

lst = [0, 1, 2, 3]
lst.remove(4)

>>> lst = [0, 1, 2, 3]
>>> lst.remove(4)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: list.remove(x): x not in list
>>>

本題ですが、なぜ subtract_list_if_remove の方が速いのでしょうか？それは list.remove メソッドが C 言語で実装されているからです。 Python は遅い言語です。 C 言語で書かれたコードがあるなら、自分で Python では書かずに、 C 言語で書かれたコードを使った方が速いのです。

list.remove メソッドの中身については以下の記事で解説させていただきました。

CPython のコードを覗いてみた - Python の list.remove メソッド (opens new window)

# 6.1.4. なんで if_del より try_del が速いの？

if e2 in lst: と書いた時に、リストをぐるっと回って、要素が有るか、無いか探しているから。

list.remove メソッドは要素がなかった場合、 ValueError という例外を投げてきます。投げられたら処理が中断してしまうので、なんとかしないといけません。

この時の考え方として、例外が起こるか判定してから実行する方法と if 、とりあえずやって見て例外が起こってから対処する方法 try の２つが考えられます。

まったく覚える必要はありませんが、考え方として２つの用語をご紹介させていただきます。

if 文を使った書き方は LBYL と呼ばれるアプローチです。

LBYL (opens new window)
「ころばぬ先の杖 (look before you leap)」の略です。このコーディングスタイルでは、呼び出しや検索を行う前に、明示的に前提条件 (pre-condition) 判定を行います。 EAFP アプローチと対照的で、 if 文がたくさん使われるのが特徴的です。

try 文を使った書き方は EAFP と呼ばれるアプローチです。

EAFP (opens new window)
あるオブジェクトが正しいインタフェースを持っているかを決定するのにオブジェクトの型を見ないプログラミングスタイルです。代わりに、単純にオブジェクトのメソッドや属性が呼ばれたり使われたりします（とりあえず単純に呼び出して失敗したら try 文で捕まえる）。

ここでのポイントは２つあります。まず第一に try 文は例外が発生すると遅くなるけど、発生しなければ遅くならないということ。また第二に e2 in lst はリストを１度、線形探索 (opens new window) してしまっているということ。

第一の要因と第二の要因、どちらが重いのかと言えば、上記の測定結果を見ると大抵の場合 e2 in lst の線形探索の方が重いことがわかります。

ただし Case 2 のようにほとんど例外が発生しない場合は、 if 文の方が速くなります。

# 6.1.5. LBYL と EAFP

Python では EAFP で書くことが多い気がします。

なぜなら C 言語で実行して、失敗したら Python で処理させた方が速いからです。例えば dict も基本的には EAFP なアプローチです。

d = {'a': 0}
c = d['b']  # KeyError  <--- None では無く例外を投げる

また None を返されると変数に代入される型が変わってしまいます。変数 c に代入されるオブジェクトの型が type(None) と int の２種類になってしまうのです。

d = {'a': 0}
c = d.get('b')

これは地味なようで色々と問題を引き起こします。それについては本記事の末尾に添付したリンク先の記事「例外ってなに？」の中でご紹介させていただきます。

とは言え try 文なんてあまり使わないので、見せられると、結構圧迫感があります。 Python は可読性を重視して設計された言語です。 try 文を使った書き方が、果たして許されるのでしょうか？

def subtract_list_try_remove(lst1, lst2):
    lst = lst1.copy()
    for e2 in lst2:
        try:
            lst.remove(e2)
        except ValueError:
            continue
    return lst

この場合は try 文を無理して使わなくてもいいかなと思います。なぜなら Python はもともと遅い言語なので、無理して速度を求めてもあまり得られるものは無いからです。お前、いま更それいうのかよという感じですが...

特に、あまり使われない汎用的でない処理の場合は、可読性を損なってまで try 文を使うのは個人的に望ましく無いと思います。なぜなら Python は書き方を頑張っても遅いからです。

可読性が良くなる場合は、積極的に try 文を使うべきだと思います。言語は違いますが、以下の記事のコードを見ると、なんと無く雰囲気が伝わるかなと思います。

もう少し例外を使用しても良いのではないか... - Qiita (opens new window)

どのような場合に try 文で包み、例外を投げるべきなのかについて、もう少し詳しく以下の記事で記述させていただきました。

try 文ってなに？

型が異る値を受けるときに使います。

← 5. for 文かリスト内包表記か 6.2. 例外か関数か →