38

任意の数の引数を持つ関数のメモ化インターフェイスを作成しようとしていますが、悲惨なことに失敗しています。私のソリューションはあまり柔軟ではないように感じます。実行時に自動的にメモ化される関数のインターフェイスを定義しようとしましたが、各関数はこのインターフェイスを実装する必要があります。これは、2つのパラメーターの指数移動平均関数を使用した例です。

class EMAFunction:IFunction
{
    Dictionary<List<object>, List<object>> map;

    class EMAComparer : IEqualityComparer<List<object>>
    {
        private int _multiplier = 97;

        public bool Equals(List<object> a, List<object> b)
        {
            List<object> aVals = (List<object>)a[0];
            int aPeriod = (int)a[1];

            List<object> bVals = (List<object>)b[0];
            int bPeriod = (int)b[1];

            return (aVals.Count == bVals.Count) && (aPeriod == bPeriod);
        }

        public int GetHashCode(List<object> obj)
        {
            // Don't compute hash code on null object.
            if (obj == null)
            {
                return 0;
            }

            List<object> vals = (List<object>) obj[0];
            int period = (int) obj[1];

            return (_multiplier * period.GetHashCode()) + vals.Count;

        }
    }

    public EMAFunction()
    {
        NumParams = 2;
        Name = "EMA";
        map = new Dictionary<List<object>, List<object>>(new EMAComparer());
    }
    #region IFunction Members

    public int NumParams
    {
        get;
        set;
    }

    public string Name
    {
        get;
        set;
    }

    public object Execute(List<object> parameters)
    {
        if (parameters.Count != NumParams)
            throw new ArgumentException("The num params doesn't match!");

        if (!map.ContainsKey(parameters))
        {
            //map.Add(parameters,
            List<double> values = new List<double>();
            List<object> asObj = (List<object>)parameters[0];
            foreach (object val in asObj)
            {
                values.Add((double)val);
            }
            int period = (int)parameters[1];

            asObj.Clear();
            List<double> ema = TechFunctions.ExponentialMovingAverage(values, period);
            foreach (double val in ema)
            {
                asObj.Add(val);
            }
            map.Add(parameters, asObj);
        }
        return map[parameters];
    }

    public void ClearMap()
    {
        map.Clear();
    }

    #endregion
}

これが私の関数のテストです：

private void MemoizeTest()
{
    DataSet dataSet = DataLoader.LoadData(DataLoader.DataSource.FROM_WEB, 1024);
    List<String> labels = dataSet.DataLabels;

    Stopwatch sw = new Stopwatch();
    IFunction emaFunc = new EMAFunction();
    List<object> parameters = new List<object>();
    int numRuns = 1000;
    long sumTicks = 0;
    parameters.Add(dataSet.GetValues("open"));
    parameters.Add(12);

    // First call

    for(int i = 0; i < numRuns; ++i)
    {
        emaFunc.ClearMap();// remove any memoization mappings
        sw.Start();
        emaFunc.Execute(parameters);
        sw.Stop();
        sumTicks += sw.ElapsedTicks;
        sw.Reset();
    }
    Console.WriteLine("Average ticks not-memoized " + (sumTicks/numRuns));


    sumTicks = 0;
    // Repeat call
    for (int i = 0; i < numRuns; ++i)
    {
        sw.Start();
        emaFunc.Execute(parameters);
        sw.Stop();
        sumTicks += sw.ElapsedTicks;
        sw.Reset();
    }
    Console.WriteLine("Average ticks memoized " + (sumTicks/numRuns));
}

更新：
私のn00bishエラーを指摘してくれてありがとう...私はいつもストップウォッチでリセットを呼び出すのを忘れています！

メモ化への別のアプローチも見ました...これはn引数のメモ化を提供しませんが、関数ごとにクラスを作成する必要があるため、インターフェイスを使用したアプローチはそれほど有利ではありません。これらのアイデアをより堅牢なものにマージできる合理的な方法はありますか？ユーザーが使用する関数ごとにクラスを作成することなく、関数を簡単にメモ化できるようにしたいと思います。

4

5 に答える 5

87

これはどう？まず、1つの引数のメモ化を作成します。

static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
    var d = new Dictionary<A, R>();
    return a=> 
    {
        R r;
        if (!d.TryGetValue(a, out r))
        {
            r = f(a);
            d.Add(a, r);
        }
        return r;
    };
}

簡単です。次に、関数タプリファイアを記述します。

static Func<Tuple<A, B>, R> Tuplify<A, B, R>(this Func<A, B, R> f)
{
    return t => f(t.Item1, t.Item2);
}

そしてdetuplifier：

static Func<A, B, R> Detuplify<A, B, R>(this Func<Tuple<A, B>, R> f)
{
    return (a, b) => f(Tuple.Create(a, b));
}

そして今、2つの引数のメモ化は簡単です：

static Func<A, B, R> Memoize<A, B, R>(this Func<A, B, R> f)
{
    return f.Tuplify().Memoize().Detuplify();
}

3つの引数のメモ化機能を作成するには、次のパターンに従います。3つのタプリファイア、3つのアンタプリファイア、および3つのメモ化機能を作成します。

もちろん、それらが必要ない場合は、タプリファイアを名目上の方法にする必要はありません。

static Func<A, B, R> Memoize<A, B, R>(this Func<A, B, R> f)
{
    Func<Tuple<A, B>, R> tuplified = t => f(t.Item1, t.Item2);
    Func<Tuple<A, B>, R> memoized = tuplified.Memoize();
    return (a, b) => memoized(Tuple.Create(a, b));
}

