Эффективность алгоритма подсчета сумм

Question

У нас есть ряд платежей (Transaction), которые поступают в наш бизнес каждый день. Каждый Transaction имеет ID и Amount. У нас есть требование сопоставить ряд этих транзакций с определенной суммой. Пример:

Transaction Amount 
1    100 
2    200 
3    300 
4    400 
5    500 

Если мы хотим, чтобы найти сделок, которые добавляют до 600 вы бы число наборов (1,2,3), (2,4), (1,5).

Я нашел алгоритм, который я адаптировал, который работает, как определено ниже. Для 30 транзакций это занимает 15 мс. Но количество транзакций в среднем составляет около 740 и максимальное значение - до 6000. Является ли более эффективным способом выполнить этот поиск?

sum_up(TransactionList, remittanceValue, ref MatchedLists);

private static void sum_up(List<Transaction> transactions, decimal target, ref List<List<Transaction>> matchedLists) 
{ 
    sum_up_recursive(transactions, target, new List<Transaction>(), ref matchedLists); 
} 

private static void sum_up_recursive(List<Transaction> transactions, decimal target, List<Transaction> partial, ref List<List<Transaction>> matchedLists) 
{ 
    decimal s = 0; 
    foreach (Transaction x in partial) s += x.Amount; 

    if (s == target) 
    { 
     matchedLists.Add(partial); 
    } 

    if (s > target) 
     return; 

    for (int i = 0; i < transactions.Count; i++) 
    { 
     List<Transaction> remaining = new List<Transaction>(); 
     Transaction n = new Transaction(0, transactions[i].ID, transactions[i].Amount); 
     for (int j = i + 1; j < transactions.Count; j++) remaining.Add(transactions[j]); 

     List<Transaction> partial_rec = new List<Transaction>(partial); 
     partial_rec.Add(new Transaction(n.MatchNumber, n.ID, n.Amount)); 
     sum_up_recursive(remaining, target, partial_rec, ref matchedLists); 
    } 
} 

С Transaction определяется как:

class Transaction 
{ 
    public int ID; 
    public decimal Amount; 
    public int MatchNumber; 

    public Transaction(int matchNumber, int id, decimal amount) 
    { 
     ID = id; 
     Amount = amount; 
     MatchNumber = matchNumber; 
    } 
} 

Answer 1

Да.

я не могу предоставить полный код на данный момент, но вместо того, чтобы каждый итерации список транзакций дважды до нахождения матчей (O в квадрате), попробуйте эту концепцию:

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

Вместо O^2 вы можете получить его до 4 * O, что сделает заметную разницу в скорости.

Удачи вам!

Answer 2

Динамическое программирование может эффективно решить эту проблему: Предположим, что у вас есть n транзакций, а максимальное количество транзакций - m. мы можем решить его только по сложности O (нм).

узнайте об этом в Knapsack problem. Для этой задачи мы можем определить для транзакций pre i числа подмножества, суммировать сумму: dp [i] [sum]. уравнение:

for i 1 to n: 
    dp[i][sum] = dp[i - 1][sum - amount_i] 

ДП [п] [сумма] является количество вам нужно, и вам нужно добавить некоторые приемы, чтобы получить то, что все подмножества. BLOCKQUOTE

Answer 3

Как уже упоминалось, ваша проблема может быть решена с помощью псевдо полиномиального алгоритма в O(n*G) с n - количество элементов и G - вашу целевую сумму.

