json - 从哈希表中查找某个范围内的键的最佳算法

Question

问题

从下面的项目列表中，我需要通过识别具有给定值的键范围来访问该项目，例如，如果该值是 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
.
.

问题上述解决方案的问题是文件大小会增加，这会导致我的紧凑型应用程序中的堆溢出

解决方案2

？

Answer 1

哈希表不太适合这个问题，因为当您可能查找的所有键都存储在表中时，哈希表的工作效果最好:您已经说过您没有足够的内存。二分搜索确实是一个很好的方法，但是你提到......

The key range is in sorted array binary search maybe expensive as these are not direct numbers hence parsing converting from DMS to decimal and then performing comparison could have a performance issue, this function to be triggered every second.

首先，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", &degree, &minute, &second) == 3)
    // have parsed a valid key...

解析完 key 后，您可以合理地:

1) 有std::map<tuple<int8_t, int8_t, int8_t>, Value> values;和二分搜索 std::make_tuple(degree, minute, second) ，或

2) 有std::map<int, Value> values;和二分搜索 degree * 3600 + minute * 60 + second - 总秒数值，您的计算机可能会或可能不会更快地进行比较。

    不过乘法有点慢，所以 (degree << 12) + (minute << 6) + second可以用来避免这种情况，因为六位足以存储 0 到 59 之间的值。

当然，您为创建 key 所做的任何转换都需要在解析 json 文件和填充表时提前使用。

为了进行更多优化，您可以拥有一个 360 度 map 数组，并在您想要查找分钟和秒分量的特定 map 中建立索引。在进行每次映射查找时，将搜索空间除以 360 预计可以消除 8 或 9 次比较(因为每次比较都会将仍在争用的元素数量减半，而 360 介于 2^8 和 2^9 之间)。