如何高效地在大向量中查找元素

Question

我有一个大小为(90,000 * 9,000)的vector<unsigned>。我需要多次查找这个向量中是否存在一个元素？

为了实现这一点，我使用std::sort()将向量按排序后的形式存储，然后使用std::binary_search()在向量中查找元素。然而，在使用perf进行分析时，我发现在vector<unsigned>中查找元素是最慢的操作。

请问有人能够建议一些在C/C++中使用的数据结构，以便高效地查找(90,000 * 9,000)元素的向量中的元素。

我只进行一次插入（批量插入）。其余时间我只进行查找，因此主要开销是由于查找。

- Steg Verner

---

你是否多次查找相同的元素？如果是，你可以缓存结果。 - Micha Wiedenmann

如果您能以这种方式组织数据，那么Trie应该会更快。 - user541686

@Jagannath 向量具有无符号元素。 - Steg Verner

@marko 我只执行一次插入（批量插入）。其余时间我只执行查找操作，因此这里的主要开销是由于查找操作。 - Steg Verner

@MichaWiedenmann 反复执行二分查找是一个问题...因为我需要执行一百万次二分查找。 - Steg Verner

Answer 1

您已经从 40 亿个可能的值中获得了 8.1 亿个值(假设使用 32 位的 unsigned)。这表示您占用了总范围的五分之一，需要 3.2 GB 的空间。实际上，使用一个包含 40 亿个位的 std::vector<bool> 更好，这将在更少的空间（0.5 GB）中提供 O(1) 查找。

（理论上，unsigned 可能是 16 位。 unsigned long 至少 32 位，std::uint32_t 可能是您想要的类型）

- MSalters

---

我不明白如何使用std::vector<bool>。 - Steg Verner

@StegVerner：简单来说，你可以从一个包含UNIT_MAX个值的向量开始，所有值都为false。要插入42，只需将v[42]=true。要删除42，则将v[42]=false。要检查42是否存在，只需使用if (v[42])即可。 - MSalters

Answer 2

根据向量的实际数据结构，contains操作可能需要O(n)或O(1)的时间。通常情况下，如果向量是由关联数组或链表支持的，则contains操作是O(N)的，最坏情况下需要进行全扫描。您可以通过排序和使用二分查找来减轻全扫描，其时间复杂度为O(log (N))。对于本质上只有O(1)更好的时间复杂度，log N已经具有相当不错的复杂度了。因此，您可以选择以下方案之一：

• 缓存项目的查找结果，如果您有许多重复元素，则这可能是一个很好的折衷方案
• 用其他具有高效contains操作的数据结构替换向量，例如基于哈希表或set的数据结构。请注意，您可能会失去其他特性，如项目排序。
• 使用两个数据结构，一个用于contains操作，原始向量用于其他用途
• 使用第三种数据结构以达到折衷方案，例如适用于布隆过滤器的数据结构

- oleksii

---

问题指定了二分查找，它既不是O(1)也不是O(N)，而是O(log N)。此外，vector由连续的内存支持，而不是关联数组或链表。 - MSalters

不，问题并没有这么说。问题是：“我需要多次查找此向量中是否存在元素？”二分搜索是OP尝试的解决方案，确实二分搜索是O(logN)，但他可以使用哈希表以O(1)的时间复杂度完成，这也是我建议的选项之一。 - oleksii

Answer 3

然而，使用perf进行分析后，我发现在vector中查找元素是最慢的操作。这是你需要了解的一半信息，另一半是“与其他算法/容器相比有多快”。也许使用std::vector<>实际上是最快的，或者可能是最慢的。为了找到答案，您需要对几种不同的设计进行基准测试/分析。

例如，以下是使用随机整数在1000x9000大小的容器上进行的非常幼稚的基准测试（我会在map的较大尺寸上获得seg-faults，可能是32位内存的限制）。

如果您需要非唯一整数的计数：

- std::vector = 500毫秒 - std::map = 1700毫秒 - std::unordered_map = 3700毫秒

如果您只需要测试唯一整数的存在：

- std::vector = 15毫秒 - std::bitset<> = 50毫秒 - std::set = 350毫秒

请注意，我们对确切值不太感兴趣，而更关注容器之间的相对比较。 std::map<>相对较慢，这并不奇怪，因为涉及动态分配和数据的非局部性。 bitsets是迄今为止最快的，但如果需要非唯一整数的计数，则无法使用。我建议使用您确切的容器大小和内容进行类似的基准测试，这两者都可能影响基准测试结果。最终结果可能是std::vector<>仍然是最佳解决方案，但现在您有一些数据来支持该设计选择。

- uesp

Answer 4

如果您不需要以排序方式遍历集合，自c++11以来，您可以使用std::unordered_set<yourtype>，您只需要提供获取哈希和相等信息的集合方式即可。在这里，访问集合元素的时间为摊销O(1)，而不是排序向量的O(log(n))。

- W.F.

---

我对需求中的90,000 * 9000感到疑惑，这是否意味着向量被用作2D数组 - 如果是这种情况，元素的索引可能就是被找到的内容。 - marko

@marko 是的，在这种情况下，将unordered_map模板参数更改为例如std :: unordered_map <std :: pair <int，int>，sometype>可能是值得的。 - W.F.

我认为你不需要一个 map 而是一个 set - 因为它没有键/值分离。 - MSalters

使用 boost::multi_index 也许是一个不错的选择，可以同时使用 random_access_index 和 hashed_index 作为索引。你可以在索引类型之间获得 O(1) 的转换 - 因此在这种情况下，我们将使用 hash_index 在接近 O(1) 的时间内查找项目，并将其转换回数组索引（同样是 O(1)）。 - marko

如果他正在使用二分查找，则查找时间已经是O(log n)，因此map和set不会很快。如果有什么问题，由于内存较少，它将变慢。无序集应该更快。 - doron