Ускорение итерации по диапазону и сравнение значения

Question

У меня есть этот цикл, который генерирует комбинацию чисел и решает, чтобы увидеть, равны ли они решению.После запуска профилировщика я обнаружил, что сумма и сравнение с решением занимают больше всего времени.Это просто из-за количества звонков на каждый из них или есть способ сделать это быстрее?

Выход профилировщика: [Имя, Счетчик вызовов, Время (мс), Собственное время (мс)]

[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

1. Вы повторяете умножение для каждой комбинации.Было бы лучше сделать

   bound_dict =  [['f1', [1850, 1910]], ['f2', [2401, 2482]], ['f3', [5150, 5850]]
   coefficient = [-3, 1, 1]
   rangedict2={bound_dict(i)[0]:range(coefficient[i]*bound_dict(i)[1][0],coefficient[i]*bound_dict(i)[1][0],coefficient[i]) for i in range(len(coefficient))}
   

2. Вы перебираете все комбинации, игнорируя, что ваше ограничение снимает степень свободы.Вы должны удалить диапазон с наибольшим количеством элементов, в данном случае третий.Это уменьшит число итераций в 700 раз.

   for combination in itertools.product(*rangedict2.values()[:-1]):
       currentsolution = sum(combination)
       if  possiblesolution-currentsolution in rangedict2.values()[:-1]:
           solutionfound = True
           dosomething()
           break     
   

3. Вы можете попытаться выполнить понимание списка:

   [possiblesolution-currentsolution in rangedict2.values()[:-1] for #etc.
   

4. Если вы делаете более трех чисел, вы можете попробовать сделать вложенные циклы for вместо использования combination.Общая реализация этого будет выглядеть примерно так:

   last_value1 = list(rangedict2.values()[0])[0]       
   last_value2 = list(rangedict2.values()[1])[0] 
   current_sum = last_value1+last_value2
   for value1 in rangedict2.values()[0]:
       current_sum = current_sum+value1-last_value1
       for value2 in rangedict2.values()[1]:
           current_sum = current_sum +value2-last_value2
           #check whether this is a solution
           last_value2 = value2
           #more nested for-loops
       last_value1 = value1
   

Таким образом, независимо от длины rangedict2, каждая итерация должна выполнять только две операции сложения, а неlen(rangedict2)-1 операций.В этом случае это оказывается 2 в обоих случаях, но в общем случае это может быть меньше операций.В этом случае, поскольку разница всегда одна и та же, вы можете сделать:

    for value1 in (rangedict2.values()[0])):
        for current_sum in range(value1+2401,value2+2482):
            #check whether this is a solution

Глядя на свои действительные числа, вы сможете упростить количество комбинаций, просто выполнив некоторые математические операции.Например, единственные суммы, которые вы получаете из последних двух диапазонов, составляют от 2401 + 5150 до 2482 + 5850-2.Вам не нужно перебирать комбинации 81 * 700 для этого;вам просто нужно 81 + 700.

Answer 2

, как упомянуто в комментариях: упаковка коэффициентов в 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

---

и последнее незначительное ускорение: если вам действительно нужно только одно решение, есть только 4 (возможно, даже 3) возможные случаи для x2 и x3:

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