在 C# 中基于时间戳合并 2 个大型列表的最有效方法是什么？

Question

我有 2 个数据列表，事件和心跳。

public class RunEvent : EntityBase
    {
        public DateTime EventDateUtc { get; set; }
        public List<Heartbeat> RelevantHeartbeats { get; set; } = new List<Heartbeat>();
    }

public class Heartbeat : EntityBase
    {
        public string Image { get; set; } = string.Empty;
        public DateTime EventDateUtc { get; set; }
    }

我的目标是用 RunEvent 的 EventDateUtc 内 +- 1 秒内发生的任何心跳填充 RunEvents 列表中每个 RunEvent 的 RelevantHeartbeats 数组。每个列表可以有 100K 多个项目，因此效率至关重要。这是我尝试过的代码，但效率非常低：

private const double RelevantHeartbeatThresholdMs = 1000;

foreach (var runEvent in runEvents)
            {
                runEvent.RelevantHeartbeats = heartbeats.Where(hb => 
                    runEvent.EventDateUtc > hb.EventDateUtc.AddMilliseconds(RelevantHeartbeatThresholdMs * -1) &&
                    runEvent.EventDateUtc < hb.EventDateUtc.AddMilliseconds(RelevantHeartbeatThresholdMs)).ToList();
            }

提前感谢您的帮助。

Answer 1

您可以预先排序心跳。并使用 BinarySearch 搜索左右范围边界。

var heartbeatsArray = heartbeats.ToArray();
var heartbeatsTime = heartbeats.Select(hb => hb.EventDateUtc).ToArray();
Array.Sort(heartbeatsTime, heartbeatsArray);


foreach (var runEvent in runEvents)
{
    var leftTime = runEvent.EventDateUtc.AddMilliseconds(relevantHeartbeatThresholdMs * -1);
    var leftIndex = Array.BinarySearch(heartbeatsTime, leftTime);
    if(leftIndex < 0) leftIndex = ~leftIndex;
    
    var rightTime = runEvent.EventDateUtc.AddMilliseconds(relevantHeartbeatThresholdMs);
    var rightIndex = Array.BinarySearch(heartbeatsTime, rightTime);
    if(rightIndex < 0) rightIndex = ~rightIndex;
    
    runEvent.RelevantHeartbeats = heartbeatsArray[leftIndex..rightIndex].ToList();
}