名古屋で数学するプログラマ(仮)

@antimon2 が趣味兼一部本職の数学で何かするときのブログ。

「yieldのお勉強 Lv.2」解説(Python編) #CodeIQ

先日、CodeIQ の以下の問題が、公開終了となりました。
たくさんの挑戦、ありがとうございます。

(すでに問題の公開は終了していますので、上記 URL で問題詳細を見ることはできません)

ということで、Pythonista のみなさま、たくさんおまたせしてごめんなさい。恒例の解説記事です。

問題文は省略します(挑戦者だけの特典♪)が、Lv.1 と同様、問題は、一部が未実装のプログラムを実装してテストを全て通るようにする、というもの。
以下に、問題プログラムと解答例を示します。

※注意事項:本題に入る前に

次の Lv.99 問題ですが、問題文では触れていませんが、この Lv.2 問題の結果を利用しても良いという内容になっています。
Lv.2 問題を解いていないけれど Lv.99 問題を解く方には、この解説記事は壮大なネタバレになってしまいます^_^;
「Lv.2 解けなかった(挑戦しようとはした)けれど Lv.99 にも挑戦したい」と言う方は、そのままお進みください。
「Lv.2 問題の存在を知らなかった(最近ユーザ登録して Lv.99 問題から初挑戦)」、「Lv.2 は眼中になかったから問題を見てもいない」と言った方は、以下の「問題プログラム」だけ参照して引き返していただく(でまず Lv.2 問題をご自分で解いてみてから Lv.99 問題に取り組んでいただく)か、Lv.99 問題解答提出時に「Lv.2 解いてないですが解説見ちゃいました」と自己申告していただければ幸いです^_^;

問題プログラムと解答例

まずは、問題プログラム。

問題プログラム:

IteratorCloner というクラスを実装する、という問題。
このクラスは、コンストラクタiterator (generator) を与えて、get_clone() メソッドでそのクローンを取得する、というもの。
ここでいう「iterator のクローン」は、「オリジナルの iterator と、同じ要素を同じ順番で列挙するもの」という考えです。
また 1回の get_clone() で取得できる iterator(のクローン)は1つだけで良いのですが、その代わり何度呼び出しても常に新しいクローンが取得できること、というのを要求しています。

解答例は2種類用意しました。

※注意事項再掲:Lv.99 挑戦者で Lv.2 を解いていない方(挑戦しようとしたけれど解けなかった方は除く)は、ここで引き返していただくか、Lv.99 解答提出時に「Lv.2 解説見ちゃいました」と自己申告していただければ幸いですm(_ _)m

解答例1:

解答例1は、collections モジュールの deque を利用した実装です。deque は「双方向キュー」で、先頭または末尾への要素の挿入/要素の取り出しが高速に行えるデータ構造です。
コンストラクタdeque のリストを生成し、get_clone() メソッドで新しい deque を生成してそこに要素を出し入れしながら yield する、という仕組みです。
なお、メンバとして持つことになる deque のリストは、生成したクローンの数+1個の deque を持っています。最初の1個は、今までの要素を全てキャッシュするためのもの。新しいクローンを生成するときに、今まで列挙済の要素を知らないと頭から列挙することが出来ないための措置です。そう、結局全要素をキャッシュすることになるんですよね、これちょっともったいないですが、Pythoniterator の仕様上、仕方ないです。

解答例2:

解答例2は、解答例1をシンプルに再構築したもの。
どうせキャッシュが必要なら、メンバ変数としてはキャッシュだけを持たせて、get_clone() メソッドの実装内では、そのインデックス番号だけを管理する、という方針にしたものです。
新しく get_clone() メソッドが呼び出されたときと、まだ self._it(オリジナルの iterator)の次の要素を取得していなかったときの処理が、どちらも解答例1に比べてはるかに少ないので、今回はこの実装で充分です。

なお、解答例1で deque というものを導入しましたが、使い方だけ見れば、これは普通にリストでも問題ないように見えます。

class IteratorCloner:
  def __init__(self, it):
    self._it = iter(it)
    self._ques = [[]]

  def get_clone(self):
    new_que = list(self._ques[0])
    self._ques.append(new_que)
    while True:
      if not new_que: # empty
        new_val = next(self._it)
        for d in self._ques:
          d.append(new_val)
      yield new_que.pop(0)

