概要
- 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)
# プロファイラの生成