在什么情况下，std::map<A,B> 比排序的 std::vector<std::pair<A,B>> 更快？

Question

我在一些代码中使用了map来存储有序数据。我发现对于巨大的map，销毁可能需要一段时间。在这段代码中，我将map替换为vector<pair>，降低了处理时间10000倍...

最后，我很惊讶，决定比较map和排序后的vector或pair的性能。

我很惊讶，因为我找不到map比随机填充并稍后排序的排序vector更快的情况...必须存在某些情况下map更快...否则提供此类有何意义？

以下是我的测试：

第一项测试，比较map填充和销毁与vector填充、排序（因为我需要一个排序容器）和销毁：

#include <iostream>
#include <time.h>
#include <cstdlib>
#include <map>
#include <vector>
#include <algorithm>

int main(void)
{

    clock_t tStart = clock();

    {
        std::map<float,int> myMap;
        for ( int i = 0; i != 10000000; ++i )
        {
            myMap[ ((float)std::rand()) / RAND_MAX ] = i;
        }
    }

    std::cout << "Time taken by map: " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl;

    tStart = clock();

    {
        std::vector< std::pair<float,int> > myVect;
        for ( int i = 0; i != 10000000; ++i )
        {
            myVect.push_back( std::make_pair( ((float)std::rand()) / RAND_MAX, i ) );
        }

        // sort the vector, as we want a sorted container:
        std::sort( myVect.begin(), myVect.end() );
    }

    std::cout << "Time taken by vect: " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl;

    return 0;
}

使用g++ main.cpp -O3 -o main编译，得到以下结果：

Time taken by map: 21.7142
Time taken by vect: 7.94725

map比vector慢3倍...

然后我说："好的，用vector填充和排序更快，但用map进行搜索会更快"....所以我进行了测试：

#include <iostream>
#include <time.h>
#include <cstdlib>
#include <map>
#include <vector>
#include <algorithm>

int main(void)
{
    clock_t tStart = clock();

    {
        std::map<float,int> myMap;
        float middle = 0;
        float last;
        for ( int i = 0; i != 10000000; ++i )
        {
            last = ((float)std::rand()) / RAND_MAX;
            myMap[ last ] = i;
            if ( i == 5000000 )
                middle = last; // element we will later search
        }

        std::cout << "Map created after " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl;

        float sum = 0;
        for ( int i = 0; i != 10; ++i )
            sum += myMap[ last ]; // search it

        std::cout << "Sum is " << sum << std::endl;
    }

    std::cout << "Time taken by map: " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl;

    tStart = clock();

    {
        std::vector< std::pair<float,int> > myVect;
        std::pair<float,int> middle;
        std::pair<float,int> last;
        for ( int i = 0; i != 10000000; ++i )
        {
            last = std::make_pair( ((float)std::rand()) / RAND_MAX, i );
            myVect.push_back( last );
            if ( i == 5000000 )
                middle = last; // element we will later search
        }

        std::sort( myVect.begin(), myVect.end() );

        std::cout << "Vector created after " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl;

        float sum = 0;
        for ( int i = 0; i != 10; ++i )
            sum += (std::find( myVect.begin(), myVect.end(), last ))->second; // search it

        std::cout << "Sum is " << sum << std::endl;
    }

    std::cout << "Time taken by vect: " << ((double)(clock() - tStart)/CLOCKS_PER_SEC) << std::endl;

    return 0;
}

使用g++ main.cpp -O3 -o main进行编译，得到以下结果：

Map created after 19.5357
Sum is 1e+08
Time taken by map: 21.41
Vector created after 7.96388
Sum is 1e+08
Time taken by vect: 8.31741

即使是搜索，使用vector显然也更快（使用map进行10次搜索几乎需要2秒，而使用vector仅需半秒钟）...

所以：

• 我有遗漏吗？
• 我的测试不正确/准确吗？
• map只是一个要避免的类吗，还是真的存在map可以提供良好性能的情况？

- jpo38

---

在需要保持操作顺序的已有容器中插入大量元素（例如插入之间存在查找操作）。请尝试将10k个随机值插入Map和排序向量。 - Revolver_Ocelot

你几乎没有测试任何东西（例如：删除元素怎么办？）。但是，是的，一般基于节点的数据结构非常不友好缓存。 - Karoly Horvath

@Revolver_Ocelot：谢谢，那正是我的意思，我错过了那个点。做了一个测试（见下面的答案），是的，map最终变得更快了。 - jpo38

你可能还想考虑使用unordered_map，请参阅这篇Scott Meyers的博客文章。 - zdan

10次地图搜索花费了近2秒钟，你不觉得这很可疑吗？那个数字不可能是真的，因为它太慢了，慢了大约10000倍。 - usr

Answer 1

通常情况下，当您在查找中插入和删除大量数据时，map可能更好。如果只构建一次数据结构，然后仅执行查找操作，则排序的vector几乎肯定更快，即使只是因为处理器缓存效应。由于向量中任意位置的插入和删除的时间复杂度为O(n)，而不是O(log n)，所以会有一个点，这些操作将成为限制因素。

- Mark Ransom

---

不确定。两种算法的时间复杂度和缓存未命中次数都是对数级别的，可能大致相等。 - usr

@usr 向量中的所有数据都存储在连续的地址中；如果数据小于缓存行，则最后几次迭代将从中受益，而后续迭代不太可能将其推出缓存以供下一次使用。 - Mark Ransom

@MarkRansom：感谢您的澄清。在我的情况下，容器将经常插入新元素，但始终会插入到容器的末尾（我的键实际上是对象的时间戳）。因此，即使在这种情况下，“vector”在插入时仍然比“map”快得多。最后，我将使用二分查找而不是查找来优化搜索（如此处所提出的：https://dev59.com/cnRB5IYBdhLWcg3w-8Ho）。 - jpo38

@jpo38 我没意识到你之前没有使用二分查找，因为你明确表示正在使用已排序的向量...我很惊讶find更快！ - Mark Ransom

@MarkRansom：随着搜索次数的增加，速度会变慢......我把这个问题发布为答案，但因为被踩而将其删除了.... :-( - jpo38

Answer 2

std::find 的时间复杂度是线性的，而 map 的搜索复杂度是对数级别的。

当你发现一个算法比另一个快 100000 倍时，你应该开始怀疑了！你的基准测试无效。

你需要比较真实的变体。可能，你想比较 map 和二分查找。运行每个变体至少 1 秒钟的 CPU 时间，这样你就可以真实地比较结果。

当基准测试返回“0.00001 秒”的时间时，你已经处于时钟不准确的噪声范围内。这个数字毫无意义。

- usr