シーケンスの途中から前方に走査できるイテレーター

はじめに

以前書いた、シーケンスの途中から前方に走査できるイテレーターが

sslice.py

def sslice(sequence, *slice_args):
    return (sequence[index]
            for index in range(*slice(*slice_args).indices(len(sequence))))

という短さの割に結構便利で重宝しています。

もし貴方が常日頃から、

シーケンスに対して itertools.islice() っぽく使えて、途中から走査しても高速で、前方にも走査できるイテレーターが欲しいんだよおおおぉぉぉ！！！

と切望していらっしゃるようでしたら、ぜひ上記のコードを今すぐご自由にお使いください。

どうしてそんな関数をわざわざ用意するのかさっぱり分からない……。

と思った方は、恐れ入りますがどうか続きをご覧ください。

sslice() の使いどころ

まずは具体的な状況として、

リスト L から、n 番目の要素とその前後の最大 m 要素を含むリストを取り出したい

という状況を想定してみます。

例えば、何かのランキングのリストがあって、自分の順位が12,345位で、その上下それぞれ5位までを含めて表示したいというような場合ですね。

もう少しよくありそうな例にしたかったのですが、上手い例が見つからなくてすみません。

なお、サンプルコードを単純にしたいので、リスト L の先頭の要素は1番目ではなく0番目の要素ということにします。

この場合、12,345位は12,344番目の要素ということになりますね。

さらに、自分以下の順位について処理するのは簡単なはずですので、ここでは自分より上の順位についての処理だけ考えることにします。

よって今回の処理は、

リスト L から、n 番目の要素の前方の最大 m 要素を含むリストを取り出す

という要件になりました。この段階で私が考えた方法はスライシングを使って、

>>> L = list(range(1, 50000+1))
>>> n = 12345 - 1
>>> m = 5
>>> L[max(0, n - m): n]
[12340, 12341, 12342, 12343, 12344]

のようなコードでリストのスライスを得る方法でした。

もちろん、この方法でも特に問題はありません。

ですが、もしこの処理の要件が「前方の最大 m 要素」ではなく「ある判定条件を満たす前方の最大 m 要素」だったらどうなるでしょうか？

今回の判定条件は単純に、

>>> def is_odd(number):
...     return (number % 2 == 1)
...
>>> is_odd(1)
True
>>> is_odd(2)
False

ということにします。要は奇数ですね。

こうなると個々の要素が条件を満たすかどうかを判定しなければいけませんので、少なくともスライシングだけでは解決できず、リストの n 番目の要素から前方への走査が必要になります。

念のため、ここまでの話を一度まとめると、

>>> L = list(range(1, 50000+1))
>>> n = 12345 - 1
>>> m = 5
>>> L[max(0, n - m): n]
>>> def is_odd(number):
...     return (number % 2 == 1)
...
>>> 

という条件下で、

[12343, 12341, 12339, 12337, 12335]

という結果を得るための処理を書くことが目的です。

最終的にはランキング順に表示するために、結果のリストをひっくり返して [12335, 12337, 12339, 12341, 12343] にしなければいけませんが、その処理は省略します。

スライスはメモリを食い過ぎる

最初に検討したのは、スライスとリスト内包表記を組み合わせる方法でした。

>>> [rank for rank in L[n - 1::-1] if is_odd(rank)][:m]
[12343, 12341, 12339, 12337, 12335]

正しい結果が表示されました。

しかしこの方法はリスト L の要素数が大きかった場合に、一時的に生成されるリストのメモリ消費が馬鹿になりません。

よってこの方法は却下することにします。

islice() は前方を走査できない

次に検討したのは、みんな大好き itertools モジュールの islice() を使ってイテレーターで処理する方法だったのですが、

