Python中从SortedDict扣除自有订单的高效实现方法

核心优化思路 #

先将分散的自有订单列表转换为统一的字典结构，利用SortedDict的O(log n)键查找/修改/删除特性，彻底规避低效的线性遍历匹配操作。

实现代码 #

from sortedcontainers import SortedDict

# 原始订单簿数据
bids = SortedDict({0.0005: 11.0, 0.006: 10.0, 0.01: 28.6, 0.0105: 21.8, 0.012: 25.1})
# 自有订单列表
own_bids = [{0.006: 10.0}, {0.012: 5.1}]

# 第一步：将自有订单列表转换为统一字典，消除后续重复查找开销
own_bids_dict = {price: qty for bid in own_bids for price, qty in bid.items()}

# 第二步：批量更新订单簿
for price, own_qty in own_bids_dict.items():
    if price in bids:
        remaining_qty = bids[price] - own_qty
        if remaining_qty <= 0:
            del bids[price]
        else:
            bids[price] = remaining_qty

print(bids)
# 输出：SortedDict({0.0005: 11.0, 0.01: 28.6, 0.0105: 21.8, 0.012: 20.0})

原方法性能低下的原因 #

你之前的实现大概率是通过线性遍历SortedDict来匹配自有订单价格，时间复杂度为O(k*n)（k是自有订单数量，n是订单簿总条目数）。而优化后的方案：

1. 转换自有订单为字典是O(k)的线性操作
2. 每个订单的查找/更新/删除都是SortedDict的O(log n)操作
   整体时间复杂度降至O(k log n)，当订单簿条目较多时，性能提升会非常显著。

额外注意事项 #

• 若自有订单中存在重复价格，转换字典时会自动保留最后一个条目；若需要累加重复价格的数量，可在转换时添加累加逻辑
• SortedDict的del操作本身是O(log n)，不会触发大规模结构重排，比频繁遍历删除高效得多

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