更新：タプルタイプがない場合の対処方法を尋ねます。あなたはあなた自身を書くことができます。それは難しいことではありません。または、匿名タイプを使用できます。

static Func<T, R> CastByExample<T, R>(Func<T, R> f, T t) { return f; }

static Func<A, B, R> Memoize<A, B, R>(this Func<A, B, R> f)
{
    var example = new { A=default(A), B=default(B) };
    var tuplified = CastByExample(t => f(t.A, t.B), example);
    var memoized = tuplified.Memoize();
    return (a, b) => memoized(new {A=a, B=b});
}

スリック、え？

更新：C＃7には、言語に組み込まれた値タプルが含まれるようになりました。自分でローリングしたり、匿名タイプを使用したりするのではなく、それらを使用してください。

于 2010-05-17T20:37:38.080 に答える
3

StopWatch.Stopはストップウォッチをリセットしないため、開始/停止ごとに時間を累積しています。

例えば

  Stopwatch sw = new Stopwatch();

  sw.Start();
  System.Threading.Thread.Sleep(100);
  sw.Stop();
  Debug.WriteLine(sw.ElapsedTicks);

  sw.Start();
  System.Threading.Thread.Sleep(100);
  sw.Stop();
  Debug.WriteLine(sw.ElapsedTicks);

次の結果が得られます

228221
454626

StopWatch.Restart（Framework 4.0）を使用して毎回ストップウォッチを再起動できます。Framework4.0でない場合は、を使用StopWatch.Resetしてストップウォッチをリセットできます。

于 2010-05-17T19:39:44.313 に答える
3

sw.Reset()まず、テストの合間に呼び出す必要があります。それ以外の場合、2番目のテストの結果は最初のテストからの時間に追加されます。

vals.GetHashCode()次に、比較対象のオーバーライドで使用するべきではありません。これにより、オーバーライドGetHashCode()の評価対象となるオブジェクトに対して異なるハッシュコードを取得することになります。今のところ、コードを均等に分散させようとするのではなく、同等のオブジェクトが常に同じハッシュコードを取得するようにすることを心配します。ハッシュコードが一致しない場合、は呼び出されないため、同じパラメーターを複数回処理することになります。trueEqualsEquals

于 2010-05-17T19:42:14.980 に答える
2

（タプルと匿名タイプの）代替アプローチは次のようになります。

static void Main(string[] args)
{
    var func = Memoize<int, int, int>(Func);

    Console.WriteLine(func(3)(4));
    Console.WriteLine(func(3)(5));
    Console.WriteLine(func(2)(5));
    Console.WriteLine(func(3)(4));
}

//lets pretend this is very-expensive-to-compute function
private static int Func(int i, int j)
{
    return i + j;
}

private static Func<TArg1, Func<TArg2, TRes>> Memoize<TArg1, TArg2, TRes>(Func<TArg1, TArg2, TRes> func)
{
     Func<TArg1, Func<TArg2, TRes>> func1 = 
        Memoize((TArg1 arg1) => Memoize((TArg2 arg2) => func(arg1, arg2)));

    return func1;
}

private static Func<TArg, TRes> Memoize<TArg, TRes>(Func<TArg, TRes> func)
{
    var cache = new Dictionary<TArg, TRes>();

    return arg =>
    {
        TRes res;

        if( !cache.TryGetValue(arg, out res) )
        {
            Console.WriteLine("Calculating " + arg.ToString());

            res = func(arg);

            cache.Add(arg, res);
        }
        else
        {
            Console.WriteLine("Getting from cache " + arg.ToString());
        }

        return res;
    };
}

これらの2つのメモ化機能に基づいて、必要な数の引数の拡張機能を簡単に構築できます。

于 2012-03-15T07:53:08.450 に答える
1

私は最初、パラメータなし関数の抽象的なメモ化方法を探してここに来ました。これは質問に対する正確な答えではありませんが、他の誰かが単純なケースを探しに来た場合に備えて、私の解決策を共有したいと思いました。

public static class MemoizationExtensions
{
    public static Func<R> Memoize<R>(this Func<R> f)
    {
        bool hasBeenCalled = false; // Used to determine if we called the function and the result was the same as default(R)
        R returnVal = default(R);
        return () =>
        {
            // Should be faster than doing null checks and if we got a null the first time, 
            // we really want to memoize that result and not inadvertently call the function again.
            if (!hasBeenCalled)
            {
                hasBeenCalled = true;
                returnVal = f();
            }
            return returnVal;
        };
    }
}

LinqPadを使用する場合は、次のコードを使用して、LinqPadの超クールなダンプメソッドを使用して機能を簡単にテストできます。

new List<Func<object>>(new Func<object>[] {
        () => { "Entered func A1".Dump(); return 1; },
        () => { "Entered func A2".Dump(); return default(int); },
        () => { "Entered func B1".Dump(); return String.Empty; },
        () => { "Entered func B2".Dump(); return default(string); },
        () => { "Entered func C1".Dump(); return new {Name = String.Empty}; },
        () => { "Entered func C2".Dump(); return null; },
    })
    .ForEach(f => {
        var f1 = MemoizationExtensions.Memoize(f);
        Enumerable
            .Range(1,3)
            .Select(i=>new {Run=i, Value=f1()})
            .Dump();
    });

PS LinqPadスクリプトのコードにMemoizationExtensionsクラスを含める必要があります。そうしないと、機能しません。

于 2013-01-16T15:28:01.747 に答える