Home > Enterprise >  Which data structure is suitable to store multiple keys with one Object and Complexity is O(1)
Which data structure is suitable to store multiple keys with one Object and Complexity is O(1)

Time:08-17

When developing a trading core system, given having an order object as :

class Order{
   name string, // symbol name
   id   int,
   price float64,
   tp_price float64,
   sl_price float64,
   type  int, // 0 - market order, 1 - limit order, 2 - stop order, 3 - stop limit order 
   expiration datetime  
}

we have three triggers that need to find specified order and modify it:

  1. User Modification from client based on id
  2. Timer checking expiration need to find order based on id
  3. Tick data processing logic need to find order based on name

So for Tick data processing easily, I use the following data structure: map(key with symbol name, data is ordered array order array) real data like :

map['AUDCAD'] = array(order1, order2,order3, ...)
map['CADUSD'] = array(order7, order8,order9, ...)

then when tick data(ask/bid) comes, we can find all orders based on the symbol name easily in the map.

but if an order modifying request comes from the client, I must to loop all the map to find the specified order, it is bad.

and we need to process orders in multi-threading mode as well.

So my question is : which data structure is suitable for my case : to find an order with multiple keys (order id or symbol name) and complexity is O(1).

Any ideas are very appreciated.

CodePudding user response:

You can use a structure with two maps:

type orderIndex struct {
   sync.RWMutex
   orderByID map[int]*Order
   orderByName map[string][]*Order
}

When inserting, Lock() order index, and add order to both maps.

When looking up, RLock the index, and lookup the order in one of the maps.

If you need to protect individual order for concurrent access, you may add a Mutex to order struct, or use the Lock() for the orderIndex if you need to bulk-update orders.

  • Related