1

我在 STL 中使用 set_intersection 将一组 100,000 个数字和一组 1,000 个数字相交，它需要 21 秒，而在 C# 中需要 11 毫秒。

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;
    }
}
4

5 回答 5

8

有几件事可以使您的两个示例更具可比性。

首先，您在 STL 中的示例并不完全正确，一方面，两个集合都应该按升序排序（在 STL 中说“严格的弱排序”）。

其次，您使用在 STL 中实现为树的“集合”，而不是作为链表的“列表”。随机插入集合比插入列表末尾更昂贵。

尝试在 C++ 示例中使用整数列表并首先对列表进行排序（否则设置 inersection 将无法正常工作），我认为您会看到更有利的结果。

于 2009-06-29T17:07:48.010 回答
5

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

$ time ./test

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

21s 对我来说意味着你在没有优化的情况下编译。如果您使用 MSVC，请确保您已 在编译定义中列出_SECURE_SCL=0（参见msdn ）。否则，所有 STL 迭代器操作都非常缓慢。

于 2009-06-29T17:10:38.457 回答
2

runIntersectionTestAlgo在这个古老的 3GHz Pentium 4 上，我在禁用优化的调试版本中获得了 2734 毫秒的整个功能。我用 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 毫秒。

所以我的结论是你的基准有问题。

于 2009-06-29T18:21:14.643 回答
1

我更新了您的示例以使用我在单元测试时使用的一些计时器代码。在我的机器上，我得到以下时间（基于-O3）：

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

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

我无法在我的机器上运行你的 C# 示例，所以我无法比较时间，但绝对不是你发布的 21 秒。

于 2009-06-29T17:15:14.583 回答
0

您的 C# 和 C++ 代码的工作方式不同。C# 代码使用神奇的散列技巧来提高速度，您的 C++ 代码使用树技巧来提高速度。可能会加快速度的一件事（忽略您的测试似乎被破坏的事实）是使用散列，如下所示：

  1. 创建hash_map两个集合之一。
  2. 遍历第二个集合中的每个元素。如果 `hash_map1 包含该元素，请将其添加到您的结果中。
于 2009-06-29T18:48:38.407 回答