Python3.xで『スライドするイテレータ』を書いてみる (重複あり／なし)
能書き
次のようなイテレータが欲しくなったことはないだろうか。
>>> for e in ideal_it_A(range(6), 3):
... print(e)
...
(0, 1, 2)
(3, 4, 5)
>>>
>>> for e in ideal_it_B(range(6), 3):
... print(e)
...
(0, 1, 2)
(1, 2, 3)
(2, 3, 4)
(3, 4, 5)
これらを書いてみただけの話。Gist
重複のないイテレータ
出落ちのようだが、これについては公式リファレンスに言及がある。
引用元： 2. 組み込み関数 — Python 3.6.3 ドキュメント (太字は引用者)
zip(*iterables)
それぞれのイテラブルから要素を集めたイテレータを作ります。
(中略)
イテラブルの左から右への評価順序は保証されています。そのため zip(*[iter(s)]*n) を使ってデータ系列を長さ n のグループにクラスタリングするイディオムが使えます。これは、各出力タプルがイテレータを n 回呼び出した結果となるよう、 同じ イテレータを n 回繰り返します。これは入力を長さ n のチャンクに分割する効果があります。
よって、これをそのまま用いて次のように書けばよい。
def split_each(iterable, n):
return zip(
* [iter(iterable)]*n
)
重複のあるイテレータ
一方こちらのイテレータについては、リファレンスに言及がない。
最初は単純に考え、次のようなコードを書いてみた。
def slide_each_simple(iterable, n):
sequence = tuple(iterable)
return zip(
* [sequence[i:] for i in range(n)]
)
しかしこの方法は、与えられた全てのイテレータをタプルに置き換えてしまう。
意味合い的には分かりやすいが、実体化する時間的なコストがある。
そこで、次のような二つの代替関数を用意した。*1
from copy import copy
def slide_each_faster_A(iterable, n):
iterator = iter(iterable)
return zip(
* [
[copy(iterator), next(iterator)][0]
for _ in range(n)
]
)
def slide_each_faster_B(iterable, n):
def _func(iterator, n):
for _ in range(n):
yield copy(iterator)
next(iterator)
return zip(
*_func(iter(iterable), n)
)
後述するとおり上記の代替関数のパフォーマンスはさして変わらない。
好きな方を使うと良いだろう。後者の方が素直だが。*2
実行速度の計測／比較
ideal_it_Bを満たす三関数について、実行速度を比較してみた。*3
| Gist | Iterator | Sequence | |
|---|---|---|---|
| List | Tuple | ||
| simple | 23.01130 | 10.26225 | 7.27913 |
| faster_A | 14.45048 | 13.33324 | 13.42435 |
| faster_B | 14.48402 | 13.39973 | 13.36088 |
結果を見ると、必ずしもfaster_Xが速いというわけではないことがわかる。
simpleのボトルネックは、やはりイテレータのタプルへの置き換えのようだ。
次のようにエイリアスを決めておくと、ストレスなく利用できるかもしれない。
slide_each = slide_each_faster_A
slide_each_gen = slide_each_faster_A
slide_each_seq = slide_each_simple
悲しいオチ
書いた記事が間違っていると恥ずかしい。従って、必死で調べる。
その結果、自らのコーディングが車輪の再発明に過ぎないことを知るのだ。
Windowing
These tools yield windows of items from an iterable. Return a sliding window of width n over the given iterable.
These tools yield windows of items from an iterable. Return a sliding window of width n over the given iterable.
>>> from more_itertools import windowed
>>>
>>> for e in windowed(range(5), 3):
... print(e)
...
(0, 1, 2)
(1, 2, 3)
(2, 3, 4)
>>>
>>> for e in windowed(range(5), 3, step=2):
... print(e)
...
(0, 1, 2)
(2, 3, 4)
わあ便利。みなさんはこっちを使いましょう。pipで入るよ。
私のコードに優位性を見出すとしたら、ミニマムなことくらいだと思う。*4
追記：2018/02/01
タイムリーにも、同様の記事がQiitaにアップされていた。
このコードをちょいと書き換えて、more-itertoolsを含め再計測してみる。
| Gist | Iterator | Sequence | |
|---|---|---|---|
| List | Tuple | ||
| simple | 22.97496 | 10.17278 | 7.31506 |
| faster_A | 14.70850 | 13.49781 | 13.45389 |
| faster_B | 14.71984 | 13.70904 | 14.27782 |
| quanon | 3.06136 | 2.77098 | 3.70850 |
| windowed | 0.67819 | 0.38008 | 0.53994 |
まじか。5～6倍の違いは覚悟していたが、まさか数十倍の差があるとは。
逆に言えば高速化に関する良い題材となり得るので、今後解析しようと思う。
