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

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

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

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

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

ということで、少々遅れましたが、恒例の解説記事です。

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

問題プログラムと解答例

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

問題プログラム:

enum_diff というメソッドが仮実装になっています(単純に第1引数 iter_a を列挙するだけになっています)。
これを適切に実装し直して、「iter_a に存在し、iter_b に出てこない要素(整数)を列挙するメソッド」にする、というもの。
ただし簡単のために、以下の仮定を設定:

  • iter_aiter_b も)要素は全て整数値で、値が増加することはあっても減少することはない(広義の単調増加)

またコメント中に「解き方は大きく分けて2種類」と書いてあります。これは私の想定解答例が2つと言うこともありますが、実際にそのアプローチが少し違うものになっています。
その解答例を以下に示します。

解答例1:

解答例1は、iter_aeach メソッドで要素を列挙しながら、その中で(Enumerator 化した)iter_bpeek および next メソッドを利用して値を取り出したり次の値を取得したりして、同じものが存在したら yield しない、という方針。
一度でも StopIteration が発生したら、フラグ変数を true に設定して、以降無駄な peeknext メソッドによる StopIteration 発生を抑制しています。
わざわざ変数に代入したりして分かりやすく書いたつもりなので、難しいことはないですよね?

解答例2:

解答例2は、iter_aiter_bEnumerator 化し、loop do〜end のループ内で両方を peek および next メソッドを利用して比較しながら処理を進める、という方針。
ポイントは、begin〜rescue〜end を利用していない、という点。
問題中では一切触れていなかったのですが、loop do〜end というループは、内部で StopIteration が発生すると、それを適切に捕捉し、そこでループを中断してくれます。ループの外に StopIterationraise しません。
この仕様を活かしました。

なお、今回用意した解答例は、説明のための利便性を重視して丁寧に書きましたが、どちらももっとコンパクトに書くことも出来ます。例えば、
解答例1改(enum_diffメソッドのみ):

def enum_diff iter_a, iter_b
  return to_enum :enum_diff, iter_a, iter_b unless block_given?
  enum_b = iter_b.to_enum
  enum_b_terminated = false
  iter_a.each do |a|
    yield a if enum_b_terminated || begin
      enum_b.next while enum_b.peek < a
      a < enum_b.peek
    rescue StopIteration
      enum_b_terminated = true
    end
  end
end

解答例2改(enum_diffメソッドのみ):

def enum_diff iter_a, iter_b
  return to_enum :enum_diff, iter_a, iter_b unless block_given?
  enum_a, enum_b = [iter_a, iter_b].map(&:to_enum)
  loop do
    enum_b.next while enum_b.peek < enum_a.peek
    yield enum_a.peek if enum_a.peek < enum_b.peek
    enum_a.next
  end
  loop do
    yield enum_a.next
  end
end

こんな感じ。
もうコンパクトというかトリッキーですね。短けりゃ良いってもんじゃない、って話です。

考察と反省

今回もまず反省として、やはりテストケース少なすぎた(>_<)
用意したテストは通るけれど、少し違う引数を与えると途端に期待通りに動かなくなるコードが、今回多数寄せられてしまいました。
最初にそれらを2パターン紹介します。

またその次に、動きとしては問題ないけれど、効率の観点から要考察なものも2つ紹介します。

△1:iter_b が空でない配列の場合

例えば、以下のようなテストケースを考えましょう。

    def test_fib_2
      expected = [5, 8, 13, 21, 34]
      result = enum_diff(fib, [1, 2, 3]).take(5)
      assert_equal(expected, result)
    end

これは fib のうち、「1, 2, 3」を除去して 5 から列挙されることを期待したもの。
期待通り「5, 8, 13, 21, 34, …」と列挙されるコードを送ってくださった方もいらっしゃいましたが、そうじゃない解答がかなり多数ありました。
またその「期待通りじゃない列挙」のパターンがいくつかに分かれていました。

  1. 「1, 1, 2, 3, 5, …」と全て列挙されてしまう。
  2. 「1, 5, 8, 13, 21, …」と、最初に「1」が1個だけ余分に列挙される
  3. 全く列挙されない!

