为什么STL中的set_intersection这么慢？

Question

我在STL中使用set_intersection交叉一组100,000个数字和一组1,000个数字,并且花费21s,在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;
    }
}

Answer 1

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

首先,您在STL中的示例不太正确,因为有一件事情应该按升序排序(在STL中说"严格的弱排序").

其次,你使用在STL中作为树实现的"集合",而不是作为链表的"列表".随机插入集合比插入列表末尾更昂贵.

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

Answer 2

我在我的linux机器上运行了你的C++代码

$ time ./test

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

21s对我意味着你编译没有优化.如果您使用MSVC,请确保已在编译定义中列出 _SECURE_SCL=0(请参阅msdn).否则所有STL迭代器操作都是狗慢.