If we find a solution which has no waste, just use that. This solution is what we would consider to be optimal, and other solutions we find would have to also have 0 waste, so they are equivalent to the first one with 0 waste. Thus we can optimize by just choosing the first one with 0 waste.
Closes #18257
If we find a solution which has no waste, just use that. This solution
is what we would consider to be optimal, and other solutions we find
would have to also have 0 waste, so they are equivalent to the first
one with 0 waste. Thus we can optimize by just choosing the first one
with 0 waste.
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
Reviewers, this pull request conflicts with the following ones:
If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.
Concept ACK on this as it is an improvement!
However, looking at this I had another thought: given we have two possible solutions with 0 waste, would we not want to minimize fees by selecting the one with fewer inputs? So, instead of stopping early we could still run through all the tries and select the best waste option with the least inputs. Actually this could be an additional breaker between any equal waste options.
However, looking at this I had another thought: given we have two possible solutions with 0 waste, would we not want to minimize fees by selecting the one with fewer inputs? So, instead of stopping early we could still run through all the tries and select the best waste option with the least inputs. Actually this could be an additional breaker between any equal waste options.
Fewer inputs does not necessarily minimize fees. It depends on the exact scripts being used. Regardless, I don’t think an explicit check for fees is needed. So long as fee > long_term_fee, the waste metric will include an amount that is proportional to the fee each input requires, so in the end, the selection that has the least waste also pays the least in transaction fees.
So long as fee > long_term_fee, the waste metric will include an amount that is proportional to the fee each input requires, so in the end, the selection that has the least waste also pays the least in transaction fees.
just to nit, in this case, fee == long_term_fee, right? I think it could go either way, if the user expects long term fees to go up or down they might want to pick more or fewer inputs. In the absence of evidence, simply returning with first result seems optimal.
175@@ -176,8 +176,8 @@ BOOST_AUTO_TEST_CASE(bnb_search_test)
176 selection.clear();
177
178 // Select 5 Cent
179- add_coin(3 * CENT, 3, actual_selection);
180- add_coin(2 * CENT, 2, actual_selection);
181+ add_coin(4 * CENT, 4, actual_selection);
Is this a case that happens in practice though?
That’s also a question I have. My intuition is it’s very unlikely to have an exact match in practice. Also, I think If the cost of change is sufficiently small, its unlikely to have any match including an exact match.
