search

eprbell / rp2

Privacy-focused, free, open-source cryptocurrency tax calculator for multiple countries: it handles multiple coins/exchanges and computes long/short-term capital gains, cost bases, in/out lot relationships/fractioning, and account balances. It supports FIFO, LIFO, HIFO and it outputs in form 8949 format. It has a programmable plugin architecture
https://pypi.org/project/rp2/
Apache License 2.0
256 stars 42 forks source link

Make LIFO/HIFO accounting methods O(n*log(m)) #116

Closed qwhelan closed 3 weeks ago

qwhelan commented 1 month ago

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
qwhelan commented 1 month ago

Unit tests are now passing (other than a new false alarm on an external link)

eprbell commented 1 month ago

Unit tests are now passing (other than a new false alarm on an external link)

Oh, fantastic! Let me take another look.

qwhelan commented 1 month ago

@eprbell Refactor is complete and all tests are passing, but I'm guessing we'll need a round of cleanup or two. I didn't see your suggestion on row until just now but I'll implement that this week with any cleanup you suggest.

eprbell commented 1 month ago

@eprbell Refactor is complete and all tests are passing, but I'm guessing we'll need a round of cleanup or two. I didn't see your suggestion on row until just now but I'll implement that this week with any cleanup you suggest.

Great! I'll review.