construct orderbook from orders example [closed]

Question

I'm looking for code that constructs orderbook from orders

For example if orders are

side | price | quantity
buy   100      1
buy   101      10
buy   100      1000
buy   100      10000

then agregated orderbook should be:

side | price | quantity
buy    100     11001
buy    101     10 

During program lifetime orders are added, modified or deleted. On each order update I need to update OrderBook quickly.

I'm sure this is very common task, so there should be a lot of implementations in Internet already.

Thank you for any references, I'm looking for c# implementation, but I can rewrite it from another language if needed.

upd Actually I should rephrase my question. Initially orderbook is empty. Then I receive events: add order, change order quantity or cancel order. I should recalculate orderBook from this messages. But now it becomes clear for me how simple it should be. When order is added I just add quantity at this price level. When order quantity is changed i just need to add "change" and when order is canceled i just need to remove corresponding quantity from corresponding price level. The only question is where should I store "last order quantity" Totally there are a lot of orders (dozens of millions), but there are not a lot of active orders (not more than 100 000) and for each active order I need to obtain "last quantity" by orderId... Of course I can use dictionary, but that would be too slow probably. I want something faster. But I can not use 50 000 000 items array.

Answer 1

Using a query you can do

UPDATE OrderBook 
SET quantity = (
    SELECT SUM(quantity) FROM orders
    WHERE price = :your_price
      AND side = :your_side) p
WHERE price = :your_price
  AND side = :your_side

where :your_price and :your_side are values of modified order.
Better if you can clear all table and fill it from beginning:

TRUNCATE TABLE OrderBook;
INSERT INTO OrderBook
SELECT side, price, SUM(quantity)
FROM orders
GROUP BY side, price

In my first example I assumed that in your order only quantity can change; but if other values can change it cannot work.
Second example is expensive, so use it only if your order don't change often.
Finally: if your orders vary often and every value can change you could:

1. Update OrderBook removing values from order that should be modified (so before it's updated)
2. Update OrderBook adding values from order that has been changed.

Answer 2

You need to group by the price and side and then select the sum of quantity for each group. Since you haven't specified any medium (database, objects in memory, etc.) we can't really give you a specific implementation.

Edit: apparently these are object in memory, in which case LINQ is your friend:

var results = orders.OrderBy(order => new{order.side, order.price})
.Select(group => new{ group.Key.side, group.Key.price, group.Sum(order => order.quantity));

Answer 3

Here is the code tested in LINQPad

var orders = new [] {
    new {Side = "Buy", Price = 100, Quantity = 1 },
    new {Side = "Buy", Price = 101, Quantity = 10 },
    new {Side = "Buy", Price = 100, Quantity = 1000 },
    new {Side = "Buy", Price = 100, Quantity = 10000 },
    new {Side = "Sell", Price = 100, Quantity = 10000 }
};

var orderboook 
    = from o in (           
                    from order in orders
                    group order by order.Side into sideGroup
                    select new {
                        Side = sideGroup.Key,
                        SideGroup = 
                            from s in sideGroup
                            group s by s.Price into g
                            select new {
                                Side = sideGroup.Key,
                                Price = g.Key, 
                                Quantity = g.Sum( s => s.Quantity) 
                            }
                    }
                )
     from g in o.SideGroup
     select g;

orderboook.Dump(); // .Dump() is LINQPad helper method...

The result in LINQPad is

Answer 4

Of course I can use dictionary, but that would be too slow probably

Any solution will involve either a tree, or a hashtable. So you're probably better off using the standard dictionary implementation of your language.

Now, don't guess anything about performance, especially before having implemented something that works. Then profile, and if the particular dictionary implementation you're using is proven to impact performance, then ask a specific question with actual code we will be glad to try and improve.