Take the 2-minute tour ×
Quantitative Finance Stack Exchange is a question and answer site for finance professionals and academics. It's 100% free, no registration required.

What is an efficient data structure to model order book of prices and quantities to ensure:

  1. constant look up
  2. iteration in order of prices
  3. retrieving best bid and ask in constant time
  4. fast quantity updates
share|improve this question

3 Answers 3

I do not know in which context you want to implement a matching engine (ME). But according to me the two nice challenges in this context are:

  • implement one in an FPGA
  • for simulation / fast replay purpose, design the most efficient in/out bus to put synthetic traders in front of the ME.

The last point is about simulating one day in few seconds.

To answer more directly your question, the reference is Josh Levine's code of Island in foxpro. Levin's has been one of the pioneer in the raise of electronic trading. It is not only an executable spec, but a piece of history.

share|improve this answer

If you assume that most updates will happen near the top of the book (a fair assumption) a linked-list ordered by price levels will be very efficient.

You can check CoralMD for an example of a very fast, garbage-free market data book implementation that provides not just the global view of the market (all exchanges) but also a per-exchange book view. It also provides the infra-structure to write exchange feeds and to distribute market data internally.

Disclaimer: I am one of the developers of CoralMD

share|improve this answer

Since Quant Cup 1's objective was an efficient price/time matching engine, the data structure of the winning implementation might partly be what you are looking for.

Else the setup of LOBSTER is supposed to be quick.

share|improve this answer
    
Nice. I was thinking of a simple array based implementation. The best implementation in Quant Cup does something similar. –  Sam Hayen Jul 10 '12 at 20:23
    
However, note that it will be less optimal when price levels are sparse and we care about every price level. –  Sam Hayen Jul 10 '12 at 20:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.