rp2
rp2 copied to clipboard
Make LIFO/HIFO accounting methods O(n*log(m))
The LIFO
and HIFO
methods are unfortunately quadratic time (first test is trivial for LIFO
):
One In, One Out
FIFO LIFO HIFO
1 0.000268 0.000233 0.000233
10 0.001612 0.001335 0.001329
100 0.011682 0.012137 0.020656
1000 0.125671 0.126606 1.090273
Buys, then Sells
FIFO LIFO HIFO
1 0.000235 0.000238 0.000233
10 0.001277 0.001378 0.001477
100 0.012547 0.021762 0.029432
1000 0.123024 1.113870 1.903485
The cases are the same as in https://github.com/eprbell/rp2/pull/115 and assume the FIFO
improvements there are merged.
The overall approach is to filter out exhausted lots early, so they do not need to be considered in each pass. In FIFO
, this can be done by keeping track of another index. In LIFO
and HIFO
we introduce a heap where "active" lots are kept. The general for
loop structure is kept to remove exhausted lots (as may occur when switching accounting methods across years), with the first non-exhausted lot guaranteed to be the one we are searching for. The use of heaps improves each loop to O(log m)
.
We translate the search criteria into a heap_key
as Python only natively supports min heaps. It is likely that this key will need to be refined to guarantee deterministic behavior.
Due to test failures, this is not ready to merge but posting to start getting feedback.
And the results with this PR:
One In, One Out
FIFO LIFO HIFO
1 0.000247 0.000250 0.000241
10 0.001286 0.001341 0.001632
100 0.011826 0.012560 0.012876
1000 0.123382 0.131119 0.133895
Buys, then Sells
FIFO LIFO HIFO
1 0.000239 0.000262 0.000243
10 0.001301 0.001400 0.001477
100 0.012038 0.013003 0.015297
1000 0.125055 0.137297 0.171604