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

本文关键字：集合 属性 搜索 | 更新日期: 2023-09-27 17:58:15

我有以下简单的类：

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之间（包括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稍快。任何关于使用最有效的集合类或更好的查找的建议都将不胜感激。

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

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

如果我理解正确，这意味着如果你按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;
    };
}

您是否可以不按StartRange排序，使用Array.BinarySearch查找最近的一个（仍然较小），并且由于您的范围很稀疏，只需一次检查（如果Endrange大于x）就可以知道您是否找到了一个或遗漏了一个
您所要做的就是以StartRange为密钥来实现IComparable<T>，这很容易。

可能不是您真正需要的，但您研究过NoSQL吗？有些实现就像您想要的一样，有些实现有一个可以从内存中运行的缓存，所以应该很快。

如果我没记错的话，Redis可能是你想要调查的。（这是一篇关于Redis的文章）。

K、 对我的东西进行了一些挖掘：NoSQL DB comparison，你可以在那里看到主要的风格以及它们适合哪些用例。

据我所见，他们在一些实现中使用B树来提高速度。如果你想重新创建轮子，我想你可能想做一些类似的事情。

如果您的范围现在或将来可能重叠，您可以考虑使用间隔树。

但是，如果你真的确定你的范围没有重叠，那么把你的class改为struct，然后做下面的事情。将class更改为struct的原因有两个：

  • 使用数组保存内存。引用类型数组是对堆上单个对象的引用数组。

  • 可能更重要的是，它有助于保留引用的位置。您将在一个连续的内存块中跳来跳去，而不是在整个堆中随机跳去。这应该有助于减少寻呼。

这是代码：

class MyClassMap
{
    MyClass[] backingStore ; // ordered by StartRange, then EndRange
    public MyClassMap( IEnumerable<MyClass> source )
    {
        backingStore.OrderBy( x => x.StartRange ).ThenBy( x => x.EndRange ) ;
    }
    public int? GetIdFromValue( long value )
    {
        int  lo = 0 ;
        int  hi = backingStore.Length ;
        int? ix = null ;
        while ( lo <= hi && !ix.HasValue )
        {
            int mid = lo + ((hi-lo)>>1) ;
            MyClass current = backingStore[mid] ;
            if      ( value > current.EndRange   ) { lo = mid+1      ; }
            else if ( value < current.StartRange ) { hi = mid-1      ; }
            else                                   { ix = current.Id ; }
        }
        return ix ;
    }
}
相关文章：