1

これが私のコードです。

import timeit

fac_mem = {}

def fac(k):
  if k < 2: return 1
  if k not in fac_mem:
    fac_mem[k] = k*fac(k-1)
return fac_mem[k]

def fact(k):
  if k < 2: return 1
  return k*fact(k-1)

if __name__ == "__main__": 
  print timeit.timeit("fac(7)","from __main__ import fac")
  print timeit.timeit("fact(7)","from __main__ import fact")
  print timeit.timeit("fac(70)","from __main__ import fac")
  print timeit.timeit("fact(70)","from __main__ import fact")

ここに出力があります

0.236774399224
0.897065011572
0.217623144304
14.1952226578

さて、プログラムが実行される前は、dict は空ですが、メモ化によって階乗が高速化されるのはなぜでしょうか? つまり、この 2 つのバージョンの呼び出し回数は同じです。次に、コードを少し変更し、辞書を関数に移動しました。

def fac(k):
  fac_mem = {}
  if k < 2: return 1
  if k not in fac_mem:
    fac_mem[k] = k*fac(k-1)
  return fac_mem[k]

出力が変わった

1.92900857225
0.910026658388
25.5475004875
14.2164999769

なぜ遅いのですか？関数内で生成された値が一時的にスタックに格納されるためでしょうか。外側の変数はグローバルですが、何がそんなに高速なのですか? 誰かが私のためにそれを片付けてくれるほど親切にしてくれませんか? ありがたく思います。

4

2 に答える 2

4

timeit.timeitキーワード に引数を指定せずに実行numberすると、渡されたコードが 1000000 回実行されます。fac_memPython のグローバル スコープで呼び出されたグローバル ディクショナリを保持すると、最初の実行の結果がそのディクショナリに保存されます。

したがって、メモ化された階乗関数は、実際に計算を行う必要がある最初の実行でのみ遅くなります。残りの 999999 回は、単に辞書で答えを検索し、計算を回避します。

関数内に辞書を保持すると、Python が関数内のスコープを離れるたびに破棄されます (関数が戻ると、辞書へのすべての参照が破棄されるため)。したがって、ディクショナリはその回答を保存することができず、将来の実行のために依然として遅くなります。

のドキュメントを確認してくださいtimeit。

于 2013-09-22T02:47:13.773 に答える
3
  1. あなたが書いたメモ化は、答えに永久にかかっています。これは、同じ回答を複数回求めるのが非常に高速であることを意味します。何かを計算する必要があるのは、最初の呼び出しだけです。
  2. timeit が関数をベンチマークする方法は、関数を何百回も実行し、すべての呼び出しの平均を取ることです。これにより、より正確になります

これは、1 回の通常速度通話と 99 回の超高速通話が平均化されることを意味します。これにより、メモ化された関数の見た目が速くなります。

実際の速度を測定したい場合は、テストを呼び出すたびにメモ化辞書をクリアする必要があります。

于 2013-09-22T02:47:16.983 に答える