求一个算法思路 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求一个算法思路

求一个算法思路# JobHunting - 待字闺中

h*62017-02-03 08:02

1 楼

一个简化的 order matching system.
匹配 sell/buy 的order, 只根据时间，不根据成交价格高低
price quantity
1. sell 120 10
2. sell 200 10
3. sell 100 10
4 buy 150 15
5 buy 200 5
交易完成后是
2. sell 200 5
3. sell 100 5
不知道怎么实现价格匹配最好
最简单的实现是一个list, 按时间顺序插入节点，有一个order来，从头遍历每个节点
，价格合适就trade. 但这样实现会不会太慢。
但这个不要求trade根据价格来，所以也没办法用价格做key 来做map. 请教各位有啥更
好的方法吗？
谢谢

n*r2017-02-03 08:02

2 楼

没太搞明白你这个是干啥用的。是面试题吗？
既然是order matching system，应该从System Design的角度考虑。
至少要用数据库吧，这样算法的那点复杂度基本可以直接忽略，因为硬盘操作和内存操
作不是一个数量级的。加快速度用cache，然后数据量大了分布式存储。
纯算法的话可以用生产者消费者吧，但是因为根据时间来定，用不了多线程。
可以用两个Queue，一个是Buy的，一个是Sell的，生产者简单就是根据Order类型入对
，消费者是从两个队列的头部开始比较，决定如何Trade。