What is the most efficient way to merge 2 large lists, based on a timestamp, in C#?

Question

I have 2 lists of data, Events and Heartbeats.

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; }
    }

My goal is to populate the RelevantHeartbeats array for each RunEvent in the list of RunEvents with any Heartbeats that occur +- 1 second within the EventDateUtc of the RunEvent. Each list can have 100K plus items, so efficiency is paramount. This is the code I have tried, but it is terribly inefficient:

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();
            }

Appreciate the help in advance.

Answer 1

You can pre-sort heartbeats. And search for left and right range borders with BinarySearch.

var heartbeatsArray = heartbeats.ToArray();
var heartbeatsTime = heartbeats.Select(hb => new DateTime?(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();
}