0/ this code can efficiently maintain a limit order book but you wouldn't believe it
1/ most likely, when implementing a limit order book, you will find yourself using self-balancing search trees (even if they are already implemented for you, e.g. std::map in C++ STL is a red-black tree) to end up with O(logN) per level update
2/ you can replace O(logN) with O(1) when an existing level is just being updated without insertion/deletion by adding a hash table, but that'll be one more tricky data structure and same overall time complexity
3/ obviously, better complexity doesn't mean faster execution, and in reality a hash table might greatly improve your implementation time-wise. you can go further with custom memory allocators, processor instructions and who knows what else, ending up with an artwork
4/ but there's something that not only takes few lines of code in any programming language and doesn't rely on any library but also has every operation working in O(1) and is pretty fast in reality
5/ there's a simple data structure called trie (also known as prefix tree), which is typically used with strings as keys. any $btc price is easily convertible to a string (e.g. 12345.67 -> "1234567"), and can therefore be a key
6/ more importantly, comparing these strings lexicographically is the same as comparing the original values because as of now they would all have an equal length of 7 (and even if they didn't, we would be able to easily solve this with extra leading 0s)
7/ with that in mind, you can find min/max price in a trie by simply traversing it in the right order (always traverse by the edge with the smallest digit on it when searching for min and vice versa) - it works in constant time
8/ apart from that, it's also easy to find kth order statistic or answer a query of form "what is the total size of orders placed between x and y?", just need to maintain counts/sizes for every subtree and traverse accordingly
9/ a simple C++ implementation within 20 meaningful lines of code handles a billion updates in under a minute on my mac, pretty inefficient memory access but still faster than STL containers by a magnitude - gist.github.com ob = 2x trie (bid+ask)
10/ thanks for coming to my ted talk
Loading suggestions...