高效搜索的数据结构

Question

我希望您能为以下场景提供适当的数据结构建议。我已经定义了键的最小值和最大值，例如：

Key          Min Value                Max Value

key1          0 .5                    4.5
key2          1                       9
key3          0.75                    1.5

我需要将每个值进一步分成子桶，以使最小值和最大值之间的差异不能超过1，并且每个桶的最小值将增加0.5。

例如，key1将进一步分解

Key               Bucket   Min Value                Max Value
key1             B1       0.5                      1.5
key1             B2       1                        2
key1             B3       1.5                      2.5
key1             B4       2                        3
key1             B5       2.5                      3.5
key1             B6       3                        4
key1             B7       3.5                      4.5

一旦我创建了这些桶（仅一次），我需要找到给定键和值的合格桶。

例如，键1和2.2的合格桶是B3和B4。

目前，我将所有桶存储在std :: map >中，

其中Buckets是具有存储桶名称，最小值和最大值的结构体变量。

除了std :: map >之外，我可以使用哪些其他替代方案来加快搜索过程？

- Geek

---

如果你的 map 很大，且不会经常更新，你可以考虑用 unordered_map 替换它，这可能会通过 Key 提供更快的查找速度。在这种情况下，桶被保证以 0.5 的增量递增，你可以立即从 2 * int(value - min_value) 中找到 vector<Bucket> 中的索引。就像任何优化一样，请确保对其进行分析 :-) - ChrisD

Answer 1

在现代硬件上，对于一个 std::vector 的线性搜索（或者如果它已经排序，则使用 std::binary_search）表现得出奇制胜。连续的内存布局非常友好，适合缓存层次结构和预取器。尽管类似于 BigO 的东西会告诉你 std::vector 通常会击败需要在整个内存中追踪指针的基于节点的容器（即使是在时间复杂度上），但是你总是需要为你的特定用例基准测试不同的解决方案，以确保。

- Jesper Juhl

Answer 2

你可以将所有记录放入一个 std::vector 中，然后使用 std::map<key, vector-index>。这被称为创建索引表。

对于小量数据，线性搜索与使用索引表无区别（实际上可能更快）。

在互联网上搜索“第一范式”，了解优化数据的方法。

- Thomas Matthews