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

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

方案一： 以下是我目前尝试过的解决方案

重新创建新的 key/value (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

散列 table 不太适合解决此问题，因为当您可能查找的所有键都存储在 table 中时，散列 table 的效果最好：您已经说你没有那个记忆。二进制搜索确实是一个很好的方法，但是你提到...

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++ 程序可以在一秒钟内完成很多的工作——即使是未优化的查找也可能足够快地工作，但让我们假设您确实需要更接近最佳速度的那一刻...

"parsing from DMS" 是模糊的，但我假设你的意思是你有一个键的文本表示，例如“2.1.1”进入你的程序：解析它几乎肯定比必须解析它更好使用文本比较进行查找。要解析 "C++ style" 中的文本，您只需使用...

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...

解析密钥后，您可以合理地：

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 之间的值。

当然，在解析 json 文件和填充 table.

时，无论您为创建密钥所做的任何转换都需要在之前使用过

为了进一步优化，您可以拥有一个 360 度地图数组，并在您想要查找分钟和秒组件的特定地图中建立索引。将搜索 space 除以 360 可以预期在每次地图查找时消除 8 或 9 次比较（因为每次比较都会将仍在竞争的元素数量减半，而 360 介于 2^8 和 2^9 之间） .

Answer 2

由于您在第一个 json 中的条目已按顺序排序，您可以解析您的输入并使用它来计算位置并生成条目的键。

对于第一个列表，我会将输入值解析为 3 个整数。对于这个，我们只需要输入的第一部分（学位）。然后我们得到这样的位置：

 int position = input_degree / step_size;

step_size 在您的第一个列表中将是 30。

如果您需要密钥，您现在可以使用以下位置生成它：

String key_begin = position * step_size;
String search_key = key_begin + ".0.0-" + key_begin+step_size + ".0.0";

Answer 3

使用 KD 树或 R 树数据结构而不是哈希映射。

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

Best algorithm to find a key within a range from hashtable

json

hashtable

hashmap