python - 加快迭代范围并比较值

我有一个生成数字组合的循环，并进行求解以查看它们是否等于一个解。运行探查器后，我发现求和与解决方案的比较花费了最长的时间。这是仅是由于每个呼叫的数量引起的，还是有一种方法可以使此速度更快？

探查器输出：
[名称，呼叫计数，时间（毫秒），自己的时间（毫秒）]

[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()

最佳答案

如评论中所述：将系数直接打包到ranges会加快整个过程：

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