>>> from itertools import islice
>>> islice(L, n - 1, None, -1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: Step for islice() must be a positive integer or None.
>>>

と何故かエラーになってしまいました。

どうしてこれがエラーになるのか少し悩んだのですが、islice() のヘルプを読んでようやくその理由が分かりました。

>>> help(itertools.islice)
Help on class islice in module itertools:

class islice(builtins.object)
 |  islice(iterable, stop) --> islice object
 |  islice(iterable, start, stop[, step]) --> islice object
 |
 |  Return an iterator whose next() method returns selected values from an
 |  iterable.  If start is specified, will skip all preceding elements;
 |  otherwise, start defaults to zero.  Step defaults to one.  If
 |  specified as another value, step determines how many values are
 |  skipped between successive calls.  Works like a slice() on a list
 |  but returns an iterator.
...

要するに、islice() は第一引数としてイテラブル (iterable)、つまり __iter__ メソッドを持つかシーケンスなオブジェクトを想定していたからだったんですね。

Python の list オブジェクトはシーケンスですが、イテラブルなオブジェクトは必ずしもシーケンスであるとは限らない、むしろシーケンスではないことの方が多いので、途中から逆方向に走査できることは期待できません。

なので islice() の step は負数にできない仕様になっていたという訳ですね。

私は諦めが悪いので、

islice() の第一引数がシーケンスだった場合だけ、step に負数を指定できるようにすればいいんじゃないの？

と思わなくもないのですが、どうやら引数の型に応じて振る舞いを変えるのは Python 的に美しくないという理由であえてそういう仕様にはしなかったようです。

これ以上「どうして私達の Python はこんなに正しくて美しすぎるのか？」について悩むのは Pythonista の方々にお任せすることにして、今回の目的を達成するための話に戻りたいと思います。

シーケンス用の islice()、sslice() を作る

色々考えてみたのですが、結局は安直にシーケンス用の islice()、sslice() を書いてみました。

def sslice(sequence, *slice_args):
    return (sequence[index]
            for index in range(*slice(*slice_args).indices(len(sequence))))

sslice() を使ってスライスをなるべく展開しないように気をつけて書いたのが下記のコードです。

>>> list(islice((rank for rank in sslice(L, n - 1, None, -1) if is_odd(rank)), 0, m))
[12343, 12341, 12339, 12337, 12335]

これでようやく今回の目的を達成できました。

ちなみに islice() はイテラブルなオブジェクトのスライス (slice) のイテレーター (i) という意味らしいので、シーケンスのスライスのイテレーターを sslice() という名前にしてしまうと、敬虔な Pythonista の方々に叱られそうですが、イテレーターのスライスが欲しい時は islice()、シーケンスのスライスが欲しい時は sslice() というのはとても覚えやすいのでどうかご勘弁ください。

sslice() が islice() よりも速いケース

sslice() はシーケンスを添字経由でアクセスしますので、islice() でも同じ結果を得られるのであれば色々と最適化された islice() を使う方が大抵は速いのですが、引数の start の値が大きい場合は sslice() を使った方が速いことがあります。

その理由は、islice() が先頭から逐次処理しなければいけないのに対して、sslice() が添字でアクセスできるからです。

先程、「自分以下の順位について処理するのは簡単なはず」と書きましたが、そちらについても必要に応じて sslice() を使った方が良いということですね。

islice() のこの制限というか仕様については過去何度か改善要望があったようなのですが、どうやら前述した

引数の型に応じて振る舞いを変えるのは Python 的に美しくない

という理由で却下されているようです。

よく訓練された Python ユーザーであれば、その説明を聞いた途端に感涙にむせび泣きながら、

さすが Pythonista！　使いやすさよりも正しさを優先するなんて事を平然とやってのけるッ　そこにシビれる！　あこがれるゥ！

と叫びながら服を脱いでバケツに入った氷水を頭から被るぐらいはしないといけないのかもしれませんが、私は体が弱くてそういうのはちょっと苦手ですのですみませんがパスさせてください。

まとめ

シーケンスの途中から前方に走査できるイテレーターを書いてみました。

sslice.py

def sslice(sequence, *slice_args):
    return (sequence[index]
            for index in range(*slice(*slice_args).indices(len(sequence))))

短い割に結構便利で重宝していますので、シーケンスに対して itertools.islice() っぽく使えて、途中から走査しても高速で、前方にも走査できるイテレーターが欲しい方はぜひご利用ください。

短いので多分過去に誰かが似た関数を書いているだろうと思っていたのですが、変数名以外は同じコードをさっき見つけたのでライセンスは主張しないことにします。

どうかご自由にお使いください。

（おまけ）slice.indices() の使いどころ

ちなみに sslice() が slice.indices() を使っているのは、

>>> sslice(range(20), None, None, -1)

のような引数に対応するためです。

Python のヘルプドキュメントは「これって、わざと難しく書いているんだろうか？」と思ってしまうほど分かりにくい箇所が多数あるのですが、slice.indices() のヘルプもその一つだと思います。

>>> help(slice.indices)
Help on method_descriptor:

indices(...)
    S.indices(len) -> (start, stop, stride)

    Assuming a sequence of length len, calculate the start and stop
    indices, and the stride length of the extended slice described by
    S. Out of bounds indices are clipped in a manner consistent with the
    handling of normal slices.
(END)

このメソッドが一体何を目的として用意されているメソッドなのか上記のヘルプを読んで初見で分からなかったのは私だけではないですよね？(汗

そんな slice.indices() ですが、任意の slice オブジェクトから range() の引数を生成したくなった時に使うと一発でビシッと決まりますのでオススメです。

多分、それ以外でこのメソッドが有用な状況はないと思います。(笑)