セカイノカタチスマートフォン用の表示で見るセカイノカタチ世界のカタチを探求するブログ。関数型言語に興味があり、HaskellやScalaを勉強中。プログラミングさて、前回の続きです。満たす(x,y)を全て挙げる関数の設計について話題にしています。一つの解き方として、鞍型探索というものの説明を追いかけました。鞍型探索とは、表の左上を基点にじわじわxとyを増加しながら答えを探るやり方で、最適解が出たところで一件落着!と、思いきやMaryが「分割統治でやるとどうなるでしょう?」と話を蒸し返したところで、心折れて一旦終了しました。分割統治による解法Maryの提案はこうです。(p,q)を調べ、(z>),(z==),(z<)の場合で、矩形をごっそり削ることができるため、これを再帰的に繰り返すことによって、効率よく解を求められるのではないかという発想のようです。ここから4人は、この方法の評価回数を見積もり始めます。2ページ半に渡り計算をした結果、Maryが「Jackの分割統治法は本当は必要ではないと思います。」と言い放ちます(Mary鬼だな。お前が言い出しっぺだろ!?)。「各行で二分探索すればいいじゃん」という身も蓋もないシンプルな解法を思いつきます。(^^;コードを示します。z)考え方がシンプルな割に、コードはえらく複雑ですね。(^^;;実行結果を表にすると、確かになんとなく二分探索している感じがしますね。二分探索には、前回作成したbsearchをそのまま流用しています。ScalaにしてみるScalaのコードに直します。言っても、単純に置き換えただけです。z)}再帰がtailrecになっていないので、規模が大きいとスタックがアレして落ちるかもしれません(おぃ)。(^^;最後にベンチマークが載っていて、分割統治の方が速いことが多いようです(必ず速いわけではない)。はてなブログProシステム開発の世界で15年の山の民による、世界のカタチを探求するブログ。(4)はてなブログをはじめよう!qtamakiさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。