Python のリスト操作は collections.deque が速い

こんにちは。吉田弁二郎です。

先日タスクスケジューラを Python で実装することがあり、深さ優先探索の方針で作業を進める必要がありました。その際、リストの先頭からデータを取り出し先頭にデータを入れる、ということをやったのですが、デフォルトの list ではなく collections.deque を使うと遥かに効率的に動作することを知ったので共有したいと思います（かなり旧聞にあたる内容ですが、ご容赦ください）。

今回確認したのは下記のコード。

from collections import deque

# list
def check_list(n):
    l = list(range(n))
    for _ in range(10000):
        l.pop(0)
        l.insert(0, 0)

# deque (extendleft)
def check_deque(n):
    l = deque(list(range(n)))
    for _ in range(10000):
        l.popleft()
        l.extendleft([0])

# deque (appendleft)
def check_deque(n):
    l = deque(list(range(n)))
    for _ in range(10000):
        l.popleft()
        l.appendleft(0)

ある長さ n のリストもしくは deque を生成した後、10万回先頭要素を取り出し挿入することを繰り返します。今回 deque に関しては extendleft と appendleft を試しました。所要時間の計測には ipython の %timeit マジックを使っています。

結果はこちらの通り。横軸はリスト / deque 長 n を対数表示したもの、縦軸は ms 単位の所要時間です。

青いラインが通常のリストに対する結果です。配列長が長くなるほど、deque が圧倒的に効率よく処理できていることがわかりますね。extendleft と appendleft に関しては、後者の方が2倍ほど速かったです（そもそも用途が違うので比較するものでもないかもしれないですが）。

なお、deque は python2 でも python3 でも利用可能です。また、今回は先頭要素に対して操作を行いましたが、末尾要素に対しての操作については違う結果が出ると思います。

Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

8.3. collections — High-performance container datatypes — Python 2.7.13 documentation

動作環境

• MacOS 10.11.6
• Python 2.7.13
• Processor 1.1 GHz Intel Core m3
• Memory 8 GB 1867 MHz LPDDR3
• IPython 5.1.0