问题描述
可以更详细地了解斯特恩的双原子序列；但是，出于我的目的，我现在将对其进行定义。
斯特恩双原子序列的定义
让 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）：
如果n < = 1：
返回n
而n> 2和n％2 == 0：
n / = 2
return fusc（（n-1）/ 2）+ fusc（（n + 1）/ 2）
但是，我的代码必须能够处理数百万位的数字，并以递归方式运行数以千计的函数似乎并不高效或不实用。
有什么方法可以算法改进我的算法吗？这样的代码可以传递大量数字而无需递归调用该函数多次？
可以解决您的问题。确保 maxsize 是2的幂。对于您的应用程序，可能需要花一点时间调整该大小。 cache_info（）将对此有所帮助。
还可以使用 // 而不是 / 进行整数除。
从functools导入lru_cache
@lru_cache（maxsize = 512，typed = False）
def fusc（n）：
如果n
而n> 2和n％2 == 0：
n // = 2
return fusc（（n-1）// 2）+ fusc（（n + 1）// 2）
print（fusc（1000000000078093254329870980000043298））
print（fusc.cache_info（））
是的，这只是Filip Malczak提出的记忆法。
您可以使用bit-bit获得额外的 tiny 加速while循环中的操作：
而不是n& 1：＃只要最低位不是1
n>> == 1＃将n右移一个
更新：
这是做记忆的一种简单方法'手工'：
def fusc（n，_mem = {}）：＃_mem将是值的缓存$ b_b＃如果_mem中的n在
之前计算：＃如果我们知道一个：仅返回值
return _mem [n]
如果n< = 1：
返回n
而不是n& 1：
n>> = 1
如果n == 1：1：
返回1
ret = fusc（（n-1）// 2）+ fusc（（n + 1）// 2）
_mem [n] = ret＃存储下一次的值
return ret
更新
是一个小的更新。 / p>
该文章指出，如果拳头最后一点<$$，则 f（n）= f（m） c $ c> m 与 n 相同，并且中间的位被反转。想法是使 n 尽可能小。
这就是位掩码 （1<< n.bit_length（）-1）-2 是用于（第一和最后一位是 0 ;中间的 1 ; xor 与 n 相乘得到 m 如上所述）。
我只能做小的基准测试；我很想知道这是否对您输入的内容大有帮助...这将减少缓存的内存并希望带来一些加速。
def fusc_ed（n，_mem = {}）：如果n< = 1：
返回n
而不是n& 1：
n>> = 1
，如果n == 1：
返回1
＃https://www.cs.utexas.edu/users /EWD/transcriptions/EWD05xx/EWD578.html
＃位反转中间位，并检查中间位是否小于n
m = n ^（1 n = m（如果m< n否则n
如果_mem中的n：
return _mem [n]
ret = fusc（n>> 1）+ fusc（（n ;> 1）+ 1）
_mem [n] = ret
return ret
我必须增加递归限制：
import sys
sys.setrecursionlimit（10000）＃默认限制是1000
基准测试得出了奇怪的结果；使用下面的代码，并确保我总是启动一个新的插入器（具有空的 _mem ），有时我会获得更好的运行时环境；在其他情况下，新代码比较慢...
基准代码：
print（n.bit_length（））
ti = timeit（'fusc（n）'，setup ='from __main__ import fusc，n'，number = 1）
打印（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
那是我停下来的地方...
Stern's Diatomic Sequence can be read about in more details over here; however, for my purpose I will define it now.
Definition of Stern's Diatomic Sequence
Let n be a number to generate the fusc function out of. Denoted fusc(n).
If n is 0 then the returned value is 0.
If n is 1 then the returned value is 1.
If n is even then the returned value is fusc(n / 2).
If n is odd then the returned value is fusc((n - 1) / 2) + fusc((n + 1) / 2).
Currently, my Python code brute forces through most of the generation, other than the dividing by two part since it will always yield no change.
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)
However, my code must be able to handle digits in the magnitude of millions of bits, and recursively running through the function millions of times does not seem very efficient or practical.
Is there any way I could algorithmically improve my code such that massive numbers can be passed through without having to recursively call the function so many times?
lru_cache works wonders in your case. make sure maxsize is a power of 2. may need to fiddle a bit with that size for your application. cache_info() will help with that.
also use // instead of / for integer division.
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())
and yes, this is just meomization as proposed by Filip Malczak.
you might gain an additional tiny speedup using bit-operations in the while loop:
while not n & 1: # as long as the lowest bit is not 1
n >>= 1 # shift n right by one
UPDATE:
here is a simple way of doing meomzation 'by hand':
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
UPDATE
after reading a short article by dijkstra himself a minor update.
the article states, that f(n) = f(m) if the fist and last bit of m are the same as those of n and the bits in between are inverted. the idea is to get n as small as possible.
that is what the bitmask (1<<n.bit_length()-1)-2 is for (first and last bits are 0; those in the middle 1; xoring n with that gives m as described above).
i was only able to do small benchmarks; i'm interested if this is any help at all for the magitude of your input... this will reduce the memory for the cache and hopefully bring some speedup.
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
i had to increase the recursion limit:
import sys
sys.setrecursionlimit(10000) # default limit was 1000
benchmarking gave strange results; using the code below and making sure that i always started a fresh interperter (having an empty _mem) i sometimes got significantly better runtimes; on other occasions the new code was slower...
benchmarking 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)
and these are three random results i got:
6959
24.117448464001427
0.013900151001507766
6989
23.92404893300045
0.013844672999766772
7038
24.33894686200074
24.685758719999285
that is where i stopped...
这篇关于有效生成斯特恩双原子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！