Найти значения в списке, которые представляют собой сумму - оптимизацию

Question

Это действительно продолжение из question, который я задал в начале этого года. Я получил большой ответ на следующую проблему:

Я пытаюсь кодировать что-то простое и вещее, чтобы определить комбинации значений из списка, сумма которых равна определенное значение, в пределах некоторого допуска.

Например:

если А = [0.4,2,3,1.4,2.6,6.3] и целевое значение равно 5 +/- 0,5, то выход я хочу есть (2,3) , (1,4,2,6), (2,2,6), (0,4,2,3), (0,4,3,1,4) и т. Д., Если комбинаций не найдено, функция должна возвращать 0 или , или что-то подобное.

Я внедрил предложение в свой код. Тем не менее, метод (см. Ниже) быстро стал этапом ограничения производительности в моем коде. Это довольно быстро запускать каждую итерацию, но ее запускают много, много раз.

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

def findSum(self, dataArray, target, tolerance=0.5): 
    for i in xrange(1, len(dataArray)+1): 

     results = [list(comb) for comb in list(itertools.combinations(dataArray, i)) 
        if target-tolerance < sum(map(float, comb)) < target+tolerance] 

     if len(results) != 0: 
      return results 

Answer 1

Это, кажется, Subset sum problem.

Согласно википедии, если все элементы в позитивы, и вы ищете для приближенного результата, то этот алгоритм:

initialize a list S to contain one element 0. 
for each i from 1 to N do 
    let T be a list consisting of xi + y, for all y in S 
    let U be the union of T and S 
    sort U 
    make S empty 
    let y be the smallest element of U 
    add y to S 
    for each element z of U in increasing order do 
     //trim the list by eliminating numbers close to one another 
     //and throw out elements greater than s 
     if y + cs/N < z ≤ s, set y = z and add z to S 
if S contains a number between (1 − c)s and s, output yes, otherwise no 

должен дать вам ответ. Он имеет многочленную сложность.

в псевдо питоне (жаль нету я написал питон в то время)

def calc(A,s,c): 
''' 
A is the list containing yours numbers 
s is your goal value 
c is your approximation ie +/- 0.5 
''' 
    S = [0] 
    y = 0 
    for i in xrange(1,N): 
     T = [x+y for x in A for y in S] 
     U = list(set(T) | set(S)) 
     U.sort() 
     S = [] 
     y = min(U) 
     S = [y] 
     for z in U: 
      if y + cs/N < z ≤ s: 
       y = z 
       S.append(z) 
    return [ x for x in S , x>s-c , x<s+c ]  

Answer 2

Я дал ответ с рекурсивной функцией в вашем предыдущем вопросе и сделал несколько оптимизаций ему для этого ответа. Он не только быстрее, чем с использованием itertools.combinations(), он возвращает правильный ответ.

import itertools 
import timeit 

def findSum(dataArray, target, tolerance=0.5): 
    for i in xrange(1, len(dataArray)+1): 

     results = [list(comb) for comb in list(itertools.combinations(dataArray, i)) 
        if target-tolerance <= sum(map(float, comb)) <= target+tolerance] 

     if len(results) != 0: 
      return results 

def recursive(dataArray, target, tolerance=0.5, i=0, possible=[]): 
    results = [] 
    max_target = target + tolerance 
    min_target = target - tolerance 
    l = len(dataArray) 
    while i < l: 
     a = dataArray[i] 
     i += 1 
     if a > max_target: # possible+[a] is too large 
      break 
     if a >= min_target: # Found a set that works 
      results.append(possible+[a]) 
     # recursively try with a shortened list dataArray and a reduced target 
     result = recursive(dataArray, target-a, tolerance, i, possible+[a]) 
     if result: results += result 
    return results 

dataArray = [0.4,2,3,1.4,2.6,6.3] 
dataArray.sort() 
target = 5 

print findSum(dataArray, target) 
print recursive(dataArray, target) 

print timeit.Timer(lambda: findSum(dataArray, target)).timeit(number=100000) 
print timeit.Timer(lambda: recursive(dataArray, target)).timeit(number=100000) 

Как вы можете видеть на выходе, ваша функция возвращает только два результата, но рекурсивная функция возвращает все пять результатов. Для 100000 итераций ваша функция занимает около 2 секунд, а рекурсивная функция занимает около 1,85 секунды.

[[2, 2.6], [2, 3]] 
[[0.4, 1.4, 3], [0.4, 2, 2.6], [0.4, 2, 3], [2, 2.6], [2, 3]] 
2.03791809082 
1.84496808052 

В зависимости от данных, рекурсивная функция может быть даже быстрее, так как он выходит из цикла, когда отсортированные данные больше не могут соответствовать целевому диапазону. Это требует, чтобы dataArray был отсортирован, прежде чем вы вызовете функцию.