为什么在 C++ 的数组中查找元素最有效？

Question

我需要一个快速的 STL 容器来查找其中是否存在元素，因此我测试了数组、向量、集合和无序集合。我认为集合针对查找元素进行了优化，因为值是唯一且有序的，但是 1000 万次迭代中最快的是：阵列（0.3 秒）矢量（1.7 秒）无序集（1.9 秒）集（3 秒）

代码如下：

#include <algorithm>
#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>

int main() {
    using std::cout, std::endl, std::set, std::unordered_set, std::vector, std::find;
    
    int i;
    
    const long ITERATIONS = 10000000;
    
    int a[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
    for (int i = 0; i < ITERATIONS; i++) {
        if (find(a, a + 16, rand() % 64) == a + 16) {}
        else {}
    }
    
    vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
    for (i = 0; i < ITERATIONS; i++) {
        if (find(v.begin(), v.end(), rand() % 64) == v.end()) {}
        else {}
    }
    
    set<int> s({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15});
    for (i = 0; i < ITERATIONS; i++) {
        if (find(s.begin(), s.end(), rand() % 64) == s.end()) {}
        else {}
    }
    
    unordered_set<int> us({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15});
    for (i = 0; i < ITERATIONS; i++) {
        if (find(us.begin(), us.end(), rand() % 64) == us.end()) {}
        else {}
    }
}

Answer 1

请记住C和C++中有as if rule！这意味着只要运行代码的可观察结果保持不变，编译器就可以通过任何方式（甚至通过删除代码）转换代码。

这是您的代码 godbolt。

现在请注意编译器为 if (find(a, a + 16, rand() % 64) == a + 16) {} 做了什么：

.L206:
        call    rand
        sub     ebx, 1
        jne     .L206

基本上编译器注意到它的结果没有被使用，并删除了所有期望调用 rand() 的东西，它有副作用（结果有明显变化）。

std::vector也是如此：

.L207:
        call    rand
        sub     ebx, 1
        jne     .L207

甚至对于 std::set 和 std::unordered_set 编译器也能够执行相同的优化。您看到的差异（您没有指定您是如何做到的）只是初始化所有这些变量的结果，这对于更复杂的容器来说是耗时的。

编写良好的性能测试很难，应谨慎对待。

你的问题还有第二个问题。给定代码的时间复杂度。搜索数组和搜索 std::set 和 std::unrodered_set 对数据大小的缩放比例不同。对于小数据集，简单的数组将成为命运，因为它的简单实现和对内存的最佳访问。随着数据大小的增长，数组 std::find 的时间复杂度将增长为 O(n) 另一方面，较慢的 std::set 查找项目的时间将增长为 O(log n) 而对于 std::unordered_set这将是常数时间O(1)。因此，对于少量数据数组将是最快的，对于中等大小 std::set 是赢家，如果数据量很大 std::unordered_set 将是最好的。

查看使用 google 基准的 this benchmark example。

Answer 2

你不是在衡量效率，而是在衡量绩效。而且做得很糟糕。

地址 space 随机化或只是不同的用户名或 env 中的其他变量对速度的影响高达约 40%。这不仅仅是 -O0 和 -O2 之间的差异。您只测量了一个单一地址 space 布局的单一系统 10000000 次。这使得 about 的值变得毫无意义。

但您仍然设法弄清楚，对于 16 个整数，任何比仅仅查看所有整数更好的尝试都会表现得更差。在单个缓存行中进行简单的线性搜索（如果布局不好，更有可能是两个）就是最好的方法。

现在再试 10000000 个整数和运行二进制 1000 次。如果您使用布局随机化器从时序中真正排除布局事故，那就更好了。

注意：Iirc 的排序限制在 32 到 64 个整数之间是最好的冒泡排序数组，查找更简单。

为什么在 C++ 的数组中查找元素最有效？

Why are finding elements most efficient in arrays in c++?

c++

set

find