使用幂函数计算效率图大小
efficiency graph size calculation with power function
我正在寻找改进以下简单函数(写在python),计算特定图的最大尺寸:
def max_size_BDD(n):
i = 1
size = 2
while i <= n:
size += min(pow(2, i-1), pow(2, pow(2, n-i+1))-pow(2, pow(2, n-i)))
i+=1
print(str(i)+" // "+ str(size))
return size
如果我将它作为输入 n = 45,进程将被终止(可能是因为它花费的时间太长,我不认为这是内存问题,对吧?)。我如何重新设计以下算法,使其能够处理更大的输入?
我的建议:虽然原始函数在 ~10 时开始 运行 出现问题,但我实际上没有任何限制(即使对于 n = 100000000,我也保持在 1s 以下)。
def exp_base_2(n):
return 1 << n
def max_size_bdd(n):
# find i at which the min branch switches
start_i = n
while exp_base_2(n - start_i + 1) < start_i:
start_i -= 1
# evaluate all to that point
size = 1 + 2 ** start_i
# evaluate remaining terms (in an uncritical range of n - i)
for i in range(start_i + 1, n + 1):
val = exp_base_2(exp_base_2(n - i))
size += val * (val - 1)
print(f"{i} // {size}")
return size
备注:
- 核心思想:避免2的大次方,如果最后用
min
就不用计算了
- 我匆忙做了所有这些,也许我可以稍后添加更多解释......如果有人感兴趣的话。然后,我也可以对新的实现做一个更体面的验证。
exp_base_2
的影响在完成所有数学运算以优化原始计算后应该可以忽略不计。我在分析之前做了这个优化。
- 也许一个完整的封闭形式的解决方案是可能的。我没有投入时间进行进一步调查。
我正在寻找改进以下简单函数(写在python),计算特定图的最大尺寸:
def max_size_BDD(n):
i = 1
size = 2
while i <= n:
size += min(pow(2, i-1), pow(2, pow(2, n-i+1))-pow(2, pow(2, n-i)))
i+=1
print(str(i)+" // "+ str(size))
return size
如果我将它作为输入 n = 45,进程将被终止(可能是因为它花费的时间太长,我不认为这是内存问题,对吧?)。我如何重新设计以下算法,使其能够处理更大的输入?
我的建议:虽然原始函数在 ~10 时开始 运行 出现问题,但我实际上没有任何限制(即使对于 n = 100000000,我也保持在 1s 以下)。
def exp_base_2(n):
return 1 << n
def max_size_bdd(n):
# find i at which the min branch switches
start_i = n
while exp_base_2(n - start_i + 1) < start_i:
start_i -= 1
# evaluate all to that point
size = 1 + 2 ** start_i
# evaluate remaining terms (in an uncritical range of n - i)
for i in range(start_i + 1, n + 1):
val = exp_base_2(exp_base_2(n - i))
size += val * (val - 1)
print(f"{i} // {size}")
return size
备注:
- 核心思想:避免2的大次方,如果最后用
min
就不用计算了 - 我匆忙做了所有这些,也许我可以稍后添加更多解释......如果有人感兴趣的话。然后,我也可以对新的实现做一个更体面的验证。
exp_base_2
的影响在完成所有数学运算以优化原始计算后应该可以忽略不计。我在分析之前做了这个优化。- 也许一个完整的封闭形式的解决方案是可能的。我没有投入时间进行进一步调查。