c# - 加快从集合中查找数据范围的速度

说我有一堂课

public class TimestampedTrackId
{
    private readonly int trackId;
    private readonly DateTime insertTime;
    public TimestampedTrackId(int trackId, DateTime insertTime)
    {
        this.trackId = trackId;
        this.insertTime = insertTime;
    }

    public int TrackId
    {
        get
        {
            return trackId;
        }
    }

    public DateTime InsertTime
    {
        get
        {
            return insertTime;
        }
    }
}

我有一个List<TimestampedTrackId>类型的大型列表，需要从此列表中提取TimestampedTrackId实例，这些实例的属性InsertTime位于最小和最大DateTime之间。

List<TimestampedTrackId> tracks; //Count=largeNumber
...
tracks.Where(t=>t.InsertTime>min&&t.InsertTime<max)

List<T>显然不是此任务的正确容器，因为它需要搜索每个项目以检查InsertTime是否在最小值和最大值之间。

因此，我假设加快此代码的过程将涉及将列表重新打包到一个更合适的集合中，但是哪个集合呢？

给定正确的集合（可能是有关键字的），我可以使用哪种查询来利用最大查询速度？

提前致谢

最佳答案

您可以按InsertTime对列表进行排序吗？如果是这样，List<T>.BinarySearch是您的朋友-提供一个IComparer<TimestampedTrackId>，将其与InsertTime进行比较，并为BinarySearch和min比较max。 （您需要使用TimestampedTrackId和InsertTime的min值创建“虚拟” max对象才能搜索它们。）

如果BinarySearch返回负值，则应采用按位补码（使用〜运算符）以查找将值插入到的索引。还要记住，如果多个项目可以具有相同的InsertTime，则需要从min索引向后进行操作，并从max索引进行向前进行操作，以确保获得完整的范围。无论如何，它仍然比线性搜索更有效率。坦率地说，这有点麻烦:)