C# メモ化

あいさつ

どうも、はかせです。

今日もILをやろうとネタを集めていたんですが、
そんな中こんな記事を見つけました。

qiita.com

内容はILを使ってメモ化を行うというものです。

そこで一つ私の頭の中にはてなマークがでました。

「メモ化ってなんぞ？」
メモ帳でも出すんか？

この記事では説明されていないので
もしかしたら変数宣言並みにメジャーなものなのかもしれませんが、
私は初見の単語でした。

なので調べてみました。今回はそのまとめです。

メモ化とは？

メモ帳を出すことじゃないですからねw

メモ化ってのはメソッドの返り値をメモ(キャッシュ)して
次回以降同じ引数で呼ばれた場合はキャッシュしたものを返すことで
高速化、最適化を行う技法だそうです。

実際に作ってみる

さてメモ化の正体がキャッシュの応用とわかったところで
カリカリ実装していきましょう。
(キャッシュ系には謎の自信をもつはかせであった)

やることとしては
・引数と返り値をペアでキャッシュ
・メソッドが呼ばれた時キャッシュがあればそれを返すようにする
こんな感じですね。

ではコードです。

using System;
using System.Collections.Generic;
using System.Diagnostics;

namespace ConsoleApp6
{
    class Memoization
    {
        private Dictionary<int, int> memoDic = new Dictionary<int, int>();

        /// <summary>
        /// メモ化した場合の時間計測
        /// </summary>
        /// <param name="title"></param>
        /// <param name="index"></param>
        public void MemoTime(string title, int index)
        {
            Console.WriteLine($"[{title}]");
            var stopwatch = new Stopwatch();
            stopwatch.Start();
            int result = MemoFibonacci(index);
            stopwatch.Stop();
            Console.WriteLine($"Index: {index}");
            Console.WriteLine($"Answer: {result}");
            Console.WriteLine($"Time: {stopwatch.Elapsed}");
            Console.WriteLine("");
        }

        /// <summary>
        /// メモ化しなかった場合の時間計測
        /// </summary>
        /// <param name="title"></param>
        /// <param name="index"></param>
        public void NotMemoTime(string title, int index)
        {
            Console.WriteLine($"[{title}]");
            var stopwatch = new Stopwatch();
            stopwatch.Start();
            int result = NotMemoFibonacci(index);
            stopwatch.Stop();
            Console.WriteLine($"Index: {index}");
            Console.WriteLine($"Answer: {result}");
            Console.WriteLine($"Time: {stopwatch.Elapsed}");
            Console.WriteLine("");
        }

        /// <summary>
        /// メモ化しているメソッド
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        private int MemoFibonacci(int index)
        {
            if (index < 0) throw new ArgumentException();
            //キャッシュの有無によって中に入れるものを変える
            int result = 0;
            //キャッシュされていればそれを返す
            if (memoDic.ContainsKey(index)) result = memoDic[index];
            //無けりゃ素直にメソッド動かす
            else
            {
                result = index < 2 ? index : MemoFibonacci(index - 1) + MemoFibonacci(index - 2);
                memoDic[index] = result;
            }
            return result;
        }

        /// <summary>
        /// メモ化していないメソッド
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        private int NotMemoFibonacci(int index)
        {
            if (index < 0) throw new ArgumentException();
            return index < 2 ? index : NotMemoFibonacci(index - 1) + NotMemoFibonacci(index - 2);
        }
    }
}

Dictionaryで引数と返り値をキャッシュして、
メモ化したメソッド内ではキャッシュの有無で返す値を変えています。

さて実行結果はどうなりますかね。

約2万倍速い・・・！

あとがき

今回はメモ化についてでした。

今回のフィボナッチ数列みたいな
引数に対して返り値が不変なものなら
なんでもメモ化の対象になりえるそうです。
(逆に落ちモノパズルの盤面走査みたいなやつには使えなさそう)

じゃあメモ化は一部の隙もない神的技術かというと
もちろん答えはNoです。
この世に銀の弾丸はない。無常ですね・・・

所詮キャッシュの応用なのでオブジェクトプールとかと同じく
メモリを食います。

メモリ容量と実行速度を天秤にかけて
使うかは決めていく必要がありそうですね。

次回はできたら最初の記事みたいに
このメモ化をILでやってみたいななんて思ってます。
(予定は未定)

それでは今回はこの辺でノシ