为什么在 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++那里有好像规则！这意味着编译器可以通过任何方式转换代码（甚至通过删除代码），只要运行代码的可观察结果保持不变。

这是你的代码的上帝螺栓。

现在注意编译器做了什么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将是最好的。

看看这个使用谷歌基准测试的基准示例。