今川館

都内勤務の地味OLです

イテレータは前に突き進む

http://d.hatena.ne.jp/imagawa_yakata/20120104/1325703433
このネタなのですが、id:yanolabさんが別の解答を書かれています。

map_between をやってみる -slice使ったっていいじゃない編- - yanolabの日記

from itertools import islice, imap
imap(func, it, islice(it, 1, None))

このように、itertools.isliceを使えば、「次の次」を参照できるというわけです。
itertools.isliceの使い方をよく知らなかったので、これでok、これが最強の答えだと思ったのですが、一つだけ前提があります。

引数にはイテレータを渡さない。(listやdictを渡す)

です。

わたしがこだわっていたこと

何だかいちいち口うるさいなと思われるかもしれませんが、わたしは他のやり方を否定したい訳ではありません。
単に、些細なことに敢えてこだわってみるとどうなるのか自分で試したくなっただけです。

わたしがこだわっていたことは、最初は

  • リストのスライスを使うとコピーするから避けたい。
  • イテレータを作ればnextを呼んで次々に要素にアクセスできる。

この2点でした。
しばらくしてから、pythonのドキュメントを見ると、map関数の引数はiterableならば何でも良いことに気づきます。

そして今度は

  • iterableならば何でも渡せるよう実装しよう。listやdictでもイテレータでも渡せるように。

この点にこだわり始めました。
普段こんなことにこだわる必要はないでしょうが、敢えてこだわってみるとどうなるのか試したくなりました。

こだわった結果

isliceを使う方法で、引数にリストやxrangeオブジェクトを渡すと期待通り動きます。
しかし、イテレータを渡すと期待通りの結果になりません。

# -*- coding:utf-8 -*-
import itertools


def _map_between(func, iterable):
    return itertools.imap(func, iterable, itertools.islice(iterable, 1, None))
map_between = lambda func, iterable: list(_map_between(func, iterable))


def main():
    from operator import add
    
    L1 = map_between(add, [1, 2, 3, 4, 5])
    print(L1) # [3, 5, 7, 9]

    L2 = map_between(add, xrange(1, 6))
    print(L2) # [3, 5, 7, 9]

    itr = iter([1, 2, 3, 4, 5])
    L3 = map_between(add, itr)
    print(L3) # [4, 9]

    def list_like():
        yield 1
        yield 2
        yield 3
        yield 4
        yield 5

    L4 = map_between(add, list_like())
    print(L4) # [4, 9]


if __name__ == "__main__":
    main()

結果

  1. listを渡したL1 -- [3, 5, 7, 9] 期待通り。
  2. xrangeを渡したL2 -- [3, 5, 7, 9] 期待通り。
  3. iter(リスト)を渡したL3 -- [4, 9] 期待通りにならない。
  4. ジェネレータから作ったイテレータを渡したL4 -- [4, 9] 期待通りにならない。

この通り、イテレータを渡すと結果が変になります。

イテレータは戻らない

「そんなもん引数にイテレータなんか渡すんじゃねぇヴォケ!!」
というのが普通でしょうが、わたしの書いた、いちいちnextを呼んで要素を取り出す方法だとイテレータを渡しても期待通り動きます。

def _map_between2(func, lst):
    itr = iter(lst)
    x = itr.next()
    for y in itr:
        yield func(x, y)
        x = y 
map_between2 = lambda func, iterable: list(_map_between2(func, iterable))


L5 = map_between2(add, iter([1, 2, 3, 4, 5]))
print(L5) # [3, 5, 7, 9]

L6 = map_between2(add, list_like())
print(L6) # [3, 5, 7, 9]

イテレータは基本的に前に突き進むだけです。
戻りません。後ろを振り返りません。

isliceを使う方法で結果が違うのは、引数にイテレータを渡された場合に「次の」要素用イテレータと「次の次の」要素用のイテレータが同時にポインタを進めてしまうことが原因です。
「一つのイテレータを一度に2回ずつ進めてしまうから」と言った方がわかりやすいかもしれません。

ジェネレータを定義する方法はnextを呼ぶタイミングを完全にコントロールしているので大丈夫なわけです。

まとめ

何か「どやぁ」とでも言わんばかりの解説ですが、最初はそこまで考えていませんでした。

単にスライシングするとコピーを作るから嫌だ、くらいにしか思っていなかったのですが、他人から色々ツッコミをもらうと曖昧だった理解が明確になるものだなぁと思いました。

あと、このネタが3エントリに渡るちょっとしたシリーズ化してしまったので、記事を読んだ人にはくどく感じられたのではないかと思います。
一応断っておくと、これはジェネレータを使った方がわたしは良いと思ったことが発端ですが、いつ何時でもジェネレータを使えとか、ジェネレータを使わないやり方は偽物だなどと言いたい訳ではありません。

本当は最近はまっている海原雄山のネタを交えて

「この関数を作ったのは誰だ!女将を呼べ!」という風に読者を釣ろうと思ったのですが、面倒くさくなったのでやっぱりやめます。

元ネタを提供してくれたtell-k、その他指摘をくれた皆様、お陰で正月にエントリ数が稼げました。
ありがとうございました。

追記(2012/01/09)

この記事を投稿した後、id:yanolabさんがブログを更新されていました。
そう、わたしもあの後itertools.teeでイテレータをコピーできると気づいたんです。
しかし時既に遅く、最高の答えを公開されていました。

記事を引用します。

from itertools import islice, imap, tee

def mapbtw(func, it):
    iter1, iter2 = tee(it)
    return imap(func, iter1, islice(iter2, 1, None))

teeはイテレータをコピーしちゃう関数。tee(it,n)で好きなだけコピーできる。
ただし、注意点は、itとteeの戻り値の1個目は同じイテレータを指していること。(意外とハマる)

これだ!これですよ!わたしが作りたかった関数は。
簡潔で、無駄がなく、そして正しく動く。
itertoolsがいかに様々な機能を備え、使いこなせる者には強力な力を与えるということがよく解ります。

大変勉強になりました。

追記(2012/01/11)

あれからitertoolsのドキュメントを読んでいて思ったのですが、itertools.teeは内部でcollections.dequeを使っているようなので、やはり一番シンプルなのはジェネレータをさくっと書く、本シリーズでわたしが主張したやり方のようです。
(但しメモリや速度については計測していません。)