按属性搜索的最快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之间（包括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略快。请问有关于使用最有效的集合类或更好的查找方法的建议将不胜感激。

- TheGwa

---

试着看看这篇文章，它很好地解释了每个集合类的工作原理。 - Icemanind

可能是重复的问题SortedSet / SortedList with better LINQ performance? - Gusman

请使用 struct 替代 class（并使其不可变）。100万次（8+8+4）字节为20 MB，但使用类会是这个数字的两倍。然后将它们存储在一个排序数组中，并使用二分搜索，就像下面回答的那样。 - Kris Vandermotten

@KrisVandermotten：我很难找到关于对象引用空间要求的信息。您能为您评论中“对于具有两倍大小的类”的部分提供引文吗？ - StriplingWarrior

@StriplingWarrior 这篇关于http://msdn.microsoft.com/en-us/magazine/cc163791.aspx的文章已经相当陈旧了，其中的细节可能已经发生了变化（例如支持64位），但请看一下标题为“ObjectInstance”的部分。它的核心是：堆上的对象具有内存管理和垃圾回收的开销，以支持继承等功能。而结构体则没有这种开销。 - Kris Vandermotten

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

- StriplingWarrior

---

谢谢你的回答。我想你指的是排序列表中的LastOrDefault。请为未来读者提到一些关于结构体的事情。非常感谢。 - TheGwa

@TheGwa：不，我很确定我想要用FirstOrDefault()，因为我希望它从开头开始查找，直到找到一个其“StartRange”在给定值之前（或等于）的对象。然后我希望它快速停止搜索剩余的对象。至于“struct”，就我而言，仍未确定是否使用它是个好主意。我还没有找到足够的信息或者进行足够好的测试来确定这一点。 - StriplingWarrior

Answer 2

你可不可以通过StartRange进行排序，使用Array.BinarySearch查找最接近（但小于）目标值的一个数，并且由于你的范围是稀疏的，只需进行一次检查（如果Endrange大于x），就能知道是否找到了这个数？
要使此方法生效，您需要实现具有StartRange为键的IComparable<T>，这非常容易。

- kat0r

---

你正在正确的轨道上，但情况并不完全那么简单。除非你要查找完全相同的“StartRange”值，否则BinarySearch方法将无法帮助你找到最接近的一个，对吧？ - StriplingWarrior

Array.BinarySearch 应该返回最接近的匹配项，并使用一些位运算技巧（http://msdn.microsoft.com/en-us/library/2cy9f6wb%28v=vs.110%29.aspx）。否则，您需要自己实现 BinSearch，它返回最接近的匹配项（这也很容易实现）。 - kat0r

Answer 3

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

但是，如果您确信您的范围没有重叠，将您的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 ;

    }

}

- Nicholas Carey

Answer 4

可能不是你真正需要的，但你有考虑过NoSQL吗？一些实现方式就像你想要的那样，而且有些具有缓存功能，可以从内存中运行，因此速度应该很快。

如果我没记错的话，Redis可能是你想要研究的一个（这里有一篇关于Redis的文章）。

好的，我在我的资料中找到了：NoSQL数据库比较，你可以看到哪些是主要的类型以及它们适用的用例。

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

- Noctis

---

我们已经在其他解决方案中使用了它。特别是Couchbase，但对于一个非常简单的缓存来说，有相当多的开销。 - TheGwa

完全同意，但仍然指出了其他选择。 - Noctis