|
発端は キミならどう書く 2.0 - ROUND 2 - にある、次の問題:
Collatz予想の収束までのステップ数の最大値を求めよ．
Collatz予想とは，1以上の自然数 n に対して，次の関数 f(n) が必ず1を返すものとする．
f(n) = 1 , n = 1 のとき
= f(n/2) , n が偶数のとき
= f(3*n + 1) , n が奇数のとき
たとえば，f(3)が 1 になるまでの経緯は，
f(3) -> f(10) -> f(5) -> f(16) -> f(8) -> f(4) -> f(2) -> f(1) -> 1
となり， f(n) の呼出は8回である．これをステップ数と呼ぶことにする．
ここで f(n) が 1 になるまでのステップ数を g(n) とする．つまり，g(3) = 8 である．
このとき
h(n) = k, 1 ≦ k ≦ n ∧ g(k) = max (g(1),g(2),…,g(n))
について h(100) を求めよ．
また，余力のある者は大きな n についても h(n) を求めよ．
とりあえず、問題文にあるように忠実に次のように書いてみた。
ただし、f に当たる collatz 関数は1ステップだけ計算を進める。
def collatz(n):
if n == 1:
return 1
elif n & 1:
return 3*n + 1
else:
return n // 2
def collatz_length(n):
length = 0
while n > 1:
n = collatz(n)
length += 1
return length
def collatz_longest(n):
k, length = 1, 0
for i in range(2, n+1):
length_i = collatz_length(i)
if length_i > length:
k, length = i, length_i
return k
if __name__ == '__main__':
import sys
print collatz_longest(int(sys.argv[1]))
実際に走らせれば、
% python collatz.py 100
97
問題から、ステップ数も数えなければならないので f を問題文にあるまま実装する訳にはいかないが、
ステップを数える部分を合わせて再帰的に書き換えてみた。
奇数についての計算は姑息に1ステップ削っている。
呼出側の変更もあるが自明なので、collatz_length の変更のみ:
def collatz_length(n, count):
if n == 1:
return count
elif n & 1:
return collatz_length((3*n + 1)//2, count + 2)
else:
return collatz_length(n//2, count + 1)
こちらの方が若干速くもなった。
速さを上げるもっと簡単な手は、探索範囲を後半半分だけに削ることだ。
その範囲の偶数が、前半部分の数の2倍になるので、正当化できる。
全く別方向から、つまり 1 から逆算して木を作る、という方向も考えたが、効率が悪いので却下。
うまく要らない枝が見分けられればいいのだが…。
あとはキャッシュする、という方向で考えた。
再帰の途中でキャッシュは面倒そうなので、元のコードからの派生。
def _collatz_branch_sequence(n, trunk):
seq = []
while n not in trunk:
seq.append(n)
n = collatz(n)
seq.append(n)
return seq
def collatz_length(n, _memo={1:0}):
branch = _collatz_branch_sequence(n, _memo)
level = len(branch) - 1 + _memo[branch[-1]]
for i, node in enumerate(branch):
if node % 6 == 4:
_memo[node] = level - i
return level
デフォルト引数に辞書を使ってそれを更新することで、キャッシュを実現。
素直に外からキャッシュを渡してもいいんだけど、API 的にはキャッシュのあるなしは本質ではないかな、とか余計なことを考えてこういう実装。
いまのところ、これが自分の書いた中では最速だけど、大きい n を最初に渡すとメモリーを食ってしまうのが問題点。
6 で割って 4 余りのノードで木が分岐するので、そこだけキャッシュするようにはしているが、まだ無駄がある。
不必要になったキャッシュを削ることができればもう少しましなのだが、よい方法が浮かばない。
|