I need a more efficient algorithm that I do have in a current application.
The algorithm should calculate a indicator based on a "level 2 orderbook".
A level 2 orderbook is a list of all buy orders("bid") for different prices with
different quantities; and also a list of all sell orders ("ask" for different
prices with different quantities.
Example:
Ask 1.45 2000
Ask 1.44 1000
Ask 1.43 500
Ask 1.42 50
Bid 1.41 1000
Bid 1.40 10
Bid 1.39 500
Bid 1.3805 100
The level 2 book is calculated for each instrument. For a symbol
it could contain 500 Bids and Asks. Whenever there is a new
bid a message is received, say "Bid 1.41 1000". When a bid
is removed from the list, a message with 0 quantity is received,
say "Bid 1.41 0"; in this case the bid is removed from the
orderbook. Same goes for the asks.
Now the indicator is calculating the sum of bid quantities
and also the sum of all ask quantities. Then the net
difference is calculated as net difference = sum of ask -
sum of bid. The percentage then is net difference /
(sum of ask + sum of bid) * 100. This is the indicator we
are interested in.
Right now this indicator is recalculated from scratch for
each message that comes in, whihc means we iterate
through an array of possibly 500 items, and this costs time.
The algorithm should be improved, so that the total bid
sum, and the total aks sum is increased or decreased;
therefore the 500 iterations can be saved. Because there
can be 50.000 update messages a second, this means
a significant performance improvement.
## Deliverables
We also need a parameter, which would limit the
calculation of the book only to the best bids or asks.
In our example the best bid is 1.41 and the best ask is 1.42.
If the range would be 0.02 then we would only use the ask
till 1.44 and only those bids down to 1.39. With this
calculation, the running sum has to be calculated on the
"top bids" and "top asks", so it is a little more complex;
but still should be much faster than a full recalc with each
message.
We have a complete visual studio solution with the inefficient
algorithm and require that it is speeded up.
Project is in C# and the programmer should be interested
in mathematics and financial markets. We do have lots
of follow up work.
I would share a dropbox folder for those who are interested
which contains the full project and also demo files to
allow to simulate past market data.
Because the algorithm is incremental, one wrongly
added calculation would mean that the full history
thereafter is wrong as well. Therefore to verify that
the algorithm works, for debugging reaons I want to
be able to verify this. So in this case, the full "non incremental"
algorithm result needs to be compared with the incremental
algorithm. This is to make sure the algo is correct.