c# - 按属性搜索最快的 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

The ranges do not overlap, but may be sparse.

如果我没理解错的话，这意味着如果您按 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;
    };
}