在哈希表范围内查找密钥的最佳算法

问题

从下面的项目列表我将需要通过识别具有给定值的键范围来访问该项目,例如,假设值为2.1.1,这是度,分和秒我需要找到键0.0.0-30.0.0性能是高优先级.

key: 0.0.0-30.0.0   value: x-y-z
key: 30.0.0-60.0.0  value: y-x-z
key: 60.0.0-90.0.0  value: z-y-z

解决方案1: 到目前为止我尝试过以下解决方案

重新创建新的键/值(json)文件,如下所示

key: 0.0.0  value: x-y-z
key: 0.0.1  value: x-y-z
.
key: 0.0.59 value: x-y-z
.
key: 0.1.0 value x-y-z
key: 0.1.1 value x-y-z

key: 30.0.0  value: y-x-z
.
.
key: 30.0.59 value: y-x-z
.
key: 30.1.0 value: y-x-z
key: 30.1.1 value: y-x-z
key: 30.1.2 value: y-x-z
.
.
key: 30.1.59 value: y-x-z
key: 30.2.0 value: y-x-z
key: 30.2.1 value: y-x-z
key: 30-2.3 value: y-x-z
.
.
key: 60.0.0 value: z-y-x
key: 60.0.1 value: z-y-x
key: 60.0.2 value: z-y-x
.
.
key: 60.0.59 value: z-y-x
key: 60.1.0 value: z-y-x
key: 60.1.1 value: z-y-x
.
.

发行(S) 与上述解决方案的问题是,文件大小会增加,这是造成堆溢出在我的紧凑型应用

溶液2

？

哈希表不太适合这个问题,因为哈希表在您查找的所有键都存储在表中时效果最好:您已经说过没有内存.二进制搜索确实是一种很好的方法,但你提到......

关键范围是排序数组二进制搜索可能很昂贵,因为这些不是直接数字,因此解析从DMS转换为十进制然后执行比较可能会产生性能问题,此功能每秒触发一次.

首先,C++程序可以做很多的工作,在一名秒钟的一小部分-甚至是未优化的查找是可能的工作足够快足够了,但我们姑且假设你确实需要更接近最佳速度的时刻...

"从DMS解析"是模糊的,但我假设你的意思是你有一个关键字的文本表示,如"2.1.1"进入你的程序:解析这几乎肯定比使用文本进行查找更好比较.要解析"C++风格"中的文本,您只需使用...

std::istringstream iss(the_incoming_key);
int degree, minute, second;
char c1, c2;
if (iss >> degree >> c1 >> minute >> c2 >> seconds &&
    c1 == '.' && c2 == '.')
{
    // have parsed a valid key...
}
else
    error_throw_exit_whatever();

如果您准备使用较旧的C函数来提高速度,请考虑:

if (sscanf(the_incoming_key.c_str(), "%d.%d.%d", °ree, &minute, &second) == 3)
    // have parsed a valid key...

解析密钥后,您可以合理地:

1)有std::map, Value> values;和二进制搜索std::make_tuple(degree, minute, second),或

2)进行std::map values;二进制搜索degree * 3600 + minute * 60 + second- 计算机比较可能会或可能不会更快的总秒数值.

     一个.乘法虽然有点慢,但(degree <<12) + (minute <<6) + second可以用它来避免它,因为六位足以存储0到59之间的值.

当然,在解析json文件和填充表时,无论你做什么转换都需要先使用.

对于更多优化,您可以拥有360个地图数组,并索引到要查找分钟和秒组件的特定地图.将搜索空间除以360可以预期在执行每个地图查找时消除8或9个比较(因为每个比较将仍处于争用中的元素数量减半,并且360在2 ^ 8和2 ^ 9之间).