Optimal data structure for limit order book

我鐘意返工返學

4 回覆
2 Like 0 Dislike
我鐘意返工返學 2024-01-17 13:01:10
https://web.archive.org/web/20110219163448/http://howtohft.wordpress.com/2011/02/15/how-to-build-a-fast-limit-order-book/

想知呢個approach general嚟講係咪optimal?

呢個approach係用red black tree store個Limit

Order係一個linked list同會point to 相對Limit

每個Limit都會store head Oeder同 tail Order

有個hashmap store曬所有Order

一個pointer to smallest Limit
一個pointer to highest Limit

Time complexity:

Add Order: O(logN) for Traversing binary tree, O(1) for adding Order to linked list and Hashmap

Cancel Order: O(1), use hashmap for quick reference

Execute Order: O(1), use smallest or highest limit pointer to get the limit for Buy order or Sell order. Remove Order in linked list takes O(1)

而家諗緊有冇可能可以用array而唔洗用linked list
Stefan 2024-01-17 13:56:59
咁點解唔用RMQ data structure或者搞個interval/segment tree?

https://en.wikipedia.org/wiki/Range_minimum_query#:~:text=6%20External%20links-,Definition,r%5D.

我鐘意返工返學 2024-01-17 14:29:42
我覺得RMQ喺呢個situation唔係必須?
Limit order book淨係需要return lowest or highest price 唔需要query一個range
b42b82 2024-01-18 12:24:45
吹水台自選台熱 門最 新手機台時事台政事台World體育台娛樂台動漫台Apps台遊戲台影視台講故台健康台感情台家庭台潮流台美容台上班台財經台房屋台飲食台旅遊台學術台校園台汽車台音樂台創意台硬件台電器台攝影台玩具台寵物台軟件台活動台電訊台直播台站務台黑 洞