dequeから範囲を指定して値を取得

Question

やりたいこと

dequeで範囲を指定して値を取得したい。
調べても出てこなかったので、無理そうならlistに変換しようと思いますが、
スマートな方法があればご教授ください。

例

_deque = collections.deque(maxlen=1000)

for i in range(1000)
    _deque.append(i)

# 1000個の値がappendされた状態で末尾から100個、500個のように任意の値を取得したい。(取り出しはしなくてよい)

Answer 1

itertools.isliceを使うと良いと思います。-> ドキュメント

Comments

[quickquip]

dequeに対してisliceを使ってしまっては、dequeを使う意味がなくなるでしょう。

[YouheiSakurai]

私がitertools.isliceを良いと思った理由は「Simple is better than complex.」と「itertoolsがCで実装されているから」です。「dequeを使う意味がなくなる」はitertools.isliceが良くないとする理由としては少し変じゃないですか？dequeを使うその前提で何がスマートかと考えた結論が私の回答です。

[quickquip]

dequeを使う意味はappendとpopがO(1)の速度でできる点と、rotateがCで実装されていて高速な点にあります。それらの操作を「使わない」isliceを選ぶということは、dequeを使う意味を「無くす」ことに等しいと思います。
大きいdequeからたくさんの部分要素を取り出すならpopを繰り返すのは不利で、isliceの方がいいのですが、「大きいdequeからたくさんの部分要素を取り出す」という前提自体がdeque向きじゃない、という意味でもあります。

[Zuishin]

他のところで deque の利点を生かしてるなら別にここで生きてなくても使う意味あるんじゃないですか？
そもそもそこまで速度が必要なものかどうかも疑問です。
1000 程度の数では、データ型を変更しなければならないほどの差は出ないと思います。

[quickquip]

なるほどその通りです。納得しました。
dequeを使う局面を考えると確かに、"この部分を高速にしたい"欲求はそれほどなさそうです。

[YouheiSakurai]

quiquiさん、「dequeを使う意味」は他にもありますよ。dequeはmaxlenからあぶれた要素への参照が勝手に切れるのでweakref.WeakSet等と組み合わせると面白い使い方ができます。ご参考までに。https://teratail.com/questions/168245#reply-251105

Answer 2

一般的にこれが最良という方法はありません。
dequeはどういうアルゴリズムで動いているかを中までわかった上でないと速くならないし、実際にどのぐらいのデータをどのように扱うかを前提にしないと使うべきなのか判断できない、かなり低水準なライブラリなのです。
（だからこそスライス実装を提供していないように思えます）

長いdequeから、少数の末尾を取り出すだいたいは速い方法は

def slice_last_n(d, n):
    t = [d.pop() for _i in range(n)][::-1]
    d.extend(t)
    return t

こうでしょう。（もっときれいに書けないか……、という気はします）

ipythonの%timeitでの計測

In : x = deque(range(1000000), 1000000)

In : %timeit y = slice_last_n(x, 100)
9.9 µs ± 175 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In : %timeit y = list(x)[-100:]
11 ms ± 131 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

---

でも長いdequeから、長い末尾を取り出すならlistにする方が速いです。

In : %timeit y = slice_last_n(x, 900000)
106 ms ± 653 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In : %timeit y = list(x)[-900000:]
19.3 ms ± 429 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

---

質問のような短いdequeから、短い末尾を取り出すなら、だいたいはlistにするのが速く、コードもわかりやすいはずです。

In : x = deque(range(1000), 1000)

In : %timeit y = slice_last_n(x, 100)
10.3 µs ± 282 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In : %timeit y = list(x)[-100:]
5.93 µs ± 636 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

---

追記

https://docs.python.org/ja/3/library/collections.html#deque-recipes

To implement deque slicing, use a similar approach applying rotate() to bring a target element to the left side of the deque. Remove old entries with popleft(), add new entries with extend(), and then reverse the rotation. With minor variations on that approach, it is easy to implement Forth style stack manipulations such as dup, drop, swap, over, pick, rot, and roll.

def slice_deque(d, i, n):
    d.rotate(-i)
    t = [d.popleft() for _i in range(n)]
    d.extend(t)
    d.rotate(i+n)
    return t

In : x = deque(range(1000000), 1000000)

In : %timeit y = list(islice(x, 100, 10))
808 ns ± 12.6 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In : %timeit slice_deque(x, 100,10)
1.99 µs ± 52.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

In  %timeit y = list(islice(x, 700000, 10))
2.31 ms ± 44.5 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In : %timeit slice_deque(x, 700000,10)
257 µs ± 19.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

追記
長いdequeから、長い部分要素を取り出すならisliceの方が有利です。（popを繰り返す操作がネックになりますから）

In : %timeit y = list(islice(x, 700000, 100000))
2.21 ms ± 24.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In : %timeit slice_deque(x, 700000, 100000)
9.72 ms ± 48.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)