collections.dequeは凄い

スタック構造にしても,キュー構造にしても,collections.dequeがリーズナブルチョイス.
(n=1,000以下ならあまり気にするレベルではないけど)

比較検討したかっただけで厳密値を求めたかった訳ではないのでいい加減.
(以下の計測結果には,リスト生成(O(n)),ループ処理(O(n))の時間が含まれる)

from collections import deque


def stack_pop(n):
    a = list(range(n))
    for _ in range(n):
        a.pop()
    return a


def queue_pop(n):
    a = list(range(n))
    for _ in range(n):
        a.pop(0)
    return a


def deque_pop(n):
    a = deque(range(n))
    for _ in range(n):
        a.pop()
    return a


def deque_leftpop(n):
    a = deque(range(n))
    for _ in range(n):
        a.popleft()
    return a
%timeit stack_pop(10)
%timeit deque_pop(10)
%timeit queue_pop(10)
%timeit deque_leftpop(10)

3.56 µs ± 133 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
2.54 µs ± 32 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
4.37 µs ± 41 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
2.55 µs ± 100 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit stack_pop(100)
%timeit deque_pop(100)
%timeit queue_pop(100)
%timeit deque_leftpop(100)

20.6 µs ± 1.82 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
13.8 µs ± 349 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
30.1 µs ± 354 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
13.6 µs ± 544 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

%timeit stack_pop(1000)
%timeit deque_pop(1000)
%timeit queue_pop(1000)
%timeit deque_leftpop(1000)

188 µs ± 14.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
145 µs ± 1.8 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
388 µs ± 5.68 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
145 µs ± 2.68 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

%timeit stack_pop(10000)
%timeit deque_pop(10000)
%timeit queue_pop(10000)
%timeit deque_leftpop(10000)

2.03 ms ± 242 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
1.52 ms ± 25 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
21.7 ms ± 366 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
1.48 ms ± 22.2 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

%timeit stack_pop(100000)
%timeit deque_pop(100000)
%timeit queue_pop(100000)
%timeit deque_leftpop(100000)

20.8 ms ± 2.41 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
16 ms ± 570 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
2.84 s ± 42.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
16.3 ms ± 702 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
 
 
 
FireShot Capture 216 - JupyterLab Alpha Preview - http___localhost_8888_lab
 
 
 

list.pop(0)はとにかく遅い.配列を全て操作するので,n=1,000以上になると目にみえて,指数的に遅くなっていく(n=1000000では遅すぎて打ち切った).それ以外は,このグラフではO(n)になっているけど,上述した無駄な部分が原因で,操作の計算量はおそらくはO(1)だろう(O(1) + O(n) + O(n) ~ O(n)になってしまっている).ただ,list.pop()よりもdequeを使う方が常に20%程高速だった.かなり実効性が高い.

広告
カテゴリー: 未分類 パーマリンク

collections.dequeは凄い への1件のフィードバック

  1. ピンバック: 和が0じゃない行数だけ列を左にシフト | 粉末@それは風のように (日記)

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中