0

Python でのメモ化の使用を理解するために、あなたの助けが本当に欲しいです。私は Python が初めてで、この構文を理解する方法がよくわかりません。

def fib_mem(n):
    return fib_mem_helper(n,[0,1]+[-1]*(n-1))

def fib_mem_helper(i,mem):
    if mem[i] == -1:
        mem[i]=fib_mem_helper(i-1,mem) + fib_mem_helper(i-2,mem)
        return mem[i]

これは、メモ化を使用してフィボナッチ数を評価するために見たコードですが、どういう[0,1]+[-1]*(n-1)意味ですか? このタイプの文章が何を表しているのか説明してもらえますか?

4

6 に答える 6

1

[0, 1] + [-1] * (n - 1)は、「2 つのリストを連結します。1 つは[0, 1]で、もう 1 つは-1繰り返しn-1回数です」を意味します。

于 2013-02-17T12:45:20.950 に答える
1

[-1]*5 は、5 つの要素が -1、つまり [-1 -1 -1 -1 -1] である新しいリストを作成します。

[0 1]+[-1]*5 は、[0 1 -1 -1 -1 -1 -1] になる 2 つのリストを追加します。

于 2013-02-17T12:47:27.037 に答える
0

まず、編集した後でも、コードのインデントが間違っていることを言わreturn mem[i]なければなりません。インデントを解除する必要があります。

リスト操作の中で、「+」は連結を意味し、「*」は繰り返しを[0,1]+[-1]*(n-1)意味するため、リストを意味します：[0、1、-1、...、-1]（合計（n-1）負の1）。

詳細説明：

リスト[0, 1, -1, ..., -1]には、計算されたフィボナッチ数列（メモ化）が格納されます。最初は、0と1の2つの有効な値のみが含まれています。すべての「-1」要素は、そのインデックスのシーケンスがまだ計算されていないことを意味します。このメモは、関数の2番目のパラメーターとして渡されますfib_mem_helper。指定されたインデックス（つまりi）のフィボナッチ数が計算されていない場合（テストする場合mem[i] == -1）、fib_mem_helper再帰的に計算してに格納しmem[i]ます。計算されている場合は、再計算せずにメモから戻るだけです。

それが全体の話です。

最後の言葉：

このコードはメモ化を利用していますが、十分に効率的ではありません。実際、が呼び出されるたびに新しいリストが作成されます。fib_memたとえば、fib_mem(8)2回呼び出す場合でも、2回目の呼び出しではリストを再作成し、すべてを新たに再計算する必要があります。その理由は、メモをのスコープ内fib_memに保存するためです。これを修正するには、メモを外部の辞書として保存しますfib_mem。

于 2013-02-17T13:04:55.633 に答える
0

メモ化は、同じ問題の再計算を回避するための手法です。私はあなたの質問に戻りますが、ここに解決策を理解するのがより簡単です。

mem = {0:0, 1:1}

def fib(n):
    global mem
    if mem.get(n,-1) == -1:
        mem[n] = fib(n-1) + fib(n-2)
    return mem[n]

グローバル変数を作成memすることにより、への呼び出し全体でメモ化を利用できますfib()。この行は、の計算がすでに含まれているかどうかをmem.get(n,-1) == -1確認します。その場合、結果を返します。それ以外の場合は、を再帰的に呼び出して計算し、これをに格納します。memnmem[n]fib()fib(n)mem[n]

コードを見ていきましょう。ここでの2番目の引数fib_mem_helper(n,[0,1]+[-1]*(n-1))は、長さが。の[0,1、-1、-1、...]形式のリストを渡します(n+1)。関数内ではfib_mem_helper、このリストは変数によって参照されますmem。mem[i]-1であることが判明した場合、計算しm[i]ます; それ以外の場合は、すでに計算された結果をに使用しmem[i]ます。memへの呼び出し全体で永続化していないfib_mem()ため、実行速度が1桁遅くなります。

于 2013-02-17T13:23:36.150 に答える
0

しかし、奇妙なコーディング。構文エラーのようです。しかし、あなたの質問によると：

[0,1] は 2 つの要素を持つリストで、最初の要素は整数 0 で、2 番目の要素は整数 1 です。

Python でのメモ化を使用したこのような関数の賢明な実装は次のようになります。

def fib(i):
    try:
        return fib._memory[i]
    except KeyError:
        pass
    if i == 1 or i == 2:
        return 1
    else:
        f = fib(i-1) + fib(i-2)
        fib._memory[i] = f
        return f
fib._memory = {}
于 2013-02-17T12:45:28.493 に答える
0

Python での高速化は、特定の関数でメモ化を使用すると、100 万倍以上になる可能性があります。これはフィボナッチ数列の例です。従来の再帰的な方法はこのようなもので、永遠に時間がかかります。

def recursive_fibonacci(number):
    if number==0 or number==1:
        return 1
    return recursive_fibonacci(number-1) + recursive_fibonacci(number-2)

print recursive_fibonacci(50),

メモ化を使用した同じアルゴリズムには、数ミリ秒かかります。自分で試してみてください！

def memoize(f):
    memo={}
    def helper(x):
        if x not in memo:
            memo[x]=f(x)
        return memo[x]
    return helper

@memoize
def recursive_fibonacci(number):
    if number==0 or number==1:
        return 1
    return recursive_fibonacci(number-1) + recursive_fibonacci(number-2)

print recursive_fibonacci(50),
于 2014-11-08T23:30:33.203 に答える