複数キーのルックアップテーブル

メモ化では、関数／メソッドの呼び出し結果を、そのときの引数とあわせて覚えておく必要があります。

記憶域としては、連想配列、すなわちDictionary<TKey, TValue>クラスをルックアップテーブルとして使うのがよさそうですが、関数／メソッドのアリティは単項とは限らないので、複数のキーに対応しなければなりません。

一番シンプルなのは、キーとしてタプルを使う方法です。タプルはObject.Equals()メソッドをオーバーライドしていて、格納している構成要素がすべて一致すればtrueが返ります。同じようにObject.GetHashCode()メソッドもオーバーライドされています。つまり、Dictionary<TKey, TValue>のキーとして使うことができます。

ただし、既定の実装では、構成要素を比較する時にobject型にキャストして比較します。構成要素が値型のときはボックス化されてしまうこともあり、効率はあまりよくありません。

効率を良くしたい場合は、タプル用の等値比較オブジェクト、すなわちIEqualityComparer<T>インターフェースの実装クラスを用意して、Dictionary<TKey, TValue>のコンストラクタに引数として渡すことになります。

タプルはIStructuralEquatableインターフェースを実装しているので、IEqualityComparer<T>インターフェースの実装クラスの型制約にIStructuralEquatableを付けておけばいいように思えますが、それも効率はよくありません。効率のためには、タプルの要素数ごとに別のクラスが必要になります。たとえば、要素数4のタプルであればこんな感じです。

TupleComparer.cs

class TupleComparer<T1, T2, T3, T4> : EqualityComparer<Tuple<T1, T2, T3, T4>>
{
    private static readonly IEqualityComparer<T1> comparer1
        = EqualityComparer<T1>.Default;
    private static readonly IEqualityComparer<T2> comparer2
        = EqualityComparer<T2>.Default;
    private static readonly IEqualityComparer<T3> comparer3
        = EqualityComparer<T3>.Default;
    private static readonly IEqualityComparer<T4> comparer4
        = EqualityComparer<T4>.Default;
 
    public override bool Equals(Tuple<T1, T2, T3, T4> x, Tuple<T1, T2, T3, T4> y)
    {
        if (x == null || y == null) return (x == y);
        return (comparer1.Equals(x.Item1, y.Item1)
            && comparer2.Equals(x.Item2, y.Item2)
            && comparer3.Equals(x.Item3, y.Item3)
            && comparer4.Equals(x.Item4, y.Item4));
    }
 
    public override int GetHashCode(Tuple<T1, T2, T3, T4> obj)
    {
        if (obj == null) return 0;
        var hash = comparer1.GetHashCode(obj.Item1);
        hash = (31 * hash) ^ comparer2.GetHashCode(obj.Item2);
        hash = (31 * hash) ^ comparer3.GetHashCode(obj.Item3);
        hash = (31 * hash) ^ comparer4.GetHashCode(obj.Item4);
        return hash;
    }
}