この関数呼んだら毎回超モッサリするんだけど？だったらメモ化とかしてみたら？というただのメモ

メモ化とはプログラムを高速化するための最適化技法のひとつで、
関数呼び出しの結果を保持しておいて再利用するというものです。
1度呼び出された関数が再度呼び出されたときに再計算をせずに、保持しておいた値を再利用する手法です。
具体的には、キーと値のペアを保持しておくためのコレクションを用意し、
クロージャを用いて、関数の結果が静的スコープ内で解決されるように実装するようなもののことをそう呼びます。
サンプルとしてC#、VB10、F#についてコードを書きました。

たとえば、以下のようなものがメモ化です。

C#でメモ化

using System;
using System.Linq;
using System.Threading;
using System.Collections.Generic;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main()
        {
            Func<int, int> memofunc = Memoization(x => Heviy(x));
            foreach (var i in Enumerable.Range(0, 5))
                Console.WriteLine(memofunc(i));
            foreach (var i in Enumerable.Range(0, 5))
                Console.WriteLine(memofunc(i));

            Console.ReadKey();
        }

        static Func<int, int> Memoization(Func<int, int> source)
        {
            var dic = new Dictionary<int, int>();
            return x =>
            {
                if (dic.ContainsKey(x)) return dic[x];
                return dic[x] = source(x);
            };
        }

        static int Heviy(int i)
        {
            Thread.Sleep(1000);
            return i + 1;
        }
    }
}

VB10でメモ化

Imports System
Imports System.Linq
Imports System.Threading
Imports System.Collections.Generic

Namespace ConsoleApplication1

    Module Module1

        Sub Main()
            Dim memofunc As Func(Of Integer, Integer) = Memoization(Function(x) (Heviy(x)))
            For Each i In Enumerable.Range(0, 5)
                Console.WriteLine(memofunc(i))
            Next
            For Each i In Enumerable.Range(0, 5)
                Console.WriteLine(memofunc(i))
            Next

            Console.ReadKey()
        End Sub

        Function Memoization(ByVal source As Func(Of Integer, Integer)) As Func(Of Integer, Integer)
            Dim dic As New Dictionary(Of Integer, Integer)()
            Return Function(x)
                       If dic.ContainsKey(x) Then Return dic(x)
                       dic(x) = source(x)
                       Return dic(x)
                   End Function
        End Function

        Function Heviy(ByVal i As Integer) As Integer
            Thread.Sleep(1000)
            Return i + 1
        End Function

    End Module

End Namespace

F#でメモ化

#light
open System
open System.Threading
open System.Collections.Generic

let memoization source = 
  let dic = new Dictionary<'a,'b>()  
  fun x -> match dic.ContainsKey(x) with 
           | true -> dic.[x]
           | _    -> dic.[x] <- source x
                     dic.[x]

let Heviy i = 
  Thread.Sleep 1000
  i + 1
 
let Main =
  let memofunc = memoization (fun x -> Heviy x)
  for i=0 to 4 do Console.WriteLine(memofunc(i))
  for i=0 to 4 do Console.WriteLine(memofunc(i))
let k = Console.ReadKey ()

上記の例はメモ化のサンプルコードとしてはイマイチーな感じですが、
なんとなくエッセンスは感じられるのではないでしょうか。
というわけで皆さん。メモ化を検討するなどしてモッサリする関数とはおさらばしましょう。
不幸をもたらすモッサリ関数は絶対に作らないでください。zeclからのお願いです。

VB10の複数行ラムダきもかわいい(笑