لماذا set_intersection في المحكمة الخاصة بلبنان بطيئة جدا ؟

Question

أنا المتقاطعة مجموعة من 100 ، 000 أرقام مجموعة من 1,000 الأرقام باستخدام set_intersection في المحكمة و أخذ 21s ، حيث يأخذ 11ms في C#.

C++ Code:

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

في هذا القديم 3GHZ بنتيوم 4، وأحصل على 2734 ميلي ثانية من أجل وظيفة runIntersectionTestAlgo بأكملها، في بناء تصحيح مع تحسينات تعطيل. أنا جمعت مع SP1 VS2008.

إذا أنا تمكين أمثل، وأحصل على 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 ميلي ثانية.

وهكذا أخلص إلى أن هناك شيء خاطئ مع المعايير الخاصة بك.

Answer 2

وبضعة أشياء من شأنها أن تجعل الخاصة بك مثالين أكثر قابلية للمقارنة.

أولا، مثالك في STL ليس صحيحا تماما، لشيء واحد يجب أن يتم فرز كلتا المجموعتين في ترتيب تصاعدي (في STL يتكلم "ترتيب ضعف الصارم").

والثانية، باستخدام "مجموعات" التي تنفذ كما الأشجار في المحكمة الخاصة بلبنان، في مقابل "القوائم" التي هي القوائم المرتبطة. إدراج عشوائية إلى مجموعة هي أكثر تكلفة من إدخال إلى نهاية القائمة.

وحاول استخدام قائمة [إينتس] في المثال C ++ وكذلك فرز القائمة أولا (لن تعيين على خلاف ذلك inersection لا تعمل بشكل صحيح) وأعتقد أنك سترى نتائج أكثر إيجابية.

Answer 3

وركضت التعليمات البرمجية C ++ على مربع لينكس بلدي

$ time ./test

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

و21S تعني لي كنت جمعت دون أمثل. في حال كنت تستخدم MSVC تأكد ذكرتموها  _SECURE_SCL=0 (انظر MSDN ) في تعريفات الترجمة . على خلاف جميع عمليات STL مكرر هي الكلاب إلى بطء.

Answer 4

ولقد قمت بتحديث سبيل المثال لاستخدام بعض الرموز الموقت التي تستخدم عند اختبار وحدة. على الجهاز الخاص بي أحصل على توقيت التالية (على أساس -O3):

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

وبناء على ذلك، إذا أنا أقرأ العشرية بلدي بشكل صحيح، فإنه يأخذ "4ms" لادخال العناصر في المجموعة الأولى، 50 ميكروثانية لادخال العناصر في المجموعة الثانية و03/01 من مللي ثانية لأداء التقاطع.

وأنا غير قادر على تشغيل الخاص بك C # المثال على الجهاز الخاص بي، لذلك لا يمكن المقارنة بين توقيت، لكنها بالتأكيد ليست 21S كما نشر.

Answer 5

C# و C++ البرمجية تعمل بشكل مختلف.C# كود يستخدم السحرية تجزئة الحيل السرعة ، C++ يستخدم رمز شجرة الحيل السرعة.الشيء الوحيد الذي ربما تسريع الأمور (تجاهل حقيقة أن الاختبار الخاص بك يبدو أن كسر) سيكون باستخدام التجزئة على النحو التالي:

1. إنشاء hash_map واحد من اثنين من المجموعات.
2. تكرار عبر كل عنصر في 2 المجموعة.إذا كان `hash_map1 يحتوي على هذا العنصر ، إضافة إلى النتائج الخاصة بك.