unordered_set vs 向量的迭代速度

Question

我有一个应用程序需要存储不同客户的各种子集。 容器中客户的顺序无关紧要。

由于顺序无关紧要，我希望与 std::vector<int> 相比，在 std::unordered_set<int> 上存储和迭代这组客户会更快。

CPPREference，然而，声明：

unordered_set containers are faster than set containers to access individual elements by their key, although they are generally less efficient for range iteration through a subset of their elements.

为了对此进行测试，我评估了遍历 std::unoredered_set 和 std::vector.

所需的时间

#include <vector>
#include <unordered_set>
#include <chrono>
#include <stdio.h>

static const int NoElements = 100000000;

int main()
{
    std::vector<int> VecofElems;
    VecofElems.reserve(NoElements);

    std::unordered_set<int> SetofElems;
    SetofElems.reserve(NoElements);

    for (int i = 0; i < NoElements; i++)
        VecofElems.push_back(i); 
    for (int i = 0; i < NoElements; i++)
        SetofElems.insert(i);

    auto VecIterStartTime = std::chrono::steady_clock::now();
    long vec_cumulative_sum = 0;
    for (std::vector<int>::const_iterator viter = VecofElems.begin(); viter != VecofElems.end(); ++viter)
        vec_cumulative_sum += *viter;
    auto VecIterEndTime = std::chrono::steady_clock::now();
    std::chrono::duration<double, std::milli> VecTime = VecIterEndTime - VecIterStartTime;
    
    auto SetIterStartTime = std::chrono::steady_clock::now();
    long set_cumulative_sum = 0;
    for (std::unordered_set<int>::const_iterator uositer = SetofElems.begin(); uositer != SetofElems.end(); ++uositer) {
        set_cumulative_sum += *uositer;
    }
    auto SetIterEndTime = std::chrono::steady_clock::now();
    std::chrono::duration<double, std::milli> SetTime = SetIterEndTime - SetIterStartTime;

    printf("Vector Sum %ld, Size %ld, Time Taken %f\n", vec_cumulative_sum, VecofElems.size(), VecTime);
    printf("Set Sum %ld, Size %ld, Time Taken %f\n", set_cumulative_sum, SetofElems.size(), SetTime);

    getchar();
}

我的机器上的输出，当上面在 MSVC 编译器的发布模式下编译时是：

Vector Sum 887459712, Size 100000000, Time Taken 51.340000
Set Sum 887459712, Size 100000000, Time Taken 4772.139100

表明迭代 vector 比 unordered_set.

快很多数量级

在我的应用程序中，由于容器中元素的顺序无关紧要，并且由于 std::vector 保留了顺序（在这种情况下没有必要），是否有任何其他容器可以比甚至更快std::vector 在遍历容器的各种元素？

Answer 1

std::vector 是您场景中线性迭代最快的 STL 容器。这仅仅是因为内存是连续分配的，因此可以从缓存机制中受益。矢量迭代器只是在内部递增一个指针。

如果可能，您可以尝试使用比 int 更小的类型来进一步提高性能。

在你的情况下，我认为 parallelization/SIMD 会最大程度地提高性能。这可以通过自动矢量化（检查项目编译器设置）来实现。

您也可以尝试 OMP 这样做（未测试）

size_t end = VecofElems.size();
#pragma omp parallel for shared(vec_cumulative_sum ) reduction(+: vec_cumulative_sum )
for (size_t i = 0; i < end; ++i) {
    vec_cumulative_sum += VecofElems[i];
}

这将运行多个线程并行。因此，将 vec_cumulative_sum 声明为在线程之间共享是很重要的。

std::for_each 提供了一些简单的方法来利用包括矢量化在内的并行性。这允许简单地使用像 std::vector 这样的任何 STL 容器（以及任何其他提供迭代器的容器），像这样

std::for_each(std::execution::par, VecofElems.begin(), VecofElems.end(), 
    , []() {
        // have some fun using a lambda, or function
    }
}

unordered_set vs 向量的迭代速度

Iteration speed of unordered_set vs vector

c++

stl

stdvector