2

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

我的解决方案需要在没有数据库访问的情况下在内存中执行此逻辑，并且速度超快，因为我需要每秒处理 1000 次事务。根据这篇文章：Doing a range lookup in C# - how to implement 但我不知道它会在这样的规模上表现如何。

  • 我是否在“启动时”预加载该表？这可能需要一段时间。
  • 有什么方法可以将表格加载到某个 .dat 文件中并在运行时进行超高效的查找？

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

4

3 回答 3

4

二进制搜索非常快。对 50M 条记录进行二分搜索只需 27 次比较即可找到答案。只需将其加载到内存中并使用您链接的范围查找。

如果您发现它很慢，请开始优化：

  • 将 Range 对象更改为 struct 而不是 class
  • 手动编写您自己的二进制搜索算法，该算法 (a) 直接实现相等比较器而不是调用 anIEqualityComparer并且 (b) 在执行搜索时使用指针和其他不安全的技巧来禁用数组边界检查。
于 2013-03-07T03:33:23.753 回答
2

您链接到的范围查找代码执行二进制搜索，因此性能将为O(log n). 我认为对于范围查找，没有比这更好的了。AHashSet<T>的查找是 O(1)，但您不能使用该结构进行范围查找。

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

于 2013-03-07T03:32:50.770 回答
0

你当然可以把它放在一个顺序文件中并在启动时加载它。50 MB 将在不到一秒的时间内从磁盘中取出。即使您必须将其解析为文本文件，您也应该能够在另一秒钟内创建表格。当您使用 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

这会让您找出查询该事物的绝对最快速度。我怀疑你每秒处理数千笔交易会很好。

于 2013-03-07T03:34:48.490 回答