Pythonでの両端キュー（deque）

概要

• listの先頭要素削除の処理（pop(0)）の時間はlistの長さの二乗で増加
  • pop(0)はlistの全要素を1つずつ前にずらすので、要素全体を再代入する必要があるため
• collectionsモジュールのdequeクラスは両端キュー
  • 要素を先頭または末尾に追加、削除するときに定数時間演算で可能
• 先頭要素に対して追加、削除を実施する処理を行う場合はdequeの使用を推奨
• 今回の実装での測定結果（pop処理を先頭要素に100000回実施）

対象	時間
list	2.245
deque	0.111

list

list_example.py

#!/usr/bin/env python3
# -*- coding: utf_8 -*-
"""listの処理時間計測
"""

from cProfile import Profile
from pstats import Stats


def all_pop(array):
    for _ in range(len(array)):
        array.pop(0)


if __name__ == "__main__":
    # プロファイラに渡す用意
    array = list(range(100000))
    test = lambda: all_pop(array)

    # プロファイラの生成
    profiler = Profile()
    profiler.runcall(test)

    # 性能についての統計情報の取り出し
    stats = Stats(profiler)
    stats.strip_dirs()
    stats.sort_stats("cumulative")
    stats.print_stats()

$ python list_example.py
         100004 function calls in 2.302 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    2.302    2.302 example.py:24(<lambda>)
        1    0.056    0.056    2.302    2.302 example.py:16(all_pop)
   100000    2.245    0.000    2.245    0.000 {method 'pop' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

deque

deque_example.py

#!/usr/bin/env python3
# -*- coding: utf_8 -*-
"""dequeの処理時間計測
"""

from collections import deque
from cProfile import Profile
from pstats import Stats


def all_pop(array):
    for _ in range(len(array)):
        array.popleft()


if __name__ == "__main__":
    # プロファイラに渡す用意
    array = deque(range(100000))
    test = lambda: all_pop(array)

    # プロファイラの生成
    profiler = Profile()
    profiler.runcall(test)

    # 性能についての統計情報の取り出し
    stats = Stats(profiler)
    stats.strip_dirs()
    stats.sort_stats("cumulative")
    stats.print_stats()

$ python deque_example.py
         1000004 function calls in 0.394 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.394    0.394 example.py:23(<lambda>)
        1    0.283    0.283    0.394    0.394 example.py:15(all_pop)
  1000000    0.111    0.000    0.111    0.000 {method 'popleft' of 'collections.deque' objects}
        1    0.000    0.000    0.000    0.000 {built-in method builtins.len}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

diff

example.py

--- list_example.py
+++ deque_example.py
@@ -1,24 +1,25 @@
 #!/usr/bin/env python3
 # -*- coding: utf_8 -*-
-"""listの処理時間計測
+"""dequeの処理時間計測
 """
 
+from collections import deque
 from cProfile import Profile
 from pstats import Stats
 
 
 def all_pop(array):
     for _ in range(len(array)):
-        array.pop(0)
+        array.popleft()
 
 
 if __name__ == "__main__":
     # プロファイラに渡す用意
-    array = list(range(100000))
+    array = deque(range(100000))
     test = lambda: all_pop(array)
 
     # プロファイラの生成

参考

• collections --- コンテナデータ型