7.1. リストの差分

try 文が速い。

とりあえず、ここではリストを比較する処理を try-remove, while-remove, for-if, while-if の4つで比較しました。 list を比較する処理は try-except を使ったものが最も速かったです。

7.1.1. 比較対象

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


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


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


def subtract_list_while_if_pop(lst1, lst2):
    lst = lst1.copy()
    lst.reverse()
    lst_c = []
    lst_pop = lst.pop
    lst_c_append = lst_c.append
    for e2 in lst2:
        while lst:
            e1 = lst_pop()
            if e1 == e2:
                break
            else:
                lst_c_append(e1)
        lst_c.reverse()
        lst.extend(lst_c)
        lst_c.clear()
    lst.reverse()
    return lst

7.1.2. 測定結果

実行結果は、以下の通りです。

$ python 7_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]

7.1.3. なんで remove は速いの?

答え: list.remove は C で実装されているから。

リストの走査→比較→削除の一貫した操作を C で実行して速くしてるような感じです。 反対に for や while を使ってしまうと、比較するために Python 側に取り出すことになり、操作が重くなります。

もちろん要素が存在しないと例外発生してしまいますが、 感覚的には if 文内で行われる条件判定のための型推論を伴う四則演算が例のごとく重くて、 例外が、ちょっとやそっと発生したくらいでは問題にならないような感じかなと思っています。

簡単に言えば、最初から提供されている神々が書いてくれた組み込みの関数を使った方が速いということですね。 なるべく自分で Python のコードを書かずに CPython に処理をしてもらうようにするようなイメージです。

7.1.4. C 言語で書かれたライブラリと
Python で書かれたライブラリ

上記のリストを比較するコードで C で組まれた remove を活用したように C で組まれたライブラリを活用すると速いです。

itertools などの C で書かれたモジュールは速い 感じがします

copy などの Python で書かれたモジュールは遅い 感じがします。 ただ、遅いとは言えども自分で組むよりは、ほぼ速いかなと思います。

同じ機能を提供しているものがないので 両者を単純に比較することはできませんが...

また、同じモジュールであっても Python 側で実装されていたり、
C 側実装されていたりするそうです。

collections.OrderedDict は Python 側で実装された型であるのに対して、 同じモジュールにある collections.defaultdict は C 言語側で実装されている型です。 このことは実際に PyPy で相当数の問題を引き起こしています。これらの違いが目立たない類似の API を実現するため、 できるだけオリジナルの型を模倣する必要があるからです。
Revenge of the Types: 型の復讐

7.1.5. なんで try remove の方が if remove より速いの?

Python で書くよりも C 言語で書かれたコードに処理を任せた方が速いです。 if remove は多くの処理を Python のコードで書いてしまっています。

ただし「例外」は重たい処理です。「例外」が発生しなければ、問題はありません。 しかし、「例外」が発生してしまうと重たくなってしまいます。

そのため Case 2 のように全てのケースで例外が発生しまうようなものについては if remove の方が速くなります。