为什么在C＆＃x2B;＆＃x2B;中找到最有效的元素？

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 ++中有就像规则！
这意味着，只要运行代码的可观察结果保持不变，编译器就可以通过任何方式（即使是删除代码）来转换代码。

这是 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 ::的时间复杂性::查找数组的将以o（n）在查找项目将以o（log n）和std :: unordered_set为o（log n） 它将是恒定的时间o（1）。因此，对于少量数据阵列将是最快的，对于中等大小std :: Set是赢家，如果数据数量将是大的std :: Unordered_set最好是最好的。

看看此基准示例示例使用Google-Benchmark。

Answer 2

您不是在衡量效率，而是在衡量性能。而且这样做很糟糕。

env> env中的地址空间随机化或仅不同的用户名或其他变量的效果对速度的影响约为40％。这不仅仅是-O0和-O2之间的差异。您只能测量一个单个系统，其中一个单个地址空间布局10000000次。这使得无意义的价值。

但是，您仍然设法弄清楚16 int的任何尝试都比仅仅看待所有尝试都会表现更糟糕的尝试。在单个缓存线路中进行简单的线性搜索（如果布局不良，更有可能的话，则只是两个）只是最好的方法。

现在，使用10000000 INT重试，运行二进制1000次。如果您使用布局随机器将布局的事故排除在时间安排之外，更好。

注意：iirc的排序极限，其中有气泡排序的数组最好在32到64个int之间，并且发现更简单。