From f99dcdf422310400fe9f20f61697328e87485a34 Mon Sep 17 00:00:00 2001
From: Joel Grunbaum <joelgrun@gmail.com>
Date: Wed, 19 Jan 2022 09:57:14 +0000
Subject: [PATCH] Insertion sort sides instead of hashmap
---
test.cpp | 42 ++++++++-----
book.cpp | 28 +++------
book.hpp | 4
protocol.cpp | 64 +++++++++++++++------
4 files changed, 82 insertions(+), 56 deletions(-)
diff --git a/book.cpp b/book.cpp
index 573fa75..1ee1d06 100644
--- a/book.cpp
+++ b/book.cpp
@@ -92,40 +92,30 @@
void Book::ask(Order& order)
{
- auto a = this->askSide.emplace(order.id, order);
- if (!a.second) {
- std::cout << order.id << "already exists" << std::endl;
- }
+ Level a(order);
+ auto b = std::lower_bound(this->askSide.begin(), this->askSide.end(), a);
+ this->askSide.insert(b, a);
}
void Book::bid(Order& order)
{
- auto a = this->bidSide.emplace(order.id, order);
- if (!a.second) {
- std::cout << order.id << "already exists" << std::endl;
- }
+ Level a(order);
+ auto b = std::upper_bound(this->bidSide.begin(), this->bidSide.end(), a);
+ this->bidSide.insert(b, a);
}
void Book::printBook(std::size_t numOrders)
{
std::cout << "Sell side: " << this->askSide.size() << std::endl;
- std::vector<Level> askCopy;
- for (auto i : this->askSide)
- askCopy.push_back(i.second);
- std::size_t count = 0;
- std::sort(askCopy.begin(), askCopy.end());
- for (auto i = askCopy.rbegin(); i != askCopy.rend(); i++) {
+ std::size_t count = 0;
+ for (auto i = this->askSide.rbegin(); i != this->askSide.rend(); i++) {
std::cout << *i << std::endl;
count++;
if (count > numOrders) break;
}
std::cout << "Buy side: " << this->bidSide.size() << std::endl;
- std::vector<Level> bidCopy;
- for (auto i : this->bidSide)
- bidCopy.push_back(i.second);
count = 0;
- std::sort(bidCopy.begin(), bidCopy.end());
- for (auto i = bidCopy.rbegin(); i != bidCopy.rend(); i++) {
+ for (auto i = this->bidSide.rbegin(); i != bidSide.rend(); i++) {
std::cout << *i << std::endl;
count++;
if (count > numOrders) break;
diff --git a/book.hpp b/book.hpp
index 5d952a3..61a68d5 100644
--- a/book.hpp
+++ b/book.hpp
@@ -43,8 +43,8 @@
std::ostream& operator<<(std::ostream& out, const Level& a);
struct Book {
- std::unordered_map<std::string, Level> bidSide;
- std::unordered_map<std::string, Level> askSide;
+ std::vector<Level> bidSide;
+ std::vector<Level> askSide;
ProductTypeEnum productType;
std::string product;
int stationId;
diff --git a/protocol.cpp b/protocol.cpp
index a4b8475..f1083c0 100644
--- a/protocol.cpp
+++ b/protocol.cpp
@@ -175,31 +175,57 @@
json::DeletedMessage* message)
{
if (message->side == book::Buy) {
- bs[message->product].bidSide.erase(message->id);
+ for (auto i = bs[message->product].bidSide.begin(); i != bs[message->product].bidSide.end(); i++) {
+ if (i->id == message->id) {
+ bs[message->product].bidSide.erase(i);
+ break;
+ }
+ }
} else {
- bs[message->product].askSide.erase(message->id);
+ for (auto i = bs[message->product].askSide.begin(); i != bs[message->product].askSide.end(); i++) {
+ if (i->id == message->id) {
+ bs[message->product].askSide.erase(i);
+ break;
+ }
+ }
}
}
void tradeOrder(std::unordered_map<std::string, book::Book>& bs,
json::TradeMessage* message)
{
- if (bs.find(message->passiveOrder) != bs.end()) {
- if (message->tradeType == json::BUY_AGGRESSOR) {
- if (message->passiveOrderRemaining > 0) {
- bs[message->product].askSide.at(message->passiveOrder).volume =
- message->passiveOrderRemaining;
- } else {
- bs[message->product].askSide.erase(message->passiveOrder);
- }
- } else if (message->tradeType == json::SELL_AGGRESSOR) {
- if (message->passiveOrderRemaining > 0) {
- bs[message->product].bidSide.at(message->passiveOrder).volume =
- message->passiveOrderRemaining;
- } else {
- bs[message->product].bidSide.erase(message->passiveOrder);
- }
- }
- }
+ if (message->tradeType == json::BUY_AGGRESSOR) {
+ if (message->passiveOrderRemaining > 0) {
+ for (auto& i : bs[message->product].askSide) {
+ if (i.id == message->passiveOrder) {
+ i.volume = message->passiveOrderRemaining;
+ break;
+ }
+ }
+ } else {
+ for (auto i = bs[message->product].askSide.begin(); i != bs[message->product].askSide.end(); i++) {
+ if (i->id == message->passiveOrder) {
+ bs[message->product].askSide.erase(i);
+ break;
+ }
+ }
+ }
+ } else if (message->tradeType == json::SELL_AGGRESSOR) {
+ if (message->passiveOrderRemaining > 0) {
+ for (auto& i : bs[message->product].bidSide) {
+ if (i.id == message->passiveOrder) {
+ i.volume = message->passiveOrderRemaining;
+ break;
+ }
+ }
+ } else {
+ for (auto i = bs[message->product].bidSide.begin(); i != bs[message->product].bidSide.end(); i++) {
+ if (i->id == message->passiveOrder) {
+ bs[message->product].bidSide.erase(i);
+ break;
+ }
+ }
+ }
+ }
}
void broker(std::unordered_map<std::string, book::Book>& bs,
diff --git a/test.cpp b/test.cpp
index 1617c70..6226a44 100644
--- a/test.cpp
+++ b/test.cpp
@@ -7,23 +7,33 @@
#include <unistd.h>
#include <unordered_map>
+constexpr int trials = 1000000;
+
int main(void)
{
- // book::Book b = book::testBook(10, true);
- auto bs = protocol::recoverBook();
+ std::chrono::nanoseconds time(0);
+ for (int i = 0; i < trials; i++)
+ {
+ auto s = std::chrono::high_resolution_clock::now();
+ book::Book b = book::testBook(100, false);
+ auto e = std::chrono::high_resolution_clock::now();
+ time += e - s;
+ }
+ std::cout << time.count() / trials << std::endl;
+ // auto bs = protocol::recoverBook();
// protocol::catchUp(bs);
- // std::cout << bs.size() << std::endl;
- // for (auto i : bs) {
- // std::cout << i.first << std::endl;
- // i.second.printBook();
- // }
- bom::initialise();
- bom::updateBom(bs);
- bom::destroy();
- protocol::catchUp(bs);
- std::cout << bs.size() << std::endl;
- for (auto& i : bs) {
- std::cout << i.first << ", " << i.second.expiry.count() << ", " << i.second.bomPrice << std::endl;
- i.second.printBook();
- }
+ // std::cout << bs.size() << std::endl;
+ // for (auto i : bs) {
+ // std::cout << i.first << std::endl;
+ // i.second.printBook();
+ // }
+ // bom::initialise();
+ // bom::updateBom(bs);
+ // bom::destroy();
+ // protocol::catchUp(bs);
+ // std::cout << bs.size() << std::endl;
+ // for (auto& i : bs) {
+ // std::cout << i.first << ", " << i.second.expiry.count() << ", " << i.second.bomPrice << std::endl;
+ // i.second.printBook();
+ // }
}
--
Gitblit v1.9.3