Первый вопрос: можно ли достичь целевой суммы G.Следующий псевдокод/​​питон решает его (нет C# на моей машине):

def subsum(values, target): 
    reached=[False]*(target+1) # initialize as no sums reached at all 
    reached[0]=True # with 0 elements we can only achieve the sum=0 
    for val in values: 
     for s in reversed(xrange(target+1)): #for target, target-1,...,0 
      if reached[s] and s+val<=target: # if subsum=s can be reached, that we can add the current value to this sum and build an new sum 
       reached[s+val]=True 
    return reached[target] 

Что такое идея? Рассмотрим значение [1,2,3,6] и целевую сумму 7:

1. Начнет с пустым множеством - возможная сумма явно 0.
2. Теперь мы рассмотрим первый элемент 1 и у вас есть варианты, которые нужно взять или не взять. Это оставляет как с возможными суммами {0,1}.
3. Теперь, глядя на следующий элемент 2: приводит к возможным наборам {0,1} (не принимается) + {2,3} (получение).
4. До сих пор не сильно отличается от вашего подхода, но теперь для элемента 3 у нас есть возможные наборы a. за несоблюдение {0,1,2,3} и b. для принятия {3,4,5,6} в результате {0,1,2,3,4,5,6} как можно сумма. Разница с вашим подходом заключается в том, что есть два способа добраться до 3, и ваша рекурсия будет запущена дважды из этого (что не требуется). Вычисление в основном одного и того же персонала снова и снова - это проблема вашего подхода и почему предложенный алгоритм лучше.
   5. В качестве последнего шага мы рассмотрим 6 и получите {0,1,2,3,4,5,6,7} как возможные суммы.

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

def subsum(values, target): 
    reached=[False]*(target+1) 
    val_ids=[-1]*(target+1) 
    reached[0]=True # with 0 elements we can only achieve the sum=0 

    for (val_id,val) in enumerate(values): 
     for s in reversed(xrange(target+1)): #for target, target-1,...,0 
      if reached[s] and s+val<=target: 
       reached[s+val]=True 
       val_ids[s+val]=val_id   

    #reconstruct the subset for target: 
    if not reached[target]: 
     return None # means not possible 
    else: 
     result=[] 
     current=target 
     while current!=0:# search backwards jumping from predecessor to predecessor 
      val_id=val_ids[current] 
      result.append(val_id) 
      current-=values[val_id] 
     return result 

В качестве другого подхода можно использовать memoization, чтобы ускорить текущее решение запоминания для государства (subsum, number_of_elements_not considered) можно ли достичь целевой суммы , Но я бы сказал, что стандартное динамическое программирование здесь является менее подверженной ошибкам.

Answer 4

У вас есть несколько практических предположения здесь, что бы сделать перебор с довольно-таки ветвью обрезкой осуществимой:

• элементов являются уникальными, поэтому вы не будете получать комбинаторное раздутие действительных подмножеств (то есть (1 , 1,1,1,1,1,1,1,1,1,1,1,1,1), добавляя до 3)
• , если количество результирующих возможных наборов по-прежнему огромно, у вас закончится память собирать их перед запуском в общие проблемы времени выполнения.
• При заказе ввода по возрастанию вы можете легко проверить раннюю остановку - если ваша оставшаяся сумма меньше текущего элемента, то ни один из еще не прошедших экспертизу элементов не может быть в результате (поскольку текущие и последующие элементы будут только больше)
• поддержанию работы суммы позволит ускорить каждый шаг, как вы бы не пересчитывая его снова и снова

Вот немного кода:

public static List<T[]> SubsetSums<T>(T[] items, int target, Func<T, int> amountGetter) 
    { 
     Stack<T> unusedItems = new Stack<T>(items.OrderByDescending(amountGetter)); 
     Stack<T> usedItems = new Stack<T>(); 
     List<T[]> results = new List<T[]>(); 
     SubsetSumsRec(unusedItems, usedItems, target, results, amountGetter); 
     return results; 
    } 
    public static void SubsetSumsRec<T>(Stack<T> unusedItems, Stack<T> usedItems, int targetSum, List<T[]> results, Func<T,int> amountGetter) 
    { 
     if (targetSum == 0) 
      results.Add(usedItems.ToArray()); 
     if (targetSum < 0 || unusedItems.Count == 0) 
      return; 
     var item = unusedItems.Pop(); 
     int currentAmount = amountGetter(item); 
     if (targetSum >= currentAmount) 
     { 
      // case 1: use current element 
      usedItems.Push(item); 
      SubsetSumsRec(unusedItems, usedItems, targetSum - currentAmount, results, amountGetter); 
      usedItems.Pop(); 
      // case 2: skip current element 
      SubsetSumsRec(unusedItems, usedItems, targetSum, results, amountGetter); 
     } 
     unusedItems.Push(item); 
    } 

Я запустить его против 100k ввод, который дает около 1k результатов в er 25 millis, поэтому он может легко справиться с вашим корпусом 740.