はい、これでも動きます。こう書いた方も正解です(^-^)
ただ、これは deque を使用したコードに比べるとかなり性能が落ちます。
list.append() メソッドや、list.pop(i) メソッドが、それほどパフォーマンスが良くないからです。
リストは要素固定での操作(i番目の要素の参照・代入)は高速ですが、要素数が変わる操作には特化されていないためです。

逆に固定長操作が高速なので、解答例2のように yield self._cache[i] というような操作は比較的高速です。
その前でたまに self._cache.append(next_val) していますが、これが実行される割合はクローンが多く生成されればされるほど少なくなるので、長い目で見れば性能は大きな問題にはなりません。

キャッシュとインデックスの比較について

解答例2で、以下のように記述しています:

      if len(self._cache) <= index:

つまり「今から参照しようとしている要素が、キャッシュにまだ含まれない(=まだ元の iterator から取得していない)なら」という if 節になっています。
これ、if で良いのでしょうか?安全のため、while の方が良いのではないか?と思う方もいらっしゃるかもしれません。実際、ここを while とした以下のようなコードを送ってくださった解答者さまもいらっしゃいました。

      while len(self._cache) <= index:

もちろんこれでも動きとしては期待通りで、正解です(^-^)
でも、while である必要はなく、解答例の通り if で充分です。

こう考えてください。
もしまだ元の self._it から取得していない値が2つ以上あったら(⇔キャッシュされていない要素がまだ2つ以上あったら)、1つ前の値を yield するときに self._it から取得せずに列挙したことになります。でもそんなことはあり得ません。構造上、1つ飛ばして列挙する仕組みにもなっていません。
コロンブスの卵のような感じですが、お分かりになりますでしょうか?

itertools.tee() を利用した別解について

実は標準添付ライブラリに、itertools.tee() という関数が用意されています。
itertools.tee() は、引数に指定した iterator を2つ以上に枝分かれさせる関数です。
元の iterator は内部で保持され、枝分かれさせた各 iterator の列挙処理時に使用されます。

はい。その字面だけ見れば、今回の仕様を満たすことは分かりますね。
実際、かなり多くの方から、以下のような解答が寄せられました。

import itertools

class IteratorCloner:
  def __init__(self, it):
    self._it = iter(it)

  def get_clone(self):
    clone, self._it = itertools.tee(self._it)
    for el in clone:
      yield el 

もちろん、これもきちんと正常に動作しますし、見た目非常にコンパクトです(^-^)
今回はこれは正解にしました。

ただ、このコードには実は少し無駄があります。

先ほど「元の iterator は内部で保持される」と書きましたが、つまりメモリ上に残るのです。
そして get_clone() メソッドを1回呼ぶたびに、新しい iterator オブジェクトが2個ずつ生成されます。
つまり。N回呼び出せば合計で 2*N+1 個の iterator オブジェクトが存在することになるのです。
クローンを N個 生成するために、それ以外のオブジェクトもそれ以上生成している。
そう考えると、無駄ですよね?

この動作が「イケてないなー」と思ったのが、この問題を思いついたきっかけなのです。
(結果的にその「イケてない」と思っていたコードも正解になってしまう問題設定になってしまったのですが^_^;)

それに itertools.tee() を使うんだったら、そもそも yield 不要です。

import itertools

class IteratorCloner:
  def __init__(self, it):
    self._it = iter(it)

  def get_clone(self):
    clone, self._it = itertools.tee(self._it)
    return clone

これでOK。こっちの方がよっぽどシンプル。
(ただしこちらは「yield を使用すること」という条件に合致しないので「正解ですが不完全(減点対象)」としています)

この答えを求めるような問題を出すのなら、「yield の使い方」というテーマではなく「標準添付ライブラリの使い方」というテーマでワンラインの穴埋め問題にでもしています。
んー、なんか、「出来るだけコンパクトに」とか「とにかく短く」というのが流行りすぎているような気がするのは、気のせいでしょうか?

あと(もう少し続きます、お付き合いくださいm(_ _)m)、そのまま使うのが忍びなかったのか、「itertools.teeを写経しました」という解答者さまもいらっしゃいました。
(↓コメント等適宜除去しています)

class IteratorCloner:
  def __init__(self, it):
    self._it = iter(it)

  def get_clone(self):
    it = iter(self._it)
    queue = [[] for i in range(2)]
    def gen(mydeque):
      while True:
        if not mydeque:
          newval = next(it)
          for d in queue:
            d.append(newval)
        yield mydeque.pop(0)
    self._it,another=tuple(gen(d) for d in queue)
    return another

