C#中高效匹配RunEvent与±1秒内Heartbeat的最优方案

问题分析 #

原实现的核心问题是时间复杂度为O(n*m)：每个RunEvent都要遍历全部Heartbeat列表（10万+条），10万次循环下来总操作量超过10^10次，完全无法满足性能要求。

优化思路 #

通过预排序+二分查找将时间复杂度降至O(m log m + n log m)，其中m是Heartbeat数量，n是RunEvent数量，适合处理百万级数据：

1. 先对Heartbeat列表按EventDateUtc排序（一次性开销）；
2. 对每个RunEvent，计算时间范围（前后1秒），用二分查找快速定位该范围内的Heartbeat边界；
3. 直接提取边界内的子列表作为匹配结果。

具体实现代码 #

1. 定义日期比较器（用于二分查找） #

public class HeartbeatDateComparer : IComparer<Heartbeat>
{
    public int Compare(Heartbeat x, Heartbeat y)
    {
        return x.EventDateUtc.CompareTo(y.EventDateUtc);
    }
}

2. 优化后的匹配逻辑 #

private const double RelevantHeartbeatThresholdMs = 1000;

// 第一步：预排序Heartbeat列表（仅需执行一次）
heartbeats.Sort(new HeartbeatDateComparer());

// 第二步：遍历每个RunEvent，用二分查找快速匹配
foreach (var runEvent in runEvents)
{
    var startTime = runEvent.EventDateUtc.AddMilliseconds(-RelevantHeartbeatThresholdMs);
    var endTime = runEvent.EventDateUtc.AddMilliseconds(RelevantHeartbeatThresholdMs);

    // 找左边界：第一个EventDateUtc >= startTime的索引
    int leftIndex = heartbeats.BinarySearch(new Heartbeat { EventDateUtc = startTime }, new HeartbeatDateComparer());
    leftIndex = leftIndex < 0 ? ~leftIndex : leftIndex;

    // 找右边界：第一个EventDateUtc > endTime的索引
    int rightIndex = heartbeats.BinarySearch(new Heartbeat { EventDateUtc = endTime }, new HeartbeatDateComparer());
    if (rightIndex < 0)
    {
        rightIndex = ~rightIndex;
    }
    else
    {
        // 若存在多个等于endTime的Heartbeat，需定位到第一个超出范围的位置
        while (rightIndex < heartbeats.Count && heartbeats[rightIndex].EventDateUtc == endTime)
        {
            rightIndex++;
        }
    }

    // 提取匹配的Heartbeat子列表
    if (rightIndex > leftIndex && leftIndex < heartbeats.Count)
    {
        runEvent.RelevantHeartbeats = heartbeats.GetRange(leftIndex, rightIndex - leftIndex);
    }
    else
    {
        runEvent.RelevantHeartbeats = new List<Heartbeat>();
    }
}

额外优化建议 #

• 如果RunEvent列表也允许排序，可以使用双指针法进一步将时间复杂度降至O(m log m + n log n + m + n)，避免多次二分查找的开销；
• 若内存紧张，可避免使用GetRange创建新列表，改为直接迭代边界内的元素并添加到RelevantHeartbeats（减少内存分配）；
• 确保EventDateUtc均为UTC时间，避免时区转换带来的误差和性能损耗。

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