11

私は三角数を見つける関数を書いています、そしてそれを書く自然な方法は再帰的にです：

function triangle (x)
   if x == 0 then return 0 end
   return x+triangle(x-1)
end

しかし、最初の100,000の三角数を計算しようとすると、しばらくするとスタックオーバーフローが発生して失敗します。これはメモ化するのに理想的な関数ですが、渡した関数をメモ化するソリューションが必要です。

4

15 に答える 15

9

Mathematica には、ハッシュと関数呼び出しが同じ構文を使用するという事実に依存して、メモ化を行うための特に洗練された方法があります。

triangle[0] = 0;
triangle[x_] := triangle[x] = x + triangle[x-1]

それでおしまい。これが機能するのは、パターン マッチング関数呼び出しのルールが、より一般的な定義の前に常により具体的な定義を使用するようになっているためです。

もちろん、指摘されているように、この例には閉じた形式の解がありますtriangle[x_] := x*(x+1)/2。フィボナッチ数は、メモ化を追加することで劇的なスピードアップが得られる典型的な例です。

fib[0] = 1;
fib[1] = 1;
fib[n_] := fib[n] = fib[n-1] + fib[n-2]

それも閉じた形式の同等物を持っていますが、厄介ではありますが: http://mathworld.wolfram.com/FibonacciNumber.html

「ループを使用するだけ」でよいため、メモ化には不適切であると示唆した人には同意しません。メモ化のポイントは、繰り返し関数呼び出しが O(1) 時間であることです。これは O(n) よりもはるかに優れています。実際、メモ化された実装がクローズド フォームの実装よりも優れたパフォーマンスを発揮するシナリオを作成することもできます。

于 2008-10-06T02:17:23.290 に答える
6

また、元の問題に対して間違った質問をしています;）

これはその場合のより良い方法です：

三角形 (n) = n * (n - 1) / 2

さらに、式にそのようなきちんとした解決策がないと仮定すると、ここではメモ化はまだ不十分なアプローチになります。この場合、単純なループを作成するだけでよいでしょう。詳細な議論については、この回答を参照してください。

于 2008-09-24T20:56:50.580 に答える
5

私はこのようなものがLuaの可変引数リストで動作するはずだと思います：

local function varg_tostring(...)
    local s = select(1, ...)
    for n = 2, select('#', ...) do
        s = s..","..select(n,...)
    end
    return s
end

local function memoize(f)
    local cache = {}
    return function (...)
        local al = varg_tostring(...)
        if cache[al] then
            return cache[al]
        else
            local y = f(...)
            cache[al] = y
            return y
        end
    end
end

おそらく、__ tostringを使用したメタテーブルを使用して巧妙なことを実行し、引数リストをtostring（）で変換できるようにすることもできます。ああ、可能性。

于 2008-09-26T20:15:21.837 に答える
5

C＃3.0では、再帰関数の場合、次のようなことができます。

public static class Helpers
{
    public static Func<A, R> Memoize<A, R>(this Func<A, Func<A,R>,  R> f)
    {
        var map = new Dictionary<A, R>();
        Func<A, R> self = null;
        self = (a) =>
        {
            R value;
            if (map.TryGetValue(a, out value))
                return value;
            value = f(a, self);
            map.Add(a, value);
            return value;
        };
        return self;
    }        
}

次に、次のようなメモ化されたフィボナッチ関数を作成できます。

var memoized_fib = Helpers.Memoize<int, int>((n,fib) => n > 1 ? fib(n - 1) + fib(n - 2) : n);
Console.WriteLine(memoized_fib(40));
于 2011-11-20T20:13:31.507 に答える
4

Scala の場合 (未テスト):

def memoize[A, B](f: (A)=>B) = {
  var cache = Map[A, B]()

  { x: A =>
    if (cache contains x) cache(x) else {
      val back = f(x)
      cache += (x -> back)

      back
    }
  }
}

これはアリティ 1 の関数に対してのみ機能することに注意してください。ただし、カリー化を使用すると機能させることができます。より微妙な問題はmemoize(f) != memoize(f)、すべての関数の場合fです。これを修正する非常に卑劣な方法の 1 つは、次のようなものです。

val correctMem = memoize(memoize _)

これがコンパイルされるとは思いませんが、アイデアを示しています。

于 2008-09-24T20:54:17.637 に答える
4