おそらく元にしたのは、以下のサイト(もしくはその英語版、もしくは Python3 版)だと思われます:
9.7. itertools — 効率的なループ実行のためのイテレータ生成関数 — Python 2.7ja1 documentation
↑の参照先に、この itertools.tee() 関数の「等価コード」が掲載されています。そっくりですね。違うのは、collections.deque を使用しているところを普通の list に置き換えているところ。
もちろんこれも、今回の正解条件を満たすので正解です(^-^)

ただ。このコードを見て、何か気付きませんか?

そうです。私の解答例1(を list に置き換えた別解)と、よく似ていますよね?

正直に言いますと、私の解答例1は、このコードから着想を得て生まれたものです。
itertools.tee() では第2引数で与えられる、枝分かれの個数を、その時点で与える代わりに動的にしてリストを可変にしただけ。
おそらく私の解答例1とほぼ同じコードを送ってくださった方の半分くらいは、同じ発想で同じコードから同じ経緯で生み出したコードを送ってくれたのではないかと想像しています*1

メソッド内の generator 関数について

私の解答例とほぼ同じなのですが、ちょっとだけ違う、以下のような解答を送ってくださった方もかなりいらっしゃいました。

class IteratorCloner:
  def __init__(self, it):
    self._it = iter(it)
    self._cache = []

  def get_clone(self):
    def iter_clone():
      index = 0
      while True:
        if len(self._cache) <= index:
          next_val = next(self._it)
          self._cache.append(next_val)
        yield self._cache[index]
        index += 1
    return iter_clone()

私の解答例2と、どこが違うか分かりますか?

get_clone()メソッドの定義の中に、もう1つ、iter_clone() という generator 関数が定義してあります。
これを呼び出した結果を返している、ということ。
はい、「yield で generator 関数を作る」という前回から続いているテーマに素直にしたがった、丁寧なコードです(^-^)

でも。
Python において、メソッドというのは結局は関数なのです。
このように関数内に関数を用意してその結果を利用する、ということは、複雑な処理をするときにはままあることですが、今回のように「メソッドの実装が、内部関数を呼んでいるだけ」の時には、逆にちょっと無駄があります。
「別の関数を呼び出す」という一手間が増えるわけですから。
むしろ、メソッドの実装を generator 関数にしてしまうというのは別にアリです。インデントも1つ減りますし関数呼び出しのオーバーヘッドも1つ減ります。
ワンポイントテクニックとして、覚えておいても損はないと思います(^-^)

別解・発展解の紹介

今回は解答に余り大きなブレはなかったのですが、その中で逆に、工夫を入れた解答、ユニークな別解も寄せられました。
逆にこちらが勉強になった面もありますので、いくつか紹介させていただこうと思います。

Chatnoir様の解答(一部抜粋)
import collections
import weakref

class IteratorCloner:
  def __init__(self, it):
    self._it = iter(it)
    # ↑この行は変更しないでください!
    # ↓必要に応じてコードを追加するのはOK。
    self._clones = weakref.WeakKeyDictionary()
    self._cache = []

  def get_clone(self):
    # ここを適切に実装しなおしてテストが通るようにしてください。
    # ただし、以下の条件を満たすこと:
    # ・self._it を何らかの形で利用すること。
    # ・yield 式を必ず利用すること。
    newclone = collections.deque(self._cache)
    def gen(mydeque):
      while True:
        if not mydeque:
          newval = next(self._it)
          for clone in self._clones.values():
            clone.append(newval)
          self._cache.append(newval)
        yield mydeque.popleft()
    ret = gen(newclone)
    self._clones[ret] = newclone
    return ret

私の解答例1に、weakref.WeakKeyDictionary を導入した発展解。
WeakKeyDictionary は、公式リファレンスによると「キーを弱参照するマッピングクラス」*2
今回キーにしているのは、内部で定義・実装した generator 関数を実行した戻り値、つまり generator そのもの。また設定している値は、collections.deque オブジェクト。
つまり。
「生成した generator が使用されなくなった(より正確には「どこからも参照されなくなった」)ら、
deque オブジェクト(と generator)をガベージコレクションの対象にする」
という仕組みが入れられたコードになっています。

確かに。解答例1のままでは、全てのクローンが使われなくならない限り(かつ IteratorCloner クラスのインスタンスそのものが GC の対象にならない限り)、内部で保持している deque オブジェクトはいつまでも残ったままになりますね。
正直、そこまで考えていませんでした。お見事です!

