Python - ilenの中身を追っかける
code:ilen.py
# This approach was selected because benchmarks showed it's likely the
# fastest of the known implementations at the time of writing.
counter = count()
deque(zip(iterable, counter), maxlen=0)
return next(counter)
が速いらしいがなんで?という話。
deque
iterableが渡された場合はdeque_extendが呼ばれている。
deque_extendはイテレータをiternextしていってdeque_append_internalするが、maxlenが0の時だけはconsume_iteratorという特別実装が呼ばれる。
こいつはiternextを呼んで、取れた要素の参照カウントを減らして、というのを黙々とやっている。シンプル。参照カウントを即座に減らすのは後でキモになる。
zip
で、dequeで呼んでいたiternextの中身はPyTypeに詰められた関数ポインタで、この場合zip_next。
おもしろいのが、zip_newで lz->result に一個だけタプルを事前に作ってあり、この参照カウントが1だったら中身だけ差し替えてnextから返すようになっている。そうでなければタプルを新規に作って返す。
使い回しタプルを返す場合は参照カウントを1増やしているので、受け取った側で参照カウントが減らされないと以降は再利用されない。
ちなみにこれ、使い回しタプルを差し替えることはしないようなので、他全部dequeで爆速ループ回したとしても最初の要素の参照を握るだけで遅くなる。
(zipしなければf1とf2の速度は大差ない)
code:bench.py
from collections import deque
def f1(iterator):
deque(iterator, maxlen=0)
def f2(iterator):
x = next(iterator)
deque(iterator, maxlen=0)
return x
a = list(range(100000000))
%timeit f1(zip(a))
%timeit f2(zip(a))
count
コメントにあるように、stepが1かつカウンタ値がPY_SSIZE_T_MAXより小さい間のnextは、めちゃくちゃシンプルに lz->cnt++ して返すだけ。そりゃー速い。
単純になにもせずイテレータを消費するだけでも、forよりdequeの方が速い。少なくともインタプリタを動かす必要はない。
code:bench.py
def consume_deque(iterator):
deque(iterator, maxlen=0)
def consume_for(iterator):
for _ in iterator:
pass
%timeit consume_deque(iter(a))
%timeit consume_for(iter(a))
enumerable自体はzip+countを高速化の工夫ごと合成したようなものなので、zip+countより若干速い。
けれど回したあとのカウンタ値がほしいとなると、next を呼ぶ時点で前の result の参照カウントを減らすことができず、タプルを使い回せないのが痛いように見える。
code:bench.py
%timeit deque(zip(a, count()), maxlen=0)
%timeit deque(enumerate(a, 1), maxlen=0)
残る手としては、enumerableやzipのようにタプルを作ることなく、流れた要素数をカウントするような部品があれば速そうだけれど…。
code:counting.py
class CountingPipe:
def __init__():
self.cnt = 0
def __call__(iterable):
for x in iterable:
self.cnt += 1
yield x
をCで実装したようなやつとか。実質的に enumerate のインターフェイス違いだな…。
forよりdequeの方が速いと書いたが、nextを呼ぶ前に強参照が消えていればタプルの再利用はできるので、maxlen > 0 なdequeより有利になるはず。実際それらしいコードはある。
(じゃあ for x in it: pass で十分では?と思ったが、 x のスコープがループ一回に閉じてないから解放できないのかこれ)
memo