Pythonでキューを list, deque で実装したときの速度比較

Pythonでキューを実装

キューを実装したときパフォーマンスを比較するため、次の5パターンを用意した

1. dequeを使ってpopleft→append
2. dequeを使ってappend→popleft
3. dequeを使ってmaxlen指定でappend
4. listでpop→append
5. listでappend→pop

コード

import timeit
from collections import deque

import matplotlib.pyplot as plt
import numpy as np

LIST_LEN = 10**8
APPEND_REP = 10**6
LOOP = 15

def que_test1(list_len=LIST_LEN, append_rep=APPEND_REP):
    que = deque([.0]*list_len)
    for i in range(append_rep-1):
        que.popleft()
        que.append(i)

def que_test2(list_len=LIST_LEN, append_rep=APPEND_REP):
    que = deque([.0]*list_len)
    for i in range(append_rep-1):
        que.append(i)
        que.popleft()

def que_test3(list_len=LIST_LEN, append_rep=APPEND_REP):
    que = deque([.0]*list_len, maxlen=list_len)
    for i in range(append_rep-1):
        que.append(i)

def lst_test1(list_len=LIST_LEN, append_rep=APPEND_REP):
    lst = [.0]*list_len
    for i in range(append_rep-1):
        lst.pop(0)
        lst.append(i)

def lst_test2(list_len=LIST_LEN, append_rep=APPEND_REP):
    lst = [.0]*list_len
    for i in range(append_rep-1):
        lst.append(i)
        lst.pop(0)

条件

キューの長さとアペンドの回数を $10^0$ - $10^5$ で条件を振って計算した

コード

r_list = list(range(0, 6))
l_list = list(range(0, 6))
funcs = [que_test1, que_test2, que_test3, lst_test1, lst_test2]

time_arr = np.zeros((len(r_list), len(l_list), len(funcs)))

for i, r in enumerate(r_list):
    def get_time(f, list_len, append_rep):
        return timeit.timeit(lambda: f(list_len, append_rep), number=LOOP)/LOOP

    for k, func in enumerate(funcs):
        for j, l in enumerate(l_list):
            print(f"{func.__name__}(append_rep={r}, list_len={l})")
            time_arr[i,j,k] = get_time(f=func, list_len=10**l, append_rep=10**r)

結果

アペンド回数を固定したときの各キュー長でのパフォーマンス

ただしAppend times: 10**0のときアペンド回数は0回（イニシャルだけ）

アペンド回数0回のときはイニシャルコストの関係でdequeが遅い
しかし、アペンド回数が少しでも多いと明確にdequeが速い

キュー長を固定したときの各アペンド回数でのパフォーマンス

先ほどの結果のグラフの描画を変更した図

deque を用いたときが速いがその中でも固定長の場合は maxlen を指定することでより高速
pop と append の順場は deque の場合 apopend を先にしたほうが若干速いようだ

list は直感的には pop を先にしたほうが速いが、誤差もあり定まらなかった

文献

Deque はどちらの側からも append と pop が可能で、スレッドセーフでメモリ効率がよく、どちらの方向からもおよそ O(1) のパフォーマンスで実行できます。
list オブジェクトでも同様の操作を実現できますが、これは高速な固定長の操作に特化されており、基礎のデータ表現形式のサイズと位置を両方変えるような pop(0) や insert(0, v) などの操作ではメモリ移動のために O(n) のコストを必要とします。
https://docs.python.org/ja/3/library/collections.html#collections.deque