なおこのコードも、先ほど挙げた例のように、メソッド内に generator 関数を定義していますが、今回は生成した generator をキーにする必要があるので、先ほどのようにメソッドそのものを generator 関数化してしまうことは出来ません。

wonderful_panda様の別解(改)
import itertools
from collections import defaultdict

class IteratorCloner:
  def __init__(self, it):
    _it = iter(it)
    self._cache = defaultdict(lambda:next(_it))

  def get_clone(self):
    c = self._cache
    for i in itertools.count():
      yield c[i]

『「self._itを使うこと」という制約が無ければこういう横着をしたいところ』という一言と共に、コメント欄に書かれていたコード(一部改)です。
collections.defaultdict *3は、インスタンス生成時の第1引数に関数を渡すと、キーが存在しないときにその関数を引数なしで呼び出し、その結果を値として登録するとともに返す、というもの。
その仕組みを利用して、「元の iterator から、すでに取得済ならその値を利用し、まだ取得していなかったら取得してキャッシュしてから利用する」という仕組みを作っています。
非常にコンパクトで良いですね(^-^) 「self._it を使うこと」なんて制約付けなくてもよかったかな、なんて思ったりもしちゃいました。

ただ、おそらくご本人もご承知の通り、この方法だとパフォーマンスはかなり落ちます。
普通の辞書(dict)のキーによる参照になるので。それなりに速い実装になってはいるであろうけれども、リストの要素参照や dequepopleft() に比べてしまったらやはり遅くなりますし。未取得の要素を取得して記憶する仕組みもそれなりに。
でもとにかくパフォーマンスよりもコンパクトさを求めるなら、見た目スッキリするこれはアリですね(^-^)

コメント紹介(抜粋)

こちらも恒例、コメントご紹介。
お寄せいただいたコメントを一部紹介、およびこの場を借りて返信いたします。

(みけCAT様)
《中略》
そこで、要素が足りなくなったら追加すればいいのではないかと考えた。
すなわち、キューのような構造である。
《後略》

⇒もっと長く考察コメントが前後に続いていたのですが、コアなこの部分だけ抜粋させていただきました。
 技術的・論理的な考察で、きちんとここに辿り着けるというのは、さすがです(^-^)
 これが、桜先生の言っていた『遅延』という言葉のコアです。
 「要素がほしいけれど、まだ算出されていなかったら算出する(必要になったときに初めて取得する)」
 この考え方に気付いて(もしくは知っていて)、それを実装出来れば、立派な中級者以上です(^-^)

(R修行中様)
標準パッケージの itertools.tee() を参考に、作成しました。
テストケース は 4つとも通りましたが、問題の趣旨を取り違えていないだろうかとやや不安です。

(tany-k様)
(とは言え、テストは通ったものの、こんな方法で良かったのでしょうか・・・。かなり不安なまま提出します・・・。)

(tnakao様)
遅延評価の実装がこれで良いか自信は無いですが、一応テストは通るので。。

⇒お三方とも、ご自分では不安と仰っていましたが、中身を見てみると先述の『遅延』処理が見事に実装されていました(^-^)
 お見事ですo(^▽^)o

(せきゅあ様)
itertools.teeを使おうと思いましたが、使い勝手が悪かったので自分で実装しました。

(そらまめ様)
itertools.tee()を使わずに実装しました。
ライブラリを知ることができ、勉強になります。

⇒お二方とも、itertools.tee() の難点に気付き(もしくはご存じで?)ご自分で実装してくださいました(^-^)
 正直、こういう反応を期待していた面もあるのでこちらとしても素直に嬉しいですo(^▽^)o

(ウッキー竹脇様)
日本中、世界中の関連するサイトやブログなど読みつくしてようやくです。。
かなり勉強になりました。

(なおゆら様)
Lv1,Lv2ともにとても勉強になります。あまり時間が割けなかったのでLv3に向けて復習等を行い理解を深めたいと思います。

⇒o(^▽^)o
 あ、既にお気づきかとは思いますが、次は Lv.3 ではなく Lv.99 なのでヨロシク。

*1:後の半分は、元々知っていて見なくてもこういうコードがかけていた方、なのではないかなー、と期待o(^▽^)o

*2:参照:http://docs.python.jp/2/library/weakref.html#weakref.WeakKeyDictionary

*3:参照:http://docs.python.jp/2/library/collections.html#collections.defaultdict