<p><a href="https://docs.python.org/3/library/functools.html#functools.lru_cache" rel="nofollow noreferrer">lru_cache</a>对你的情况很有帮助。确保<code>maxsize</code>是2的幂次方。你的应用程序可能需要调整一下这个尺寸。<code>cache_info()</code>会有帮助的。在</p>
<p>也可以使用<code>//</code>代替<code>/</code>进行整数除法。在</p>
<pre><code>from functools import lru_cache
@lru_cache(maxsize=512, typed=False)
def fusc(n):
if n <= 1:
return n
while n > 2 and n % 2 == 0:
n //= 2
return fusc((n - 1) // 2) + fusc((n + 1) // 2)
print(fusc(1000000000078093254329870980000043298))
print(fusc.cache_info())
</code></pre>
<p>是的,这只是菲利普·马尔查克提出的一个建议。在</p>
<p>您可以在while循环中使用位操作获得额外的<em>tiny</em>加速:</p>
^{pr2}$
<hr/>
<p><strong>更新</strong>:</p>
<p>这里有一个简单的“手工”方法:</p>
<pre><code>def fusc(n, _mem={}): # _mem will be the cache of the values
# that have been calculated before
if n in _mem: # if we know that one: just return the value
return _mem[n]
if n <= 1:
return n
while not n & 1:
n >>= 1
if n == 1:
return 1
ret = fusc((n - 1) // 2) + fusc((n + 1) // 2)
_mem[n] = ret # store the value for next time
return ret
</code></pre>
<hr/>
<p><strong>更新</strong></p>
<p>在阅读了<a href="https://www.cs.utexas.edu/users/EWD/transcriptions/EWD05xx/EWD578.html" rel="nofollow noreferrer">short article by dijkstra himself</a>的小更新之后。在</p>
<p>文章指出,<code>f(n) = f(m)</code>如果<code>m</code>的第一位和最后一位与{<cd7>}相同,并且两者之间的位是颠倒的。这样做的目的是使<code>n</code>越小越好。在</p>
<p>这就是位掩码<code>(1<<n.bit_length()-1)-2</code>的用途(第一位和最后一位是<code>0</code>;中间的那些<code>1</code>;<code>xor</code>ing<code>n</code>,如上所述)。在</p>
<p>我只能做一些小的基准测试;我感兴趣的是,如果这对您的输入的魔力有任何帮助。。。这将减少缓存的内存,并有望带来一些加速。在</p>
<pre><code>def fusc_ed(n, _mem={}):
if n <= 1:
return n
while not n & 1:
n >>= 1
if n == 1:
return 1
# https://www.cs.utexas.edu/users/EWD/transcriptions/EWD05xx/EWD578.html
# bit invert the middle bits and check if this is smaller than n
m = n ^ (1<<n.bit_length()-1)-2
n = m if m < n else n
if n in _mem:
return _mem[n]
ret = fusc(n >> 1) + fusc((n >> 1) + 1)
_mem[n] = ret
return ret
</code></pre>
<p>我不得不增加递归限制:</p>
<pre><code>import sys
sys.setrecursionlimit(10000) # default limit was 1000
</code></pre>
<p>基准测试给出了奇怪的结果;使用下面的代码并确保我总是启动一个新的interperter(有一个空的<code>_mem</code>),我有时会得到更好的运行时;在其他情况下,新代码会慢一些。。。在</p>
<p>基准代码:</p>
<pre><code>print(n.bit_length())
ti = timeit('fusc(n)', setup='from __main__ import fusc, n', number=1)
print(ti)
ti = timeit('fusc_ed(n)', setup='from __main__ import fusc_ed, n', number=1)
print(ti)
</code></pre>
<p>我得到了三个随机结果:</p>
<pre><code>6959
24.117448464001427
0.013900151001507766
6989
23.92404893300045
0.013844672999766772
7038
24.33894686200074
24.685758719999285
</code></pre>
<p>那就是我停下来的地方。。。在</p>