以下是使代码更高效的三种方法:
该代码存储每个部分总和的活动列表。仅存储求和所需的最新活动,并在找到解决方案后通过回溯计算其余活动,在内存和时间方面更有效。
对于每个活动,字典都会重新填充旧内容(子集 [prev_sum] = 子集)。简单地增长一个字典更快
将值一分为二并在中间方法中应用相遇。
应用前两个优化会导致以下代码快 5 倍以上:
def subset_summing_to_zero2 (activities):
subsets = {0:-1}
for (activity, cost) in activities.iteritems():
for prev_sum in subsets.keys():
new_sum = prev_sum + cost
if 0 == new_sum:
new_subset = [activity]
while prev_sum:
activity = subsets[prev_sum]
new_subset.append(activity)
prev_sum -= activities[activity]
return sorted(new_subset)
if new_sum in subsets: continue
subsets[new_sum] = activity
return []
同样应用第三个优化结果如下:
def subset_summing_to_zero3 (activities):
A=activities.items()
mid=len(A)//2
def make_subsets(A):
subsets = {0:-1}
for (activity, cost) in A:
for prev_sum in subsets.keys():
new_sum = prev_sum + cost
if new_sum and new_sum in subsets: continue
subsets[new_sum] = activity
return subsets
subsets = make_subsets(A[:mid])
subsets2 = make_subsets(A[mid:])
def follow_trail(new_subset,subsets,s):
while s:
activity = subsets[s]
new_subset.append(activity)
s -= activities[activity]
new_subset=[]
for s in subsets:
if -s in subsets2:
follow_trail(new_subset,subsets,s)
follow_trail(new_subset,subsets2,-s)
if len(new_subset):
break
return sorted(new_subset)
定义 bound 为元素的最大绝对值。中间相遇方法的算法优势很大程度上取决于边界。
对于下限(例如 bound=1000 和 n=300),中间的相遇只得到了大约 2 倍的改进,而不是第一个改进的方法。这是因为称为子集的字典非常密集。
然而,对于一个上限(例如 bound=100,000 和 n=30),中间的相遇需要 0.03 秒,而第一个改进方法需要 2.5 秒(原始代码需要 18 秒)
对于上限,中间的相遇将取正常方法操作次数的平方根。
中间相遇的速度只是低界的两倍,这似乎令人惊讶。原因是每次迭代的操作数取决于字典中的键数。添加 k 个活动后,我们可能期望有 2**k 个键,但如果 bound 很小,那么这些键中的许多会发生冲突,因此我们将只有 O(bound.k) 个键。