1. の「全て列挙されてしまう」パターンの人は、実装が以下のようになっている方がほとんどでした:

  • iter_bto_enum で変換せずに .next/.peek しようとしている。
  • rescue 節で StopIteration を明示的に指定していない、もしくは NoMethodError を余分に指定してしまっている。

つまり、iter_b[1, 2, 3] という配列の場合には、.next というメソッドは用意されていないので、NoMethodError が発生しますが、それが意図せず捕捉されてしまって「iter_b の終了」と判定されて、iter_a が頭から列挙されてしまった、というワケです。

2. の「最初に『1』が余分に列挙される」パターンは、解答例2の方式で見られるパターンです。
先述の「解答例2」の22行目、以下のようにコメントアウトしてありますよね?

      # enum_b.next

このコメントアウトを外すと再現します!
これ、実は私も問題作成時にハマってたんですよね。あの行を行かした方がパフォーマンスが良いはずだし他のテストコードは通るのですが、第2引数を [1, 2, 3] にしたら期待通りに動かなかった、それでコメントアウトしたんですそう言えば。
でありながらこれを防ぐテストコードを問題に追加するのを忘れた(>_<) これは失敗でした。

なお 3. のパターンは省略します。色々複雑で特殊なパターンなので。

△2:iter_a が有限の場合

これもテストに入れるべきだった(>_<)
例えば↓

    def test_1_10_fib
      expected = [4, 6, 7, 9, 10]
      result = enum_diff((1..10), fib).to_a
      assert_equal(expected, result)
    end

「1, 2, …, 10」からフィボナッチ数を除去、を意図したコード。
ま、こちらに関してはほとんどの方が問題なく期待した動作をするコードとなっていました。
期待通りに動かなかったパターンとしては、

  1. 最後に余分な nil が列挙されてしまう(ただしエラーにはならない)
  2. 全く列挙されない!

どちらも特殊なケースなので、詳細は省略します。

効率1:StopIteration の扱いについて

特に解答例1のパターンで、以下のような解答が多く寄せられました(enum_diffメソッドのみ):

def enum_diff iter_a, iter_b
  return to_enum :enum_diff, iter_a, iter_b unless block_given?
  enum_b = iter_b.to_enum
  iter_a.each do |a|
    begin
      b = enum_b.peek
      while b < a
        enum_b.next
        b = enum_b.peek
      end
      yield a if a < b
    rescue StopIteration
      yield a
    end
  end
end

私の解答例との違いは、ループの中がただの begin〜rescue〜end になっている、ということ。
これでもきちんと正常に動作はします。

でも、上述の「△1:」で例に挙げたような、以下の様なコードを実行する場合、どうなるでしょう?

enum_diff(fib, [1, 2, 3]) do |n|
  p n
end

「5, 8, 13, 21, 34, …」と期待通りに列挙はされるのですが、これらを列挙しているのは、すべて「rescue 節の yield a」です。
つまり、enum_b は3つ列挙したところでもう終了しており、よってそれ以降 .next(および.peek)するたびに StopIteration が発生してしまいます。
つまり、このとき起こっているのは、
「もう除去する必要はないのに一応調べて、やっぱり除去するものがないから yield する」
という処理です。これがこれ以降毎回永遠に起き続けるのです。
日本語の字面を見ただけでも「効率悪そう」ということが分かると思います。

ただ、これも今回用意したテストケースは(最初の1件を除き)iter_b は無限に続くものばかりですし、列挙する件数も多くても20件程度だったりするので、そこまでの問題にはならなかったのです。
でもやはり、長い目で見て効率を考えて、私の解答例のようにフラグを導入した方が良いと思います。

効率2:to_enum はいつやるか?

