python - 有效生成斯特恩双原子序列

斯特恩的双原子序列可以阅读到更多的细节，但是，为了我的目的，我现在将定义它。
斯特恩双原子序列的定义
设n为一个数字，从中生成fusc函数。表示为fusc(n)。
如果n为0，则返回值为0。
如果n为1，则返回值为1。
如果n为偶数，则返回值为fusc(n / 2)。
如果n为奇数，则返回值为fusc((n - 1) / 2) + fusc((n + 1) / 2)。
目前，我的python代码在这一代的大部分时间里都是暴力的，除了被两部分分割之外，因为它永远不会产生任何变化。

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)

但是，我的代码必须能够处理1000百万位的数字，并且递归地运行函数数千百万次似乎不是非常有效或实用。
有没有什么方法可以在算法上改进我的代码，使大量的数字可以通过而不必递归调用函数那么多次？

最佳答案

lru_cache对你来说真是奇迹确保maxsize是2的幂。可能需要为您的应用程序稍微修改一下大小cache_info()会有帮助的。
整数除法也使用//而不是/。

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())

是的，这只是菲利普马尔扎克提出的模糊不清。
在while循环中使用位操作可以获得额外的微小加速：

while not n & 1:  # as long as the lowest bit is not 1
    n >>= 1       # shift n right by one

更新：
这里有一个简单的“手工”方法：

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

更新
在读到一个小的更新之后。
文章指出，如果f(n) = f(m)的第一位和最后一位与m的第一位和最后一位相同，并且中间的位是倒转的，则n我们的想法是尽可能的小。
这就是位掩码n的作用（第一位和最后一位是(1<<n.bit_length()-1)-2；中间的位是0；1ingxor，其给出的n如上所述）。
我只能做一些小的基准测试；我感兴趣的是，如果这对你的输入有任何帮助这将减少缓存的内存，并有望带来一些加速。

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

我不得不增加递归限制：

import sys
sys.setrecursionlimit(10000)  # default limit was 1000

基准测试给出了奇怪的结果；使用下面的代码并确保我总是启动一个新的interperter（有一个空的m），我有时会得到明显更好的运行时间；在其他情况下，新代码速度较慢。。。
基准代码：

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)

这是我得到的三个随机结果：

6959
24.117448464001427
0.013900151001507766

6989
23.92404893300045
0.013844672999766772

7038
24.33894686200074
24.685758719999285

那就是我停下来的地方…

关于python - 有效生成斯特恩双原子序列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41229066/