Simplify `estimate_order_costs`
Closed this issue · 2 comments
HighDiceRoller commented
This would look like having a priority of concerns rather than the full cost estimation as now. Possible ordering:
- Evaluator / expression order requirement (mandatory).
- More favorable mixed dice order. For the usual right-truncation case, this would favor popping from the top, i.e. ascending / backwards or descending / forwards.
- Skips.
highest
prefers popping from the top (ascending / backwards or descending / forwards), andlowest
from the bottom (descending / backwards or ascending / forwards). (Should skips be added for decks?) - Ascending / backwards if there are no other preferences.
For anything beyond constant factors I would tend to prioritize single-query performance over caching. So pool.lowest()
might lose some cache hits when used with both mixed and homogeneous pools.
HighDiceRoller commented
In a quick test:
from icepool import MultisetEvaluator, d4, d6, d8, d10, d12, Pool, Order
import cProfile
class TestSumEvaluator(MultisetEvaluator):
def __init__(self, order):
self._order = order
def next_state(self, state, outcome, a, b):
if state is None:
state = 0
return state + outcome * a + outcome * b
def order(self):
return self._order
evaluator_a = TestSumEvaluator(Order.Ascending)
evaluator_b = TestSumEvaluator(Order.Descending)
mixed_pool = Pool([d6, d8, d10, d12])
cProfile.run('evaluator_a(mixed_pool, mixed_pool)')
cProfile.run('evaluator_b(mixed_pool, mixed_pool)')
The backwards evaluation resulted in
69975 function calls (65244 primitive calls) in 0.024 seconds
while the forwards evaluation resulted in
722621 function calls (661263 primitive calls) in 0.235 seconds
Possibly the forwards evaluation scales more poorly with state count? In which case using the backwards algorithm would probably be more important than skips. In this case, we would have:
- If mandatory order, select that one.
- If dice are mixed and prefer one pop order, use that one even if it causes forwards evaluation due to mandatory order. Otherwise, pop to get backwards evaluation.
- Otherwise, the dice are all the same. If there is a mandatory order, choose the backwards evaluation.
- Otherwise, choose pop by which makes better skips.
- Otherwise, default to ascending / backwards.
HighDiceRoller commented
done