1

STL で set_intersection を使用して 100,000 個の数字のセットと 1,000 個の数字のセットを交差させています。C# では 11ms かかりますが、21 秒かかります。

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

いくつかのことがあなたの2つの例をより比較可能にするでしょう.

まず、STL での例は正しくありません。1 つのことは、両方のセットを昇順で並べ替える必要があるためです (STL では、「厳密な弱い順序付け」と呼ばれます)。

次に、STL でツリーとして実装される「セット」と、リンクされたリストである「リスト」を使用します。セットへのランダムな挿入は、リストの最後に挿入するよりもコストがかかります。

C++ の例で int のリストを使用し、最初にリストをソートしてみてください (そうしないと、set inersection が適切に機能しません)、より好ましい結果が得られると思います。

于 2009-06-29T17:07:48.010 に答える
5

Linux ボックスで C++ コードを実行しました

$ time ./test

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

21s は、最適化なしでコンパイルしたことを意味します。MSVC を使用する場合 は、コンパイル定義にリストされていることを確認してください ( msdn_SECURE_SCL=0を参照)。そうしないと、すべての STL イテレータ操作が非常に遅くなります。

于 2009-06-29T17:10:38.457 に答える
2

この古い3GHzPentium4runIntersectionTestAlgoでは、最適化を無効にしたデバッグビルドで、関数全体で2734ミリ秒を取得します。VS2008SP1でコンパイルしました。

最適化を有効にすると、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

それに基づいて、小数を正しく読んでいる場合、アイテムを最初のセットに挿入するのに「4ミリ秒」かかり、アイテムを2番目のセットに挿入するのに50マイクロ秒かかり、交差を実行するのに1/3ミリ秒かかります。

あなたの C# の例を自分のマシンで実行できないため、タイミングを比較することはできませんが、あなたが投稿した 21 秒ではありません。

于 2009-06-29T17:15:14.583 に答える
0

C# と C++ のコードの動作は異なります。C# コードは高速化のために魔法のハッシュ トリックを使用し、C++ コードは高速化のためにツリー トリックを使用します。おそらく物事をスピードアップする1つのこと（テストが壊れているように見えるという事実を無視して）は、次のようにハッシュを使用することです。

  1. hash_map2 つのコレクションのいずれかを作成します。
  2. 2 番目のコレクションの各要素を反復処理します。`hash_map1 にその要素が含まれている場合は、それを結果に追加します。
于 2009-06-29T18:48:38.407 に答える