<p>三种版本:
<em>自然</em>递归和缓存:</p>
<pre><code>def countchain_recursive_cache(n):
if n not in cache:
if n % 2 == 0:
cache[n] = 1 + countchain_recursif(n//2)
else:
cache[n] = 1 + countchain_recursif(3 * n + 1)
return cache[n]
</code></pre>
<p>纯粹的迭代法:</p>
<pre><code>def countchain_iterative(n):
count=0
while n>1:
if n%2 == 0 :
n //= 2
count += 1
else :
n = (3*n+1)//2
count += 2
return count
</code></pre>
<p>以及无堆栈缓存版本:</p>
<pre><code>def countchain_iterative_cache(n):
count = 0
n0=n
while n not in cache:
count += 1
if n%2 == 0 : n //= 2
else : n = 3*n+1
count+= cache[n]
n=n0
while n not in cache:
cache[n]=count
count-=1
if n%2 == 0 : n //= 2
else : n = 3*n+1
return cache[n]
</code></pre>
<p>如果缓存在函数中,则缓存机制不感兴趣。一定是的
全球将加快进一步的呼吁。你知道吗</p>
<p>时间安排如下:</p>
<pre><code>%time for i in range(1,10**4) : countchain_iterative(i)
cache={1:0}
%time for i in range(1,10**4) : countchain_iterative_cache(i)
cache={1:0}
%time for i in range(1,10**4) : countchain_recursive_cache(i)
%time for i in range(1,10**4) : countChain_morcedist(i)
# respectively :
Wall time: 490 ms
Wall time: 80 ms
Wall time: 54 ms
Wall time: 3.82 s
</code></pre>
<p>但是如果你只想要一个计数链,最有效的方法是无缓存迭代法:</p>
<pre><code>%time countchain_iterative(10**10_000)
Wall time: 6.37 s
Out[381]: 177856
</code></pre>
<p>最后,我猜想你永远不会在迭代构造中破坏快速递归函数:</p>
<pre><code>%time for i in range(1,10**7): countchain_recursif(i)
Wall time: 1min 8s
</code></pre>