内存范围查找+ 5M记录表
我有一个+5M静态记录的数据库表。 简单的结构:(起始int，结束int，结果int）。 所以我有一个特定的INT，我需要找到它的相应结果（INT）。 目前，查找表在DB中，但它需要驻留在内存中，很可能在没有数据库访问的环境中。
我的解决方案需要在没有数据库访问的情况下执行此逻辑，在内存中以及超快的速度，因为我需要每秒处理1000个事务。 该集的大小略超过50MB，所以我可以把整个东西放到内存中，并根据这篇文章来运行范围查找：在C＃中进行范围查找 - 如何实现。 但我不知道它将如何在这样的规模上表现。
顺便说一句，我在Azure上，不确定使用存储表是否有助于查找...
二进制搜索速度非常快。 对50M记录进行二分搜索只需要27次比较即可找到答案。 只需将其加载到内存中并使用链接的范围查找。
如果您发现速度较慢，请开始优化：
IEqualityComparer ;（b）在搜索时使用指针和其他不安全的技巧来禁用数组边界检查。 您链接的范围查找代码执行二分搜索，因此性能将为O(log n) 。 我认为你不可能比范围查找做得更好。 HashSet<T>的查找是O（1），但不能将该结构用于范围查找。
500万条记录并不是一个巨大的数字。 我建议你用你在生产中使用的硬件链接到的代码来实现概念证明，并测量性能。
你当然可以把它放在顺序文件中并在启动时加载它。 在不到一秒的时间内，磁盘就会有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
这将让你找出绝对最快的速度，你可以查询的东西。 我怀疑你会每秒处理数千笔交易。
链接地址: http://www.djcxy.com/p/78891.html