Introduce `ISearchStrategy.UpdateSum`
MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BnB/ISearchStrategy.cs
WalletWasabi/Blockchain/TransactionBuilding/BnB/ISearchStrategy.cs
@@ -8,14 +8,32 @@ public interface ISearchStrategy
/// <summary>Target value we want to, ideally, sum up from the input values.</summary>
long Target { get; }
+ /// <summary>
+ /// Modifies selection sum so that we don't need to recompute it.
+ /// </summary>
+ /// <param name="action">Current action of the BnB algorithm.</param>
+ /// <param name="selection">Currently selected values. <c>0</c> when the corresponding value is not selected.</param>
+ /// <param name="depth">Index of a <paramref name="selection"/> value that is currently being included / omitted.</param>
+ /// <param name="oldSum">Previous sum value.</param>
+ /// <returns>New selection sum.</returns>
+ long UpdateSum(NextAction action, long[] selection, int depth, long oldSum)
+ {
+ if (action == NextAction.IncludeFirstThenOmit || action == NextAction.Include)
+ {
+ return oldSum + selection[depth];
+ }
+
+ return oldSum - selection[depth];
+ }
+
/// <summary>
/// Evaluation function that evaluates each step of the Branch and Bound algorithm and
/// tells the algorithm what to do next.
/// </summary>
- /// <param name="solution">Currently selected values. <c>0</c> when the corresponding value is not selected.</param>
- /// <param name="count">Number of <paramref name="solution"/> elements that contains the current solution.</param>
- /// <param name="sum">Sum of first <paramref name="count"/> elements of <paramref name="solution"/>.</param>
- EvaluationResult Evaluate(long[] solution, int count, long sum);
+ /// <param name="selection">Currently selected values. <c>0</c> when the corresponding value is not selected.</param>
+ /// <param name="count">Number of <paramref name="selection"/> elements that contains the current solution.</param>
+ /// <param name="sum">Sum of first <paramref name="count"/> elements of <paramref name="selection"/>.</param>
+ EvaluationResult Evaluate(long[] selection, int count, long sum);
}
public enum EvaluationResult

ADD
WalletWasabi/Blockchain/TransactionBuilding/BnB/NextAction.cs
+namespace WalletWasabi.Blockchain.TransactionBuilding.BnB;
+
+public enum NextAction
+{
+ /// <summary>First try to include a value and then try not to include the value in the selection.</summary>
+ IncludeFirstThenOmit,
+
+ /// <summary>First try NOT to include a value and then try to include the value in the selection.</summary>
+ OmitFirstThenInclude,
+
+ /// <summary>Include value.</summary>
+ Include,
+
+ /// <summary>Omit value.</summary>
+ Omit,
+
+ /// <summary>Current selection is wrong, rolling back and trying different combination.</summary>
+ Backtrack
+}

MODIFY
WalletWasabi/Blockchain/TransactionBuilding/BranchAndBound.cs
WalletWasabi/Blockchain/TransactionBuilding/BranchAndBound.cs
@@ -29,24 +29,6 @@ public class BranchAndBound
SortedValues = values.OrderByDescending(x => x).ToArray();
}
- private enum NextAction
- {
- /// <summary>First try to include a value and then try not to include the value in the selection.</summary>
- IncludeFirstThenOmit,
-
- /// <summary>First try NOT to include a value and then try to include the value in the selection.</summary>
- OmitFirstThenInclude,
-
- /// <summary>Include value.</summary>
- Include,
-
- /// <summary>Omit value.</summary>
- Omit,
-
- /// <summary>Current selection is wrong, rolling back and trying different combination.</summary>
- Backtrack
- }
-
/// <remarks>Input values sorted in descending order.</remarks>
private long[] SortedValues { get; }
@@ -106,12 +88,12 @@ public class BranchAndBound
NextAction action = actions[depth];
// Branch WITH the value included.
- if ((action == NextAction.IncludeFirstThenOmit) || (action == NextAction.Include))
+ if (action == NextAction.IncludeFirstThenOmit || action == NextAction.Include)
{
actions[depth] = GetNextStep(action);
solution[depth] = SortedValues[depth];
- sum += solution[depth];
+ sum = searchStrategy.UpdateSum(action, solution, depth, sum);
EvaluationResult result = searchStrategy.Evaluate(solution, depth + 1, sum);
@@ -127,12 +109,12 @@ public class BranchAndBound
depth++;
actions[depth] = GetRandomNextAction();
}
- else if ((action == NextAction.OmitFirstThenInclude) || (action == NextAction.Omit))
+ else if (action == NextAction.OmitFirstThenInclude || action == NextAction.Omit)
{
actions[depth] = GetNextStep(action);
// Branch WITHOUT the value included.
- sum -= solution[depth];
+ sum = searchStrategy.UpdateSum(action, solution, depth, sum);
solution[depth] = 0;
if (depth + 1 == Count)
@@ -146,7 +128,7 @@ public class BranchAndBound
}
else
{
- sum -= solution[depth];
+ sum = searchStrategy.UpdateSum(action, solution, depth, sum);
solution[depth] = 0;
depth--;
}

Introduce `ISearchStrategy.UpdateSum`