更新: コメント作成者は、メモ化が再帰を最適化する良い方法であると指摘しています。確かに、私は通常、一般化されたメモ化を構築するのがそれほど簡単ではない言語 (C#) で作業しているため、これまで考えたことがありませんでした。その一粒の塩を念頭に置いて、以下の投稿を読んでください。

Luke はおそらくこの問題に対する最も適切な解決策を持っていると思いますが、メモ化は通常、スタック オーバーフローの問題に対する解決策ではありません。

スタック オーバーフローは、通常、再帰がプラットフォームの処理能力を超えた場合に発生します。言語は、再帰呼び出しの新しいコンテキストを作成するのではなく、現在の呼び出しのコンテキストを再利用する「末尾再帰」をサポートする場合があります。しかし、主流の言語/プラットフォームの多くはこれをサポートしていません。たとえば、C# には末尾再帰に対する固有のサポートはありません。.NET JITter の 64 ビット バージョンは、IL レベルでの最適化として適用できますが、32 ビット プラットフォームをサポートする必要がある場合、これはほとんど役に立ちません。

言語が末尾再帰をサポートしていない場合、スタック オーバーフローを回避するための最良のオプションは、明示的なループに変換するか (はるかにエレガントではありませんが、場合によっては必要になります)、この問題に対して提供されている Luke などの非反復アルゴリズムを見つけることです。

于 2008-09-24T21:10:04.917 に答える
3 
function memoize (f)
   local cache = {}
   return function (x)
             if cache[x] then
                return cache[x]
             else
                local y = f(x)
                cache[x] = y
                return y
             end
          end
end

triangle = memoize(triangle);

スタックオーバーフローを回避するには、三角形をシードする必要があることに注意してください。

于 2008-09-24T20:49:08.303 に答える
2

この質問に触発されて、(さらに別の) 柔軟な memoize 機能を Lua に実装しました。

https://github.com/kikito/memoize.lua

主な利点:

  • 可変数の引数を受け入れます
  • tostring を使用しません。代わりに、パラメーターを使用してキャッシュをトラバースし、ツリー構造でキャッシュを編成します。
  • 複数の値を返す関数で問題なく動作します。

ここにコードを参照として貼り付けます。

local globalCache = {}

local function getFromCache(cache, args)
  local node = cache
  for i=1, #args do
    if not node.children then return {} end
    node = node.children[args[i]]
    if not node then return {} end
  end
  return node.results
end

local function insertInCache(cache, args, results)
  local arg
  local node = cache
  for i=1, #args do
    arg = args[i]
    node.children = node.children or {}
    node.children[arg] = node.children[arg] or {}
    node = node.children[arg]
  end
  node.results = results
end


-- public function

local function memoize(f)
  globalCache[f] = { results = {} }
  return function (...)
    local results = getFromCache( globalCache[f], {...} )

    if #results == 0 then
      results = { f(...) }
      insertInCache(globalCache[f], {...}, results)
    end

    return unpack(results)
  end
end

return memoize
于 2011-04-20T22:07:37.087 に答える
2

引数を文字列に変換せずに機能するものを次に示します。唯一の注意点は、nil 引数を処理できないことです。nilしかし、受け入れられた解決策では、値と文字列を区別できないため、"nil"おそらく問題ありません。

local function m(f)
  local t = { }
  local function mf(x, ...) -- memoized f
    assert(x ~= nil, 'nil passed to memoized function')
    if select('#', ...) > 0 then
      t[x] = t[x] or m(function(...) return f(x, ...) end)
      return t[x](...)
    else
      t[x] = t[x] or f(x)
      assert(t[x] ~= nil, 'memoized function returns nil')
      return t[x]
    end
  end
  return mf
end
于 2010-09-06T19:36:36.857 に答える
1

Perl では、一般的なメモ化は簡単に実現できます。Memoize モジュールは perl コアの一部であり、信頼性が高く、柔軟性があり、使いやすいです。

そのマンページの例：

# This is the documentation for Memoize 1.01
use Memoize;
memoize('slow_function');
slow_function(arguments);    # Is faster than it was before

実行時に関数のメモ化を追加、削除、およびカスタマイズできます。カスタム memento 計算用のコールバックを提供できます。

Memoize.pm には memento キャッシュを永続化するための機能さえあるので、プログラムを呼び出すたびに再充填する必要はありません!

ドキュメントは次のとおりです: http://perldoc.perl.org/5.8.8/Memoize.html

于 2008-11-04T20:26:01.700 に答える
1

役立つ場合は、一般的な C# 3.0 の実装を次に示します。

public static class Memoization
{
    public static Func<T, TResult> Memoize<T, TResult>(this Func<T, TResult> function)
    {
        var cache = new Dictionary<T, TResult>();
        var nullCache = default(TResult);
        var isNullCacheSet = false;
        return  parameter =>
                {
                    TResult value;

                    if (parameter == null && isNullCacheSet)
                    {
                        return nullCache;
                    }

                    if (parameter == null)
                    {
                        nullCache = function(parameter);
                        isNullCacheSet = true;
                        return nullCache;
                    }

                    if (cache.TryGetValue(parameter, out value))
                    {
                        return value;
                    }

                    value = function(parameter);
                    cache.Add(parameter, value);
                    return value;
                };
    }
}

（フランスのブログ記事より引用）

于 2008-09-24T20:53:01.493 に答える
1

さまざまな言語でメモ化を投稿するという流れで、言語を変更しない C++ の例で @onebyone.livejournal.com に返信したいと思います。

まず、単一引数関数のメモライザー:

template <class Result, class Arg, class ResultStore = std::map<Arg, Result> >
class memoizer1{
public:
    template <class F>
    const Result& operator()(F f, const Arg& a){
        typename ResultStore::const_iterator it = memo_.find(a);
        if(it == memo_.end()) {
            it = memo_.insert(make_pair(a, f(a))).first;
        }
        return it->second;
    }
private:
    ResultStore memo_;
};

memoizer のインスタンスを作成し、それに関数と引数を与えるだけです。2 つの異なる関数間で同じメモを共有しないように注意してください (ただし、同じ関数の異なる実装間で共有することはできます)。

次に、ドライバー関数と実装です。ドライバー関数だけが public int fib(int); である必要があります。// ドライバー int fib_(int); // 実装

実装:

int fib_(int n){
    ++total_ops;
    if(n == 0 || n == 1) 
        return 1;
    else
        return fib(n-1) + fib(n-2);
}

そしてドライバーは、メモする

int fib(int n) {
    static memoizer1<int,int> memo;
    return memo(fib_, n);
}

codepad.org の出力を示すパーマリンク。正確性を検証するために呼び出し回数が測定されます。(ここに単体テストを挿入...)

これは、1 つの入力関数のみを記憶します。複数の引数またはさまざまな引数の一般化は、読者の演習として残されています。

于 2008-09-27T22:31:58.270 に答える
0

アイデアを拡張して、2つの入力パラメーターで関数をメモ化することも可能です。

function memoize2 (f)
   local cache = {}
   return function (x, y)
             if cache[x..','..y] then
                return cache[x..','..y]
             else
                local z = f(x,y)
                cache[x..','..y] = z
                return z
             end
          end
end

キャッシュアルゴリズムではパラメータの順序が重要であることに注意してください。メモ化する関数でパラメータの順序が重要でない場合は、キャッシュをチェックする前にパラメータを並べ替えることで、キャッシュヒットが発生する可能性が高くなります。

ただし、一部の機能は有益にメモ化できないことに注意することが重要です。最大公約数を見つけるための再帰的ユークリッドアルゴリズムを高速化できるかどうかを確認するために、 memoize2を作成しました。

function gcd (a, b) 
   if b == 0 then return a end
   return gcd(b, a%b)
end

結局のところ、gcdはメモ化にうまく反応しません。それが行う計算は、キャッシングアルゴリズムよりもはるかに安価です。多数の場合は、かなり迅速に終了します。しばらくすると、キャッシュが非常に大きくなります。このアルゴリズムはおそらく可能な限り高速です。

于 2008-09-26T18:50:05.457 に答える
0

これを繰り返さないでください。x*(x+1)/2 式を使用するか、単純に値を反復してメモしてください。

int[] memo = new int[n+1];
int sum = 0;
for(int i = 0; i <= n; ++i)
{
  sum+=i;
  memo[i] = sum;
}
return memo[n];
于 2013-04-06T01:45:43.673 に答える
0

再帰は必要ありません。n 番目の三角形の数は n(n-1)/2 なので...

public int triangle(final int n){
   return n * (n - 1) / 2;
}
于 2011-12-06T04:42:46.383 に答える