python - 加速范围内的迭代并比较值

Question

我有一个循环，它生成数字组合并求解，看看它们是否等于一个解。运行分析器后，我发现求和以及与解决方案的比较花费了最长的时间。这仅仅是由于对每个人的调用数量所致，还是有办法加快速度？

分析器输出:[姓名、调用次数、时间(ms)、自己的时间(ms)]

[listcomp, 23114767, 5888, 5888] 总时间的 25%。

[builtin.sums, 23164699, 3097, 3097] 总时间的 12%

现在我想不出一种方法来缩小搜索范围，因此尝试在其他地方节省时间:)

感谢您的帮助。

rangedict = {'f1': range(1850, 1910), 'f2': range(2401, 2482), 'f3': range(5150, 5850)}
coefficient = [-3, 1, 1]
possiblesolution = 1930

for combination in itertools.product(*rangedict.values()):
    if solutionfound:
        break
    else:
        currentsolution = sum([x*y for x, y in zip(coefficient, combination)])
        if currentsolution == possiblesolution:
            solutionfound = True
            dosomething()

Answer 1

正如评论中提到的:直接将系数打包到范围中会加快整个过程的速度:

from itertools import product

possiblesolution = 1930
solutionfound = False
rangedict2 = {'f1': range(-3*1850, -3*1910, -3),
              'f2': range(2401, 2482), 
              'f3': range(5150, 5850)}

for combination in product(*rangedict2.values()):
    if sum(combination) == possiblesolution:
        solutionfound = True
        print(combination[0]//(-3), combination[1], combination[2])
        break

<小时/>

或者完全不同的方法:创建一个字典，其中包含可以从 f1 和 f2 获得的总和，然后检查您的目标是否possiblesolution可以到达:

from collections import defaultdict

rangedict3 = {'f1': range(-3*1850, -3*1910, -3), 
              'f2': range(2401, 2482), 
              'f3': range(5150, 5850)}

sums = {item: [[item]] for item in rangedict3['f1']}
# sums = {-5550: [[-5550]], -5553: [[-5553]], ...}

new_sums = defaultdict(list)
for sm, ways in sums.items():
    for item in rangedict3['f2']:
        new_sum = sm + item
        for way in ways:
           new_sums[new_sum].append(way + [item])
# new_sums = {-3149: [[-5550, 2401], [-5553, 2404], ...],
#             -3148: [[-5550, 2402], [-5553, 2405], ...],
#             ....}         

for item in rangedict3['f3']:
    if possiblesolution - item in new_sums:
        f1_f2 = new_sums[possiblesolution - item]
        print(f1_f2[0][0]//(-3), f1_f2[0][1], item)
        # print(new_sums[possiblesolution - item], item)
        break

这样你也可以轻松获得剩余的解决方案。

<小时/>

或者将 f2 和 f3 合并在一起:

f1 = rangedict3['f1']
f2 = rangedict3['f2']
f3 = rangedict3['f3']

# the sums that are reachable from f2 and f3
f2_f3 = range(2401 + 5150, 2482 + 5850)

for item in f1:
    if possiblesolution - item in f2_f3:
        pmi = possiblesolution - item
        x1 = item//(-3)
        for x2 in f2:
            if pmi-x2 in f3:
                x3 = pmi-x2
                break
        print(x1, x2, x3)
        break

<小时/>

最后一个小的加速:如果您确实只需要一种解决方案，则 x2 和 x3 只有 4 种(可能甚至 3 种)可能的情况:

f1 = rangedict3['f1']
f2 = rangedict3['f2']
f3 = rangedict3['f3']

min_x2 = min(f2)
max_x2 = max(f2)
min_x3 = min(f3)
max_x3 = max(f3)

# the sums that are reachable from f2 and f3
f2_f3 = range(2401 + 5150, 2482 + 5850 - 1)

for item in f1:
    if possiblesolution - item in f2_f3:
        pmi = possiblesolution - item
        x1 = item//(-3)

        if pmi-min_x2 in f3:
            x2 = min_x2
            x3 = pmi-x2
        elif pmi-max_x2 in f3:
            x2 = max_x2
            x3 = pmi-x2
        elif pmi-min_x3 in f2:
            x3 = min_x3
            x2 = pmi-x3
        # elif pmi-max_x3 in f2:
        else:
            x3 = max_x3
            x2 = pmi-x3

        print(x1, x2, x3)
        break