6

Project Euler で問題 14 に取り組んでいたとき、メモ化と呼ばれるものを使用してプロセスを高速化できることを発見しました (15 分間実行させましたが、まだ回答が返されませんでした)。問題は、それをどのように実装するかです。しようとしましたが、キーエラーが発生します（返される値が無効です）。私はこれにメモ化を適用してこれをより速く取得できると確信しているので、これは私を悩ませます。

lookup = {}

def countTerms(n):
   arg = n
   count = 1
   while n is not 1:
      count += 1
      if not n%2:
         n /= 2
      else:
         n = (n*3 + 1)
      if n not in lookup:
         lookup[n] = count

   return lookup[n], arg

print max(countTerms(i) for i in range(500001, 1000000, 2))

ありがとう。

4

3 に答える 3

4

これを行うための再帰的な方法もあり、これはおそらく poorsod のソリューションよりも遅くなりますが、最初のコードに似ているため、理解しやすいかもしれません。

lookup = {}

def countTerms(n):
   if n not in lookup:
      if n == 1:
         lookup[n] = 1
      elif not n % 2:
         lookup[n] = countTerms(n / 2)[0] + 1
      else:
         lookup[n] = countTerms(n*3 + 1)[0] + 1

   return lookup[n], n

print max(countTerms(i) for i in range(500001, 1000000, 2))
于 2013-03-18T23:48:14.267 に答える
3

Collat​​z シーケンスのメモ化のポイントは、既に行ったリストの一部を計算しないようにすることです。シーケンスの残りは、現在の値によって完全に決定されます。そのため、できるだけ頻繁にテーブルをチェックし、できるだけ早く残りの計算を回避したいと考えています。

def collatz_sequence(start, table={}):  # cheeky trick: store the (mutable) table as a default argument
    """Returns the Collatz sequence for a given starting number"""
    l = []
    n = start

    while n not in l:  # break if we find ourself in a cycle
                       # (don't assume the Collatz conjecture!)
        if n in table:
            l += table[n]
            break
        elif n%2 == 0:
            l.append(n)
            n = n//2
        else:
            l.append(n)
            n = (3*n) + 1

    table.update({n: l[i:] for i, n in enumerate(l) if n not in table})

    return l

それは働いていますか？それをスパイして、メモ化された要素が使用されていることを確認しましょう。

class NoisyDict(dict):
    def __getitem__(self, item):
        print("getting", item)
        return dict.__getitem__(self, item)

def collatz_sequence(start, table=NoisyDict()):
    # etc



In [26]: collatz_sequence(5)
Out[26]: [5, 16, 8, 4, 2, 1]

In [27]: collatz_sequence(5)
getting 5
Out[27]: [5, 16, 8, 4, 2, 1]

In [28]: collatz_sequence(32)
getting 16
Out[28]: [32, 16, 8, 4, 2, 1]

In [29]: collatz_sequence.__defaults__[0]
Out[29]: 
{1: [1],
 2: [2, 1],
 4: [4, 2, 1],
 5: [5, 16, 8, 4, 2, 1],
 8: [8, 4, 2, 1],
 16: [16, 8, 4, 2, 1],
 32: [32, 16, 8, 4, 2, 1]}

編集：最適化できることはわかっていました！その秘密は、関数内に既知で要素lをtable共有しない 2 つの場所 (2 つの戻り点) があることです。table.update以前は要素をテストすることで既存の要素を呼び出すことを避けていましtableたが、このバージョンの関数は代わりに制御フローに関する知識を活用し、多くの時間を節約します。

[collatz_sequence(x) for x in range(500001, 1000000)]現在、私のコンピューターでは約 2 秒の時間を計測していますが、@welter のバージョンの同様の式では 400 ミリ秒で計測されています。これは、関数が実際には同じことを計算しないためだと思います-私のバージョンはシーケンス全体を生成しますが、@welter はその長さを見つけるだけです。したがって、実装を同じ速度に落とすことはできないと思います。

def collatz_sequence(start, table={}):  # cheeky trick: store the (mutable) table as a default argument
    """Returns the Collatz sequence for a given starting number"""
    l = []
    n = start

    while n not in l:  # break if we find ourself in a cycle
                       # (don't assume the Collatz conjecture!)
        if n in table:
            table.update({x: l[i:] for i, x in enumerate(l)})
            return l + table[n]
        elif n%2 == 0:
            l.append(n)
            n = n//2
        else:
            l.append(n)
            n = (3*n) + 1

    table.update({x: l[i:] for i, x in enumerate(l)})
    return l

PS - バグを見つけてください！

于 2013-03-18T23:37:56.130 に答える
-1

これはPE14に対する私の解決策です:

memo = {1:1}
def get_collatz(n):

if n in memo : return memo[n]

if n % 2 == 0:
    terms = get_collatz(n/2) + 1
else:
    terms = get_collatz(3*n + 1) + 1

memo[n] = terms
return terms

compare = 0
for x in xrange(1, 999999):
if x not in memo:
    ctz = get_collatz(x)
    if ctz > compare:
     compare = ctz
     culprit = x

print culprit
于 2015-03-05T13:33:05.707 に答える