rp2
rp2 copied to clipboard
Make FIFO accounting_method linear time
The FIFO
accounting method is unfortunately quadratic time, even in trivial cases:
One In, One Out
FIFO LIFO HIFO
1 0.000234 0.000234 0.000231
10 0.001319 0.001319 0.001431
100 0.020807 0.013064 0.022888
1000 1.073289 0.129614 1.145311
Buys, then Sells
FIFO LIFO HIFO
1 0.000225 0.000236 0.000239
10 0.001399 0.001412 0.001534
100 0.022002 0.023371 0.031054
1000 1.119583 1.103518 1.977542
The "One In, One Out" alternates n
pairs of BUY, SELL
such that there is only ever k=1
active lots. This represents the most trivial case for any accounting method. A potential worst case is represented by "Buys, then Sells" which creates n
BUYS
followed by n
SELLS
. This creates a worst case scenario of k=n
.
In the first case, the LIFO
method is roughly linear; in the second case, it is clearly quadratic. The quadratic behavior of LIFO
and HIFO
will be addressed in a separate PR by using heapq
.
It is relatively straightforward to make FIFO
linear time in both of these cases by simply advancing an index of the next, un-exhausted lot on AcquiredLotCandidates
and persisting this object between invocations of get_acquired_lot_for_taxable_event()
. In the event of different accounting methods being used for different tax years, a one-time scan is performed for each switch of accounting method to find the appropriate index.
With this PR, FIFO
performance improves to linear time in both cases:
One In, One Out
FIFO LIFO HIFO
1 0.000245 0.000248 0.000242
10 0.001359 0.001396 0.001423
100 0.012248 0.012903 0.022407
1000 0.127431 0.133112 1.161365
Buys, then Sells
FIFO LIFO HIFO
1 0.000233 0.000258 0.000243
10 0.001345 0.001436 0.001533
100 0.012368 0.023112 0.031476
1000 0.129783 1.185451 2.029749