Rubyで任意のメソッドをメモ化する - ぬいぐるみライフ？
Rubyベストプラクティスの5-4より．メタプログラミングの例として面白かったのでまとめてみる． メモ化とは メモ化とは，引数に対するメソッドの戻り値を保存しておき，再び同じ引数でメソッドが呼び出された時にその値を再利用することにより，同じ計算を何度もすることを防ぐ最適化手法のひとつ．全ての引数に対しメソッドの結果が不変の場合(同じ引数で何度呼び出しても毎回同じ戻り値を返す場合)，メソッドをメモ化することができる． 以下はフィボナッチ数を再帰で計算するメソッドfibの例． def fib(n) (0..1).include?(n) ? n : fib(n-2) + fib(n-1); end この実装の場合，例えばfib(n)はn = 3で5回，n = 4で9回というように，nの値が大きくなるにつれて再帰呼び出し回数がどんどん増え，実行時間が爆発的に増大してしまう．私の環境だとfib(30
動的計画法は再帰で表せ
動的計画法の説明は常に再帰関数で書き表すことにしています．いやゆるメモ化再帰です．参照透過な関数は，同じ引数に対して同じ値を返すので，保存しておけばいいという感覚です．計算量の見積もりも簡単で，引数の異なり数に関数中のループの上限をかければおしまいです．特に再帰で書くことに慣れていれば自明に書けますし，テーブルを使ったDPと違って，ループの順番を意識する必要がありません．このテクニックは学部時代に@ohkuraに教えてもらいました．関数型言語に触れた今でこそ当たり前に見えますが，当時は目から鱗だったのを覚えています． メモ化再帰と不動点に関する@kinabaさんの日記や，プログラミングコンテスト的には@chokudaiさんの記事が参考になります． 今更ですが，ちょっと例で説明します．フィボナッチ数を計算する関数fib(x)は再帰式で，fib(x) = fib(x - 1) + fib(x
Web Site Expert #03[結]2005年8月 - www.textfile.org
配列操作の比較表: Ruby, Python, JavaScript, Perl, C++ / The Best-est Version Control / なぜ vi のカーソル移動は hjkl に割り当てられたか / Autrijus Tang (唐宗漢) / Design your own LEGO kit / こんなLLはXXだ / Memoise (Haskell) / 継続は力なり / 感想をTrackBackするまでがLLDNです / LLDN: トラックバックをお待ちしています:LL Day / OOWeb: シンプルな組み込みJava HTTPサーバ / CVS から Subversion へ (SVN レポジトリの公開) / メモ化(memoization), 再帰関数定義関数, 最小不動点 / Stay Hungry. Stay Foolish. / アーキテクチャ階
[結] 2005年8月 - 結城浩の日記 - テストが困難な性質
目次 2005年8月31日 - Perl版の「メモ化(memoization), 再帰関数定義関数, 最小不動点」 / スマトラ沖地震・津波 / 2005年8月30日 - Windowsで、手早くPerl6で遊ぶ / 他の人から学べない「何か」 / 2005年8月29日 - ミルズの外科手術チーム / 2005年8月27日 - POPFile / 2005年8月26日 - 今日も仕事 / 2005年8月25日 - 今日も仕事 / 2005年8月24日 - 今日も仕事 / 人月はなぜ神話か / 2005年8月23日 - 説明文を書く2つのフェーズ / 秋は勉強の季節 / 2005年8月22日 - 仕事 / プログラマのダイエット / 2005年8月21日 - ジェネリクス・クイズ(2) / 2005年8月19日 - ジェネリクス・クイズ(1) / テストが困難な性質 / 2005年8月18日
最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) - ITmedia エンタープライズ
動的計画法とメモ化再帰 今回は、非常によく用いられるアルゴリズムである、「動的計画法」「メモ化再帰」について説明します。この2つはセットで覚えて、両方使えるようにしておくと便利です。 なお、メモ化再帰に関しては、第5・6回の連載の知識を踏まえた上で読んでいただけると、理解が深まります。まだお読みになっていない方は、この機会にぜひご覧ください。 中学受験などを経験された方であれば、こういった問題を一度は解いたことがあるのではないでしょうか。小学校の知識までで解こうとすれば、少し時間は掛かるかもしれませんが、それでもこれが解けないという方は少ないだろうと思います。 この問題をプログラムで解こうとすると、さまざまな解法が存在します。解き方によって計算時間や有効範囲が大きく変化しますので、それぞれのパターンについて考えます。 以下の説明では、縦h、横wとして表記し、プログラムの実行時間に関しては、
いろんな言語でmemoizeとfix - メモ化と最小不動点の話題
いろんな言語でmemoizeとfix - メモ化と最小不動点の話題 目次 話の発端(k.inabaさん) 反応した人々(言語名順) メモ化と最小不動点の話題 話の発端(k.inabaさん) http://www.kmonos.net/wlog/52.php#_0308050827 http://www.kmonos.net/wlog/52.php#_0212050903 http://www.kmonos.net/wlog/53.php#_0149050905 反応した人々(言語名順) C++: http://d.hatena.ne.jp/Cryolite/20050902#p1 C++: http://d.hatena.ne.jp/Nabetani/20050901#p2 Common Lisp(xyzzy): http://d.hatena.ne.jp/ekamasmi/2005090
たらいを回すならHaskell : 404 Blog Not Found
2006年04月07日22:09 カテゴリLightweight Languages たらいを回すならHaskell たらい回し関数、またはtakと呼ばれる有名な関数が存在する。 C言語による最新アルゴリズム事典 奥村晴彦 同書をお持ちの方は、185ページに乗っている。 実はこれ、Haskellの売り込みには最高の関数なのだ。 ちなみに、これ最後にyを返すバージョンとzを返すバージョンがあるようで、それぞれtakyとtakzと呼ばれている模様。ここではtakyの方を採用。 まずは、私のnative tongueとも言えるperl。 tak.pl #!/usr/bin/perl use strict; use warnings; sub tak{ my ($x, $y, $z) = @_; ($x <= $y) ? $y : tak(tak($x-1, $y, $z), tak($y-1,
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
