如何优化查询未平仓股份数的O(m*n)朴素算法？

问题背景 #

给定交易系统的订单日志，每个订单包含以下属性：

• order_token：唯一订单ID
• shares：股份数量
• price：每股价格
• side：false=卖出，true=买入
• created_at：订单创建时间戳（有效区间起始，包含）
• cancelled_or_executed_at：订单结束时间戳（有效区间结束，不包含）

每个查询给定一个query_time，需要计算该时间点所有有效订单的未平仓股份总数（买入和卖出的股份数直接累加，比如买入10股+卖出10股合计20股）。

现有朴素解法为O(m*n)复杂度（m是查询次数，n是订单数），当m或n较大时效率极低，需要优化。

现有朴素实现 #

def calculate_outstanding_shares(orders, queries):
    result = {}

    for query in queries:
        live_trades = 0
        for order in orders:
            if order[4] <= query < order[5]:
                live_trades += order[1]
                
        result[query] = live_trades

    return result


# 示例使用
orders = [
    [3, 15, 200, True, 2000, 4000],
    [1,10,100,True,0,5000],
    [4, 25, 250, False, 2500, 6000],
    [2,20,150,False,1000,3000],
]

queries = [
    500,  # 所有订单之前
    1500,  # 在第一个买入订单有效期内
    2500,  # 在两个买入订单有效期内，且第二个卖出订单开始
    3500,  # 在第二个卖出订单有效期内，第一个卖出订单已结束
    5500  # 所有订单结束后
]

result = calculate_outstanding_shares(orders, queries)
print(result)

优化方案：差分事件+排序+二分查找 #

核心思路是把区间增减转化为单点事件，通过预处理将查询复杂度降到O(logn)，整体复杂度为O(nlogn + mlogn)，适合大数量级的订单和查询。

具体步骤 #

1. 生成事件点：对每个订单，生成两个事件：
   • 在created_at时间点，股份数增加shares
   • 在cancelled_or_executed_at时间点，股份数减少shares
2. 排序事件：将所有事件按时间戳从小到大排序；若时间戳相同，先处理减事件，再处理加事件（避免时间点刚好在结束时误算）
3. 预处理前缀和数组：遍历排序后的事件，计算累计股份数，同时记录对应的时间点，形成一个有序的(时间戳, 累计股份)列表
4. 查询处理：对每个查询时间，用二分查找找到第一个大于该时间的事件位置，取前一个位置的累计股份数即为结果

优化后的Python实现 #

def calculate_outstanding_shares_optimized(orders, queries):
    events = []
    for order in orders:
        shares = order[1]
        start = order[4]
        end = order[5]
        events.append((start, shares))
        events.append((end, -shares))
    
    # 排序：时间升序，时间相同时减事件在前（保证结束时间点不算入有效）
    events.sort(key=lambda x: (x[0], x[1]))
    
    # 预处理时间点和前缀和
    times = []
    prefix_sums = []
    current_sum = 0
    for time, delta in events:
        times.append(time)
        current_sum += delta
        prefix_sums.append(current_sum)
    
    # 处理查询
    result = {}
    for q in queries:
        # 找第一个大于q的时间点索引
        import bisect
        idx = bisect.bisect_right(times, q)
        result[q] = prefix_sums[idx-1] if idx > 0 else 0
    
    return result


# 测试示例
orders = [
    [3, 15, 200, True, 2000, 4000],
    [1,10,100,True,0,5000],
    [4, 25, 250, False, 2500, 6000],
    [2,20,150,False,1000,3000],
]

queries = [500, 1500, 2500, 3500, 5500]
result = calculate_outstanding_shares_optimized(orders, queries)
print(result)

C++实现思路 #

如果要转回C++，可以按以下方式实现：

• 用vector<pair<int, int>>存储事件，其中第一个元素是时间戳，第二个是股份变化量
• 对vector排序，排序规则：先按时间升序，时间相同则变化量小的在前（减事件先处理）
• 预处理前缀和数组，同时记录时间点
• 查询时用lower_bound或upper_bound找到对应位置，获取前缀和

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