c++ - std::map 和性能，相交集

Question

我正在对一些数字集进行求交，并通过存储我每次在 map 中看到数字时的计数来执行此操作。

我发现性能非常慢。

详细信息:- 其中一套有 150,000 个号码- 该组和另一组的交集第一次大约需要 300 毫秒，第二次大约需要 5000 毫秒- 我还没有做任何分析，但每次我在 malloc.c 中进行交集时破坏调试器!

那么，我怎样才能提高这个性能呢？切换到不同的数据结构？一些如何提高map的内存分配性能？

更新:

1. 有什么方法可以询问 std::map 或boost::unordered_map 预分配一些空间？
2. 或者，是否有任何有效使用它们的技巧？

更新2:

参见 Fast C++ container like the C# HashSet<T> and Dictionary<K,V>?

更新3:

我对 set_intersection 进行了基准测试并得到了可怕的结果:

(set_intersection) Found 313 values in the intersection, in 11345ms
(set_intersection) Found 309 values in the intersection, in 12332ms

代码:

int runIntersectionTestAlgo()
{   

    set<int> set1;
    set<int> set2;
    set<int> intersection;


    // Create 100,000 values for set1
    for ( int i = 0; i < 100000; i++ )
    {
        int value = 1000000000 + i;
        set1.insert(value);
    }

    // Create 1,000 values for set2
    for ( int i = 0; i < 1000; i++ )
    {
        int random = rand() % 200000 + 1;
        random *= 10;

        int value = 1000000000 + random;
        set2.insert(value);
    }

    set_intersection(set1.begin(),set1.end(), set2.begin(), set2.end(), inserter(intersection, intersection.end()));

    return intersection.size(); 
}

Answer 1

您绝对应该使用速度更快的预分配 vector 。与 STL 集合进行集合交集的问题在于，每次移动到下一个元素时，您都会追逐一个动态分配的指针，而该指针很容易不在您的 CPU 缓存中。对于 vector ，下一个元素通常会在您的缓存中，因为它在物理上靠近前一个元素。

vector 的技巧在于，如果您不为这样的任务预分配内存，它的性能会更差，因为它会在初始化步骤中调整自身大小时继续重新分配内存。

试试这样的 instaed - 它会更快。

int runIntersectionTestAlgo() { 

vector<char> vector1; vector1.reserve(100000);
vector<char> vector2; vector2.reserve(1000);

// Create 100,000 values for set1
for ( int i = 0; i < 100000; i++ )    {
    int value = 1000000000 + i;
    set1.push_back(value);
}

sort(vector1.begin(), vector1.end());

// Create 1,000 values for set2
for ( int i = 0; i < 1000; i++ )    {
    int random = rand() % 200000 + 1;
    random *= 10;
    int value = 1000000000 + random;
    set2.push_back(value);
}

sort(vector2.begin(), vector2.end());

// Reserve at most 1,000 spots for the intersection
vector<char> intersection; intersection.reserve(min(vector1.size(),vector2.size()));
set_intersection(vector1.begin(), vector1.end(),vector2.begin(), vector2.end(),back_inserter(intersection));

return intersection.size(); 
}