「yieldのお勉強 Lv.2」解説(Ruby編) #CodeIQ
先日、CodeIQ の以下の問題が、公開終了となりました。
たくさんの挑戦、ありがとうございます。
- yieldのお勉強 Lv.2 (Ruby編)( https://codeiq.jp/ace/antimon2/q1010 )
(すでに問題の公開は終了していますので、上記 URL で問題詳細を見ることはできません)
ということで、少々遅れましたが、恒例の解説記事です。
問題文は省略します(挑戦者だけの特典♪)が、Lv.1 と同様、問題は、一部が未実装のプログラムを実装してテストを全て通るようにする、というもの。
以下に、問題プログラムと解答例を示します。
問題プログラムと解答例
まずは、問題プログラム。
問題プログラム:
enum_diff
というメソッドが仮実装になっています(単純に第1引数 iter_a
を列挙するだけになっています)。
これを適切に実装し直して、「iter_a
に存在し、iter_b
に出てこない要素(整数)を列挙するメソッド」にする、というもの。
ただし簡単のために、以下の仮定を設定:
- (
iter_a
もiter_b
も)要素は全て整数値で、値が増加することはあっても減少することはない(広義の単調増加)
またコメント中に「解き方は大きく分けて2種類」と書いてあります。これは私の想定解答例が2つと言うこともありますが、実際にそのアプローチが少し違うものになっています。
その解答例を以下に示します。
解答例1:
解答例1は、iter_a
を each
メソッドで要素を列挙しながら、その中で(Enumerator
化した)iter_b
の peek
および next
メソッドを利用して値を取り出したり次の値を取得したりして、同じものが存在したら yield
しない、という方針。
一度でも StopIteration
が発生したら、フラグ変数を true
に設定して、以降無駄な peek
や next
メソッドによる StopIteration
発生を抑制しています。
わざわざ変数に代入したりして分かりやすく書いたつもりなので、難しいことはないですよね?
解答例2:
解答例2は、iter_a
も iter_b
も Enumerator
化し、loop do〜end
のループ内で両方を peek
および next
メソッドを利用して比較しながら処理を進める、という方針。
ポイントは、begin〜rescue〜end
を利用していない、という点。
問題中では一切触れていなかったのですが、loop do〜end
というループは、内部で StopIteration
が発生すると、それを適切に捕捉し、そこでループを中断してくれます。ループの外に StopIteration
は raise
しません。
この仕様を活かしました。
なお、今回用意した解答例は、説明のための利便性を重視して丁寧に書きましたが、どちらももっとコンパクトに書くことも出来ます。例えば、
解答例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, 2, 3, 5, …」と全て列挙されてしまう。
- 「1, 5, 8, 13, 21, …」と、最初に「1」が1個だけ余分に列挙される
- 全く列挙されない!
1. の「全て列挙されてしまう」パターンの人は、実装が以下のようになっている方がほとんどでした:
iter_b
をto_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」からフィボナッチ数を除去、を意図したコード。
ま、こちらに関してはほとんどの方が問題なく期待した動作をするコードとなっていました。
期待通りに動かなかったパターンとしては、
- 最後に余分な
nil
が列挙されてしまう(ただしエラーにはならない) - 全く列挙されない!
どちらも特殊なケースなので、詳細は省略します。
効率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_enum
で Enumerator
化したくなるのですが、パフォーマンスを重視すれば、確かにこれだと少し効率が悪くなります。
例えば 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
と互換性のない)クラスはけっこうある(例:Integer
、String
、Symbol
…)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