コメントで、「to_enum を無条件に行うのってどうか? なんらかの判定をして必要なときだけした方が良いのではないか?」というようなご指摘をいただきました。
私の解答例で言えば、解答例1の11行目、解答例2の11・12行目、ですね。
Ruby やってると、できるだけシンプルに書きたくなるので、こういうときは無条件に to_enumEnumerator 化したくなるのですが、パフォーマンスを重視すれば、確かにこれだと少し効率が悪くなります。

例えば to_s メソッドという、オブジェクトを文字列化するメソッドがありますが、これは String クラスでは自分自身を返す(コピーを作らない)ようにオーバーライドされています。
ところが to_enum は、それ自身が Enumerator であっても、新しい Enumerator オブジェクトを生成する(実質、コピーが作られる)ようになっています。
だから Enumerator かどうかを判定して、そうでなかった場合にだけ to_enum する、とした方が全体的にパフォーマンスが良くなるのです。
例えば解答例1なら

def enum_diff iter_a, iter_b
  return to_enum :enum_diff, iter_a, iter_b unless block_given?
  enum_b = iter_b.is_a?(Enumerator) ? iter_b : iter_b.to_enum
  # 以下略

等とする方がより良い(is_a?kind_of? でもOK)、ということになります。

なおダックタイピングの観点から、「next メソッドが存在するかどうかで判定しても良いのでは?」という考え方もあります(一部の方に、フィードバックでこちらをお勧めしてしまいました)。
つまり

def enum_diff iter_a, iter_b
  return to_enum :enum_diff, iter_a, iter_b unless block_given?
  enum_b = iter_b.respond_to?(:next) ? iter_b : iter_b.to_enum
  # 以下略

これでも確かに良いのですが、今回の場合は少し短所がありました。

  • next メソッドを実装している(Enumerator と互換性のない)クラスはけっこうある(例:IntegerStringSymbol…)
  • is_a?(〜) の方が respond_to?(〜) より圧倒的にパフォーマンスが良い

ということで、丁寧に書きたいときや、パフォーマンスを強く意識する場合は、is_a?(Enumerator) で余分な Enumerator が生成されないようにしましょう。

コメント紹介(抜粋)

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

(kazutomi様)
イテレータを直接演算するような技はないかと考えてみましたが、
自分の知識の範囲では思いつきませんでした…

⇒そうですね、そのようなものは私も知りません。
 愚直に組み合わせるしかない、ということもできますし、逆に言えば、
 丁寧に組み合わせれば、工夫次第で色々な新しいイテレータを創出することが出来る、
 とも言えると思います(^-^)

(alluser様)
勉強になります!Lv3もありそうなので楽しみです!

⇒o(^▽^)o
 あ、次は Lv.3 ではなく Lv.99 なのでヨロシク。

(fortissimo1997様)
to_enumの挙動がいまいちつかめず確認に時間がかかりました

⇒他にも「.next や .peek の挙動がなかなか掴めなかった」という方もいらっしゃいました。
 この辺は、色々試してみて慣れていくしかないかもしれません。
 私のこの一連の出題が、勉強の一助になれば幸いです(^-^)

(alluser様(2回目))
頂いたアドバイスを参考にもう一度挑戦してみました、1度目よりも頭が整理出来たような気がします。
丁寧に見て頂いてありがとうございました!

⇒こちらこそ丁寧なお返事、ありがとうございます(^-^)励みになりますo(^▽^)o

(福田摂津守様)
パズルみたいにやっていたら偶然通ったって感じでほぼ理解していません。
解説が聞きたくて恥を偲んで出してみました。

⇒お待たせしました、解説をお送りしています。いかがでしょうか?

(みけCAT様)
《中略》さすがにテストがザルだったといえるのでは…?

⇒せめて「穴あきおたま」とさせてください(>_<)

(kaepa3様)
yieldよりもロジックに苦労してしまい、勉強不足を感じた。

⇒はい、そうです。実は yield の使い方と言うよりロジックの構築をメインに問う問題になっています。
 この問題が勉強の一助になれば幸いです(^-^)

(beforelpkj様)
毎回丁寧なフィードバックを下さりありがとうございます。とても勉強になります!

⇒o(^▽^)o