私のプログラムが同じことを2回計算しないように、計算結果をPythonでどのように保存するのですか？

Question

私はPythonのプログラムで問題を抱えています（私は完全なnewbです）。計算からのデータを保存せず、保存しておくべきであると感じたら、何度も繰り返します。 Pythonが答えを保存するようにするにはどうすればいいですか？プログラムを何度も何度も計算しないでください。

例：

import prime 
def g(x): 
    i=0 
    while i<len(prime.sieve(x)): 
     print str(prime.sieve(x)[i])+' is prime' 
     i=i+1 

ここで、 "プライム" モジュールの場合には、誰かがこれをコンパイルしたい：

def sieve(max): 
    #Takes in a number, and returns all primes between 2 and that number 

    #Start with all of the numbers 
    primes = range(2,max+1) 
    #Start running through each number 
    for i in primes: 
      #Start with double the number, and 
      j = 2 
      #remove all multiples 
      while i * j <= primes[-1]: 
        #As long as the current multiple of the number 
        #is less than than the last element in the list 
        #If the multiple is in the list, take it out 
        if i * j in primes: 
          primes.remove(i*j) 
        j=j+1 
    return primes 

とにかく、コードの最初のビットがリスト「prime.sieve（Xを計算します）」と繰り返し、印刷する際に参考にしたいと思います。

ありがとうございます！

rofls

Answer 1

saved_sieve_map = {} 
def saved_sieve(x): 
    if x not in saved_sieve_map: 
    saved_sieve_map[x] = sieve(x) 
    return saved_sieve_map[x] 

Answer 2

あなただけのローカル変数に割り当てることができます：

i=0 
saveit = prime.sieve(x) 
while i<len(saveit): 
    print str(saveit[i])+' is prime' 
    i=i+1 

注：それはまだg(x)がxの同じ値で2回呼び出されても、ふるいを計算しません。 gの範囲を超えても計算を保存するバージョンでは、キースの答え。

Answer 3

これはメモ化と呼ばれます。幸いなことに、メモ化デコレータがたくさんあり、そのうちの一つがここにある：http://wiki.python.org/moin/PythonDecoratorLibrary#Memoize

使用例は次のとおりです。

@memoized 
def fibonacci(n): 
    "Return the nth fibonacci number." 
    if n in (0, 1): 
     return n 
    return fibonacci(n-1) + fibonacci(n-2) 

print fibonacci(12) 

（@memoized式は、それ以下の関数にデコレータを適用します）。

Answer 4

この関数を使用して、再帰的な複雑さを削除できます。

from functools import wraps 
def memo(func): 
    cache = {} 
    @wraps(func) 
    def wrap(*args): 
     if args not in cache: 
      cache[args] = func(*args) 
     return cache[args] 
    return wrap 

とにかくこれはあなたより道より高速に実行する必要がありふるいの私の実装です。

@memo 
def sieve(end): 
    import itertools 
    lng = ((end/2)-1+end%2) 
    sieve = [True]*(lng+1) 
    for i in itertools.ifilter(lambda z: sieve[z],xrange(int(end**0.5) >> 1)): 
     n=len(sieve[int((i*(i + 3) << 1) + 3): int(lng): int((i << 1) + 3)]) 
     sieve[int((i*(i + 3) << 1) + 3): int(lng): int((i << 1) + 3)]=[False]*n 
    return sum([(x << 1) + 3 for x in itertools.compress(xrange(lng),sieve)])+2