如何优化交易算法以获得最有效的速度

Question

假设您想实现一个以以下方式工作的算法:

从包含以下形式值的文件中读取:

Mark Buy  20 1 100
Bob  Sell 20 2 90

其中输入的形式为:

<name><buy or sell><quantity><time><company><buy maximum or sell minimum>

匹配买家和卖家的最快方法是什么(对于某些公司，只有在该公司买得最多的人比卖得最少的人大的时候，买家和卖家才会匹配)。最顶端的买入或卖出将决定使用什么价格。

在上面的例子中，我们有"马克，在时间1，在时间2以100美元从鲍勃那里买了20股谷歌股票。"

我们如何优化这个算法的速度?首先读取整个文件是最优的解决方案吗?

Answer 1

您需要的是每个商品的两个优先队列:一个用于活跃的买入出价(按最高价格优先)，一个用于活跃的卖出出价(按最低价格优先)，再加上一个用于创建/到期出价事件的整体队列(按时间优先)。(如果您的出价如所述在批处理文件中，而不是因果/在线序列，则可以对创建/到期事件进行排序，但仍需要买卖队列)

使用优先级队列是关键;之后的都是管道:

foreach bid creation/expiry event, in chronological order:
  if the event is an expiry:
    delete the bid from the appropriate queue
  else, the event is a creation:
    add the bid to the appropriate queue
    repeat until no further transaction can be performed:
      find max-active-buy and min-active-sell bids for the given commodity
      if they match:
        execute (and record) the transaction
        update partially fulfilled bids, and remove completely fulfilled ones

当作为批处理操作执行时，您可以通过分类每个单独的商品并单独执行每个商品来简化事情。然而，如果市场以任何方式相互作用(例如检查是否有足够的账户余额)，这将不起作用。

---

优先级队列操作在项目数上可以具有O(log N)的渐近性能。有许多快速、实用的优先级队列数据结构可以达到这个渐近极限。

由于您将整个文件作为批处理来评估，因此您可能希望查看具有分摊性能保证的优先级队列——但是如果您希望在实时设置中使用代码，则可能应该坚持使用具有严格的每查询保证的优先级队列。