用于按属性搜索的最快 C# 集合

Question

我有以下简单的课程：

public class MyClass{
    public long StartRange { get; set; }
    public long EndRange { get; set; }
    public int Id { get; set; }
}

我需要将许多（10^5 到 10^6）存储在内存缓存中。应用程序启动时将对此缓存进行一次写入，并进行多次读取。在ASP.NET环境下会访问这个缓存，所以线程很多。

我需要在此缓存中查找一行，其中我的值介于 StartRange 和 EndRange 之间（含）。范围不重叠，但可能稀疏。我发现执行此操作的最简单方法如下：

public MyClass Lookup(long value){
    return _set.FirstOrDefault(d => value >= d.StartRange && value <= d.EndRange);
}

我尝试过将集合存储为IOrderedEnumerable<T>和SortedSet<T>。SortedSet 的速度要快一个数量级。HashSet<T>不知何故比 SortedSet 稍微快一些。任何关于最有效的集合类的使用或更好的查找的建议将不胜感激。

Answer 1

范围不重叠，但可能稀疏。

如果我理解正确的话，这意味着如果您按 StartRange 对它们进行排序，然后使用 标识第一个项目value >= d.StartRange，您可以立即知道您已经找到了您的项目（如果value <= d.EndRange），或者没有匹配项，对吗？

因此，您可以通过这样做将时间减少一半：

public MyClass Lookup(long value){
    var candidate = _set.FirstOrDefault(d => value >= d.StartRange);
    if(candidate != null && value <= candidate.EndRange)
    {
        return candidate;
    }
    return null;
}

而且，由于在排序集合中的搜索可以很容易地及时完成O(log n)，因此您应该能够仅通过二分搜索来获得显着的性能提升。这里有一些示例代码，应该可以帮助您走上正确的道路。

List<MyClass> _set = new[]{
   new MyClass{StartRange = 18, EndRange = 18},
    new MyClass{StartRange = 10, EndRange = 15},
     new MyClass{StartRange = 20, EndRange = 21}
}.OrderBy(m => m.StartRange).ToList();

public class StartRangeComparer : IComparer<MyClass>
{
    public int Compare(MyClass first, MyClass second)
    {
        return first.StartRange.CompareTo(second.StartRange);
    }
}

StartRangeComparer startRangeComparer = new StartRangeComparer();

public MyClass Lookup(long value){
    var index = _set.BinarySearch(new MyClass{StartRange = value}, startRangeComparer);
    int candidateIndex = index >= 0 ? index : (~index) - 1;
    if(candidateIndex < 0)
    {
        // the given value is before any start-ranges in the list
        return null;
    }
    MyClass candidate = _set[candidateIndex];
    if(candidate.EndRange >= value)
    {
        return candidate;
    }
    else
    {
        return null;
    };
}