【Python】組込み型のlistとdequeで実行時間に差が出るケース

※誤った記載ありましたら是非マサカリください（編集リクエストでもぜひ）。

list 型と deque 型

Python の組込み型である list 型と deque 型の挙動を見ていく。

以下は一定長のリストおよびキューを生成し、その要素をで取り出していくコード。
順に1万件、10万件、100万件の長さで実行する。

import time
from collections import deque


for count in [10000, 100000, 1000000]:
    # オブジェクトの初期化
    l = ['a'] * count
    q = deque(l)

    # list 型の操作
    time1 = time.time()
    while len(l) > 0:
        l.pop(0)

    # deque 型 の操作
    time2 = time.time()
    while len(q) > 0:
        q.popleft()
    time3 = time.time()

    print('count:', count)
    print(f'list  finished: {time2 - time1} sec.')
    print(f'deque finished: {time3 - time2} sec.')
    print()

なお 第1要素と末尾要素を取り出す操作は list 型と deque 型でそれぞれ以下の関数。

from collections import deque

# 初期化
l = [1, 2, 3]
q = deque(l)

# 第1要素を取り出す操作
l.pop(0)  # => 1
d.popleft()  # => 1

# 末尾要素を取り出す操作
l.pop(-1)  # => 3
d.pop()  # => 3

実行結果

手元の実行環境では以下の結果となった。

count: 10000
list  finished: 0.006018161773681641 sec.
deque finished: 0.0003972053527832031 sec.

count: 100000
list  finished: 0.9306132793426514 sec.
deque finished: 0.003919839859008789 sec.

count: 1000000
list  finished: 133.8608682155609 sec.
deque finished: 0.04343390464782715 sec.

件数が100万件のケースでは list 型の操作は2分以上かかった。

なぜこうなるのか

公式ドキュメントから該当部分を引用する。
deque オブジェクトに対して append や pop といった操作が可能だが、list オブジェクトのそれらとはどういった違いがあるのか言及されている。

list オブジェクトでも同様の操作を実現できますが、これは高速な固定長の操作に特化されており、内部のデータ表現形式のサイズと位置を両方変えるような pop(0) や insert(0, v) などの操作ではメモリ移動のために O(n) のコストを必要とします。

これに対して deque オブジェクトでは O(1) の計算コストで済んでいるとのこと。

まとめ

データ長が頻繁に変化するデータ構造としてリストは不向き。

ちなみに データの取り出しを先頭要素（list.pop(0)）ではなく末尾要素に対して行うコード（list.pop(-1)）は以下。
この場合は リストの長さに拠らない O(1) の処理時間で済むため、実行時間の差はほとんど生じない。

※上記との差分箇所に # here を記載

import time
from collections import deque


for count in [10000, 100000, 1000000]:
    # オブジェクトの初期化
    l = ['a'] * count
    q = deque(l)

    # list 型の操作
    time1 = time.time()
    while len(l) > 0:
        l.pop(-1)  # here1

    # deque 型 の操作
    time2 = time.time()
    while len(q) > 0:
        q.pop()  # here2
    time3 = time.time()

    print('count:', count)
    print(f'list  finished: {time2 - time1} sec.')
    print(f'deque finished: {time3 - time2} sec.')
    print()

↓実行結果

count: 10000
list  finished: 0.0006232261657714844 sec.
deque finished: 0.0005576610565185547 sec.

count: 100000
list  finished: 0.005739688873291016 sec.
deque finished: 0.004764080047607422 sec.

count: 1000000
list  finished: 0.05780482292175293 sec.
deque finished: 0.05013251304626465 sec.