代码之家 › 专栏 › 技术社区 › waterlooalex

为什么在STL中设置交叉点的速度这么慢?

intersection stl performance c++ c#

waterlooalex · 技术社区 · 15 年前

我用STL中的set_交集和它的21s来交叉一组100000个数字和一组1000个数字,其中c_需要11ms。

C++代码:

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(); 
}

C代码:

static int runIntersectionTest()
    {
        Random random = new Random(DateTime.Now.Millisecond);

        Dictionary<int,int> theMap = new Dictionary<int,int>();

        List<int> set1 = new List<int>();
        List<int> set2 = new List<int>();

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

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

            // Now intersect the two sets by populating the map
        foreach( int value in set1 )
            {
                theMap[value] = 1;
            }

            int intersectionSize = 0;

        foreach ( int value in set2 )
        {
            int count;
            if ( theMap.TryGetValue(value, out count ) )
            {
                intersectionSize++;
                theMap[value] = 2;
            }
            }

            return intersectionSize;
    }
}

5 回复 | 直到 15 年前

Stack Overflow is garbage 15 年前

在这个古老的3GHz奔腾4上,我得到了2734毫秒的时间 runIntersectionTestAlgo 函数,在禁用优化的调试生成中。我用VS2008 SP1编译。

如果启用优化,我将得到93毫秒。

以下是我的代码:

#include <set>
#include <algorithm>

using namespace std;

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(); 
}

#include <windows.h>
#include <iostream>

int main(){
    DWORD start = GetTickCount();

    runIntersectionTestAlgo();

    DWORD span = GetTickCount() - start;

    std::cout << span << " milliseconds\n";
}

停用 _SECURE_SCL 对仍然徘徊在100毫秒左右的发布版本没有任何影响。

GetTickCount 当然,这并不理想,但它应该足够好地区分21秒和不足100毫秒。

所以我得出结论,你的基准有问题。

Chris Harris 15 年前

一些事情会使你的两个例子更具可比性。

首先,您在STL中的示例并不完全正确,因为一件事是两个集合都应该按升序排序(在STL中,称为“严格弱排序”)。

第二,您使用的“集合”在STL中实现为树,而“列表”则是链接列表。随机插入到一个集合比插入到列表的末尾要贵。

尝试使用C++示例中的int列表,并首先对列表进行排序(否则设置惯性段将无法正常工作),我认为您会看到更有利的结果。

Brian 15 年前

我在我的Linux盒子上运行你的C++代码

$ time ./test

real    0m0.073s
user    0m0.060s
sys     0m0.003s

21对我来说意味着你编译时没有进行优化。如果使用MSVC,请确保已列出 _SECURE_SCL=0 (见 msdn )在编译定义中。否则,所有STL迭代器操作都是缓慢的。

Richard Corden 15 年前

我更新了您的示例以使用单元测试时使用的一些计时器代码。在我的机器上,我得到以下计时(基于-o3):

First loop 0.0040654
Second loop 4.8e-05
Intersection 0.000349
Intersection size: 50

基于此,如果我正确地读取了小数,将项目插入第一组需要“4ms”,将项目插入第二组需要50微秒,执行交叉需要1/3毫秒。

我无法在我的机器上运行您的C示例,因此我无法比较时间,但绝对不是您发布的21秒。

Brian 15 年前

你的C和C++代码的工作方式不同。C代码使用神奇的散列技巧来加快速度,C++代码使用树技巧来加快速度。有一件事可能会加快速度(忽略测试似乎被破坏的事实),那就是使用散列,如下所示:

创建一个 hash_map 两个收藏中的一个。
迭代第二个集合中的每个元素。如果“hash”map1包含该元素,请将其添加到结果中。