我的程序需要很长的时间才能打印出超过25个结果，有没有办法让我运行时更高效？

Question

这些是我正在使用的行，它会生成一个列表，列出可能的总和与输入的整数，然后说明组合的数量。

import itertools 

val = int(input()) 
r = range(val)[1:] 
res = []  
for i in range(len(r)+1): 
    res += [list(x) for x in itertools.combinations(r, i) if sum(list(x)) == val]  
print("Solution : %s " % res) 
print("Combinations : %s" % len(res)) 

Answer 1

它看起来像你正在计算每一个可能的组合，然后只保留满足你的总和条件的组合。组合池是通过搜索增长的速度2 ^（N-1），你可以通过注释掉条件部分看：

import itertools 
import time 

startTime = time.time() 

val = 21 
r = range(val)[1:] 
res = []  
for i in range(len(r)+1): 
    res += [list(x) for x in itertools.combinations(r, i)]# if sum(list(x)) == val]  
#print("Solution : %s " % res) 
print("Combinations : %s" % len(res)) 

print(time.time() - startTime, 'seconds') 

试试这个：

def a(lst, target, with_replacement=False): 
    def _a(idx, l, r, t, w): 
     if t == sum(l): r.append(l) 
     elif t < sum(l): return 
     for u in range(idx, len(lst)): 
      _a(u if w else (u + 1), l + [lst[u]], r, t, w) 
     return r 
    return _a(0, [], [], target, with_replacement) 

val = 50 
s = range(1, val) 
solutions = a(s, val) 
print(solutions) 
print(len(solutions)) 

这是从修改代码由thefourtheye： Finding Combinations to the provided Sum value

定时它： 原代码：

val = 24, t = 6.5917372703552253 seconds 
val = 25, t = 13.705767631530762 seconds 
val = 26, t = 27.934977531433105 seconds 
val = 50, t = 459889248.39282094 seconds 

上述方法：

val = 24, t = 0.0084612369537353 seconds 
val = 25, t = 0.0069310665130615 seconds 
val = 26, t = 0.0085859298706054 seconds 
val = 50, t = 0.4947729110717773 seconds 

Answer 2

可能有许多方法来提高速度。我尝试过（并且注意到它有很大的不同）：简单的：消除生成器和列表之间的重复转换。这里是你的代码，修改后：

import time 
import itertools 

#val = int(input("val:")) 
#r = range(val)[1:] 

def simple_time_func(func): 
    def wrapper(*args, **kwargs): 
     start = time.time() 
     r = func(*args, **kwargs) 
     print("{} took {:.3f} seconds.".format(func.__name__, time.time() - start)) 
     return r 
    return wrapper 

@simple_time_func 
def original(val, r): 
    res = list() 
    for i in range(len(r) + 1): 
     res += [list(x) for x in itertools.combinations(r, i) if sum(list(x)) == val] 
    return res 

@simple_time_func 
def improved0(val, r): 
    res = list() 
    for i in range(len(r) + 1): 
     res += [x for x in itertools.combinations(r, i) if sum(x) == val] 
    return res 


for val in range(21, 28): 
    r = range(val)[1:] 
    print("\nval: {}".format(val)) 
    for func in (original, improved0): 
     res = func(val, r) 
     #print(" Solution : %s " % res) 
     #print(" Combinations : %s" % len(res)) 

注意：

• 我把昂贵的部分（for回路）和封装它在一个函数（original）以一次
• 我将改进的循环放在另一个函数中（称为improved0）
• 其余的代码（不幸的是，也是最重要的）仅用于性能测试

输出：

(py35x64_test) c:\Work\Dev\StackOverflow\q46853086>"c:\Work\Dev\VEnvs\py35x64_test\Scripts\python.exe" a.py 

val: 21 
original took 0.573 seconds. 
improved0 took 0.325 seconds. 

val: 22 
original took 1.185 seconds. 
improved0 took 0.633 seconds. 

val: 23 
original took 2.388 seconds. 
improved0 took 1.300 seconds. 

val: 24 
original took 4.880 seconds. 
improved0 took 2.609 seconds. 

val: 25 
original took 9.796 seconds. 
improved0 took 5.243 seconds. 

val: 26 
original took 19.701 seconds. 
improved0 took 10.489 seconds. 

val: 27 
original took 39.314 seconds. 
improved0 took 21.559 seconds. 

正如输出所示，这显然是微不足道的变化几乎削减了一半时间。
下一步包括real优化（因为计算复杂度仍然看起来指数），关于数学和编程技巧的有效使用，甚至更多地提高速度（不幸的是我没有时间）。