双拍卖匹配系统中数组快速匹配与出清价格高效计算咨询

双向拍卖出清价格高效计算方案 #

核心优化思路 #

你原有实现的时间复杂度为O(N*M)，N为价格档位总数，M为订单总数量，当价格档位粒度极细时性能会大幅退化。我们可以通过同价订单聚合、前缀/后缀和计算、二分查找的组合方案，将整体时间复杂度降至O(M + logK)（K为存在有效订单的价格档位数量，远小于总价格档位数量），完全不需要遍历所有价格档位。

具体实现步骤 #

• 聚合同价格档位的订单量：将同一价格的所有买单、卖单分别合并，得到每个价格对应的总买量、总卖量，避免重复计算
• 计算累计供需数组：
  • 累计需求（后缀和）：按价格从低到高排序，每个价格对应的值为所有报价≥该价格的买单总数量，该数组随价格上升单调递减
  • 累计供给（前缀和）：按价格从低到高排序，每个价格对应的值为所有报价≤该价格的卖单总数量，该数组随价格上升单调递增
• 二分查找出清价格：利用累计供需数组的单调性，直接二分查找第一个满足「累计需求 < 累计供给」的价格，即可得到出清价，对应出清量为该价格下两个累计值的较小值

优化后Python示例代码 #

import numpy as np

MAX_QTY = 100
MIN_QTY = 0
MIN_PX = 1
MAX_PX = 10001 # 模拟10000个细粒度价格档位
TICK_SIZE = 1

price_grid = np.arange(MIN_PX, MAX_PX, TICK_SIZE)

def gen_orders(num, price_grid):
    qty = np.random.randint(MIN_QTY, MAX_QTY, num)
    px = np.random.choice(price_grid, num)
    return np.array((px, qty)).T

buy = gen_orders(100, price_grid)
sell = gen_orders(100, price_grid)

# 1. 按价格聚合买单、卖单
buy_agg = np.zeros(MAX_PX, dtype=np.int64)
for px, qty in buy:
    buy_agg[px] += qty
sell_agg = np.zeros(MAX_PX, dtype=np.int64)
for px, qty in sell:
    sell_agg[px] += qty

# 2. 计算累计需求（后缀和）、累计供给（前缀和）
cum_demand = np.cumsum(buy_agg[::-1])[::-1]
cum_supply = np.cumsum(sell_agg)

# 3. 二分查找出清价，10000个档位仅需最多14次迭代
low, high = MIN_PX, MAX_PX - 1
cleared_px = MAX_PX - 1
while low <= high:
    mid = (low + high) // 2
    if cum_demand[mid] < cum_supply[mid]:
        cleared_px = mid
        high = mid - 1
    else:
        low = mid + 1

cleared_qty = min(cum_demand[cleared_px], cum_supply[cleared_px])

额外优化提示 #

如果价格档位总数超过10万级，还可以仅收集存在有效订单的价格档位，排序后再计算前缀/后缀和、做二分查找，不需要初始化全量价格数组，进一步降低内存开销和计算量。

低级别语言迁移说明 #

迁移到C/C++/Rust等语言时，可直接用栈/堆数组存储各价格档位的买卖总量，前缀和、后缀和遍历数组即可完成，二分逻辑和上述代码完全一致，不需要依赖任何第三方库，执行效率会更高。

内容的提问来源于stack exchange，提问作者apocalypsis