针对+5M记录表的快速内存范围查找

本文关键字：内存 范围 查找 +5M 记录表 针对 | 更新日期: 2023-09-27 18:02:35

我有一个包含+5M静态记录的数据库表。简单的结构:(开始int，结束int，结果int)。所以我有一个特定的INT，我需要找到它对应的结果(INT)。目前，查找表是在DB中，但它需要驻留在内存中，最有可能是在没有数据库访问的环境中。

我的解决方案需要在没有数据库访问的情况下执行此逻辑，在内存中并且速度超快，因为我需要每秒处理1000个事务。集合的大小只有50MB多一点，所以我可以把所有的东西都放到内存中，然后对它进行范围查找，根据这篇文章:在c#中进行范围查找-如何实现。但我不知道它在这样的规模下会有怎样的表现。

  • 我预加载表"启动"?可能要花点时间。
  • 任何方法加载表到一些。dat文件，并有超级高效的查找在运行时?

顺便说一句，我在Azure上，不确定使用存储表是否有助于查找…

针对+5M记录表的快速内存范围查找

二进制搜索超级快。对5000万条记录进行二分查找只需要27次比较就能找到答案。只需将其加载到内存中并使用您链接的范围查找。

如果你发现它很慢，开始优化:

  • 将Range对象更改为struct而不是class
  • 手工编写自己的二进制搜索算法，(a)直接实现相等比较器，而不是调用IEqualityComparer; (b)使用指针和其他不安全的技巧，在进行搜索时禁用数组边界检查。

您链接到的范围查找代码执行二进制搜索，因此性能将为O(log n)。我不认为你能做的比查找范围更好。一个HashSet<T>的查找是0(1)，但是你不能使用这个结构进行范围查找。

500万条记录并不是一个很大的数目。我建议您在将用于生产的硬件上使用链接到的代码实现概念验证，并测量性能。

您当然可以将其放在顺序文件中，并在启动时加载它。50mb将在不到一秒的时间内从磁盘上删除。即使必须将其解析为文本文件，也应该能够在另一秒钟内创建表。当你用2 GHz(或更快)的处理器处理它们时，500万条记录并不是那么大。

对列表的二分搜索是O(log n)，所以每次搜索的最大探测次数是24。那可真他妈快。

这样的加载测试应该很容易。把它旋转一下，然后看看需要多长时间，比如说，1,000,000次查找。比如:

var clock = Stopwatch.StartNew();
for (int i = 0; i < NumIterations; ++i)
{
    int val = GetRandomValueToSearchFor(); // however you do that
    Ranges.BinarySearch(val, RangeComparer);
}
clock.Stop();
// time per iteration is clock.TotalMilliseconds/NumIterations

这会让你计算出查询的绝对最快速度。我认为每秒处理数千个事务是可以接受的。

相关文章：