سريع تقاطع مجموعات:C++ vs C#

Question

على آلة (رباعية النواة, 8gb ram), تشغيل Vista x64 الأعمال ، مع Visual Studio 2008 SP1, أنا أحاول أن تتقاطع مجموعتين من الأرقام بسرعة جدا.

لقد نفذت نهجين في C++, واحد في C#.C# النهج هو أسرع حتى الآن, أود أن تحسين C++ النهج حتى أسرع من C#, والتي أتوقع C++ يمكن القيام به.

هنا هو C# output:(بناء الإصدار)

Found the intersection 1000 times, in 4741.407 ms

هنا هو الأولي C++ الانتاج ، نهجين مختلفين (الإصدار x64 بناء):

Found the intersection (using unordered_map) 1000 times, in 21580.7ms
Found the intersection (using set_intersection) 1000 times, in 22366.6ms

هنا هو أحدث C++ الانتاج لمدة ثلاثة مناهج (الإصدار x64 بناء):

أحدث المعيار:

Found the intersection of 504 values (using unordered_map) 1000 times, in 28827.6ms
Found the intersection of 495 values (using set_intersection) 1000 times, in 9817.69ms
Found the intersection of 504 values (using unordered_set) 1000 times, in 24769.1ms

لذا set_intersection النهج هو الآن تقريبا 2x أبطأ من C#, ولكن 2x أسرع من الأولي C++ النهج.

أحدث C++ code:

Code:

// MapPerformance.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <hash_map>
#include <vector>
#include <iostream>
#include <time.h>
#include <algorithm>
#include <set>
#include <unordered_set>

#include <boost\unordered\unordered_map.hpp>

#include "timer.h"

using namespace std;
using namespace stdext;
using namespace boost;
using namespace tr1;


int runIntersectionTest2(const vector<int>& set1, const vector<int>& set2)
{
    // hash_map<int,int> theMap;
    // map<int,int> theMap;
    unordered_set<int> theSet;      

     theSet.insert( set1.begin(), set1.end() );

    int intersectionSize = 0;

    vector<int>::const_iterator set2_end = set2.end();

    for ( vector<int>::const_iterator iterator = set2.begin(); iterator != set2_end; ++iterator )
    {
        if ( theSet.find(*iterator) != theSet.end() )
        {
                intersectionSize++;
        }
    }

    return intersectionSize;
}

int runIntersectionTest(const vector<int>& set1, const vector<int>& set2)
{
    // hash_map<int,int> theMap;
    // map<int,int> theMap;
    unordered_map<int,int> theMap;  

    vector<int>::const_iterator set1_end = set1.end();

    // Now intersect the two sets by populating the map
    for ( vector<int>::const_iterator iterator = set1.begin(); iterator != set1_end; ++iterator )
    {
        int value = *iterator;

        theMap[value] = 1;
    }

    int intersectionSize = 0;

    vector<int>::const_iterator set2_end = set2.end();

    for ( vector<int>::const_iterator iterator = set2.begin(); iterator != set2_end; ++iterator )
    {
        int value = *iterator;

        unordered_map<int,int>::iterator foundValue = theMap.find(value);

        if ( foundValue != theMap.end() )
        {
            theMap[value] = 2;

            intersectionSize++;
        }
    }

    return intersectionSize;

}

int runSetIntersection(const vector<int>& set1_unsorted, const vector<int>& set2_unsorted)
{   
    // Create two vectors
    std::vector<int> set1(set1_unsorted.size());
    std::vector<int> set2(set2_unsorted.size());

    // Copy the unsorted data into them
    std::copy(set1_unsorted.begin(), set1_unsorted.end(), set1.begin());
    std::copy(set2_unsorted.begin(), set2_unsorted.end(), set2.begin());

    // Sort the data
    sort(set1.begin(),set1.end());
    sort(set2.begin(),set2.end());

    vector<int> intersection;
    intersection.reserve(1000);

    set_intersection(set1.begin(),set1.end(), set2.begin(), set2.end(), back_inserter(intersection));

    return intersection.size(); 
}

void createSets( vector<int>& set1, vector<int>& set2 )
{
    srand ( time(NULL) );

    set1.reserve(100000);
    set2.reserve(1000);

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

    // Try to get half of our values intersecting
    float ratio = 200000.0f / RAND_MAX;


    // Create 1,000 values for set2
    for ( int i = 0; i < 1000; i++ )
    {
        int random = rand() * ratio + 1;

        int value = 1000000000 + random;
        set2.push_back(value);
    }

    // Make sure set1 is in random order (not sorted)
    random_shuffle(set1.begin(),set1.end());
}

int _tmain(int argc, _TCHAR* argv[])
{
    int intersectionSize = 0;

    vector<int> set1, set2; 
    createSets( set1, set2 );

    Timer timer;
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runIntersectionTest(set1, set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using unordered_map) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    timer.Reset();
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runSetIntersection(set1,set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using set_intersection) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    timer.Reset();
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runIntersectionTest2(set1,set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using unordered_set) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    getchar();

    return 0;
}

C# كود:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DictionaryPerformance
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> set1 = new List<int>(100000);
            List<int> set2 = new List<int>(1000);

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

            Random random = new Random(DateTime.Now.Millisecond);

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

            long start = System.Diagnostics.Stopwatch.GetTimestamp();
            for (int i = 0; i < 1000; i++)
            {
                runIntersectionTest(set1,set2);
            }
            long duration = System.Diagnostics.Stopwatch.GetTimestamp() - start;

            Console.WriteLine(String.Format("Found the intersection 1000 times, in {0} ms", ((float) duration * 1000.0f) / System.Diagnostics.Stopwatch.Frequency));

            Console.ReadKey();
        }

        static int runIntersectionTest(List<int> set1, List<int> set2)
        {

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

            // 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 ) )
                {
                    theMap[value] = 2;
                    intersectionSize++;
                }
            }

            return intersectionSize;
        }
    }
}

C++ code:

// MapPerformance.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <hash_map>
#include <vector>
#include <iostream>
#include <time.h>
#include <algorithm>
#include <set>

#include <boost\unordered\unordered_map.hpp>

#include "timer.h"

using namespace std;
using namespace stdext;
using namespace boost;

int runIntersectionTest(vector<int> set1, vector<int> set2)
{
    // hash_map<int,int> theMap;
    // map<int,int> theMap;
    unordered_map<int,int> theMap;

    // Now intersect the two sets by populating the map
    for ( vector<int>::iterator iterator = set1.begin(); iterator != set1.end(); iterator++ )
    {
        int value = *iterator;

        theMap[value] = 1;
    }

    int intersectionSize = 0;

    for ( vector<int>::iterator iterator = set2.begin(); iterator != set2.end(); iterator++ )
    {
        int value = *iterator;

        unordered_map<int,int>::iterator foundValue = theMap.find(value);

        if ( foundValue != theMap.end() )
        {
            theMap[value] = 2;

            intersectionSize++;
        }
    }

    return intersectionSize;

}

int runSetIntersection(set<int> set1, set<int> set2)
{   
    set<int> intersection;

    set_intersection(set1.begin(),set1.end(), set2.begin(), set2.end(), inserter(intersection, intersection.end()));

    return intersection.size(); 
}



int _tmain(int argc, _TCHAR* argv[])
{
    srand ( time(NULL) );

    vector<int> set1;
    vector<int> set2;

    set1.reserve(10000);
    set2.reserve(1000);

    // Create 100,000 values for set1
    for ( int i = 0; i < 100000; i++ )
    {
        int value = 1000000000 + i;
        set1.push_back(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.push_back(value);
    }


    Timer timer;
    for ( int i = 0; i < 1000; i++ )
    {
        runIntersectionTest(set1, set2);
    }
    timer.Stop();

    cout << "Found the intersection (using unordered_map) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    set<int> set21;
    set<int> set22;

    // Create 100,000 values for set1
    for ( int i = 0; i < 100000; i++ )
    {
        int value = 1000000000 + i;
        set21.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;
        set22.insert(value);
    }

    timer.Reset();
    for ( int i = 0; i < 1000; i++ )
    {
        runSetIntersection(set21,set22);
    }
    timer.Stop();

    cout << "Found the intersection (using set_intersection) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    getchar();

    return 0;
}

---

حسنا هنا هو أحدث, مع بعض التغييرات:

• C++ مجموعات يتم الآن الإعداد بشكل صحيح بحيث يكون 50% تقاطع (مثل C#)
• Set1 وتعديلا حتى لا فرزها set2 كان بالفعل غير مصنفة
• على set_intersection التنفيذ الآن يستخدم ناقلات ، وفرزها الأولى

C++ (الإفراج x64) النتائج:

Found the intersection of 503 values (using unordered_map) 1000 times, in 35131.1ms
Found the intersection of 494 values (using set_intersection) 1000 times, in 10317ms

لذلك 2x أبطأ من C#.@Jalf:كنت الحصول على بعض بسرعة الأرقام, هل هناك شيء أفعله خطأ هنا ؟

C++ Code:

// MapPerformance.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <hash_map>
#include <vector>
#include <iostream>
#include <time.h>
#include <algorithm>
#include <set>

#include <boost\unordered\unordered_map.hpp>

#include "timer.h"

using namespace std;
using namespace stdext;
using namespace boost;

int runIntersectionTest(const vector<int>& set1, const vector<int>& set2)
{
    // hash_map<int,int> theMap;
    // map<int,int> theMap;
    unordered_map<int,int> theMap;  

    vector<int>::const_iterator set1_end = set1.end();

    // Now intersect the two sets by populating the map
    for ( vector<int>::const_iterator iterator = set1.begin(); iterator != set1_end; ++iterator )
    {
        int value = *iterator;

        theMap[value] = 1;
    }

    int intersectionSize = 0;

    vector<int>::const_iterator set2_end = set2.end();

    for ( vector<int>::const_iterator iterator = set2.begin(); iterator != set2_end; ++iterator )
    {
        int value = *iterator;

        unordered_map<int,int>::iterator foundValue = theMap.find(value);

        if ( foundValue != theMap.end() )
        {
            theMap[value] = 2;

            intersectionSize++;
        }
    }

    return intersectionSize;

}

int runSetIntersection(const vector<int> set1_unsorted, const vector<int> set2_unsorted)
{   
    // Create two vectors
    std::vector<int> set1(set1_unsorted.size());
    std::vector<int> set2(set2_unsorted.size());

    // Copy the unsorted data into them
    std::copy(set1_unsorted.begin(), set1_unsorted.end(), set1.begin());
    std::copy(set2_unsorted.begin(), set2_unsorted.end(), set2.begin());

    // Sort the data
    sort(set1.begin(),set1.end());
    sort(set2.begin(),set2.end());

    vector<int> intersection;
    intersection.reserve(1000);

    set_intersection(set1.begin(),set1.end(), set2.begin(), set2.end(), inserter(intersection, intersection.end()));

    return intersection.size(); 
}

void createSets( vector<int>& set1, vector<int>& set2 )
{
    srand ( time(NULL) );

    set1.reserve(100000);
    set2.reserve(1000);

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

    // Try to get half of our values intersecting
    float ratio = 200000.0f / RAND_MAX;


    // Create 1,000 values for set2
    for ( int i = 0; i < 1000; i++ )
    {
        int random = rand() * ratio + 1;

        int value = 1000000000 + random;
        set2.push_back(value);
    }

    // Make sure set1 is in random order (not sorted)
    random_shuffle(set1.begin(),set1.end());
}

int _tmain(int argc, _TCHAR* argv[])
{
    int intersectionSize = 0;

    vector<int> set1, set2; 
    createSets( set1, set2 );

    Timer timer;
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runIntersectionTest(set1, set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using unordered_map) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    timer.Reset();
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runSetIntersection(set1,set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using set_intersection) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    getchar();

    return 0;
}

Answer 1

هناك العديد من المشاكل في الاختبار الخاص بك.

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

ثانيًا، يجب عليك إجراء الاختبار عددًا كبيرًا من المرات لأخذ تأثيرات التخزين المؤقت المحتملة والشكوك الأخرى في الاعتبار.(ومن المحتمل أن يتم إنتاج وقت إجمالي واحد، على سبيل المثال، 1000 مرة، بدلاً من وقت فردي لكل منها.وبهذه الطريقة يمكنك تقليل عدم اليقين من المؤقت الذي قد يكون ذو دقة محدودة والإبلاغ عن نتائج غير دقيقة عند استخدامه في نطاق 0-20 مللي ثانية.

علاوة على ذلك، بقدر ما أستطيع قراءته من المستندات، يجب فرز المدخلات إلى set_intersection، ولن يتم فرز set2.ويبدو أنه لا يوجد سبب للاستخدام unordered_map, ، متى unordered_set سيكون أفضل بكثير لما تفعله.

حول رمز الإعداد المطلوب، لاحظ أنك على الأرجح لا تحتاج إلى ملء المتجهات لتشغيل التقاطع.كل من التنفيذ الخاص بك و set_intersection العمل على التكرارات بالفعل، لذا يمكنك ببساطة تمرير زوج من التكرارات إلى هياكل البيانات الموجودة بالفعل في مدخلاتك.

بعض التعليقات المحددة على الكود الخاص بك:

• يستخدم ++iterator بدلاً من iterator++
• بدلًا من استدعاء الدالة Vector.end()‎ عند كل تكرار للحلقة، قم باستدعاءها مرة واحدة وتخزين النتيجة مؤقتًا
• تجربة استخدام المتجهات المصنفة مقابل std::set vs unordered_set (لا unordered_map)

يحرر:

لم أجرب إصدار C# الخاص بك، لذلك لا أستطيع مقارنة الأرقام بشكل صحيح، ولكن هذا هو الاختبار المعدل.يتم تشغيل كل منها 1000 مرة، على معالج Core 2 Quad بسرعة 2.5 جيجا هرتز وذاكرة الوصول العشوائي (RAM) سعة 4 جيجابايت:

std::set_intersection on std::set: 2606ms
std::set_intersection on tr1::unordered_set: 1014ms
std::set_intersection on sorted vectors: 171ms
std::set_intersection on unsorted vectors: 10140ms

الخيار الأخير غير عادل بعض الشيء، لأنه يجب عليه نسخ المتجهات وفرزها.من الناحية المثالية، يجب أن يكون هذا النوع فقط جزءًا من المعيار.لقد حاولت إنشاء إصدار يستخدم مصفوفة مكونة من 1000 متجه غير مصنف (لذلك لن أضطر إلى نسخ البيانات غير المصنفة في كل تكرار)، ولكن الأداء كان هو نفسه تقريبًا، أو أسوأ قليلاً، لأن هذا قد يتسبب في حدوث أخطاء ثابتة في ذاكرة التخزين المؤقت ، لذلك عدت إلى هذا الإصدار

والكود الخاص بي:

#define _SECURE_SCL 0

#include <ctime>
#include <vector>
#include <set>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <windows.h>

template <typename T, typename OutIter>
void stl_intersect(const T& set1, const T& set2, OutIter out){
    std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), out);
}

template <typename T, typename OutIter>
void sort_stl_intersect(T& set1, T& set2, OutIter out){
    std::sort(set1.begin(), set1.end());
    std::sort(set2.begin(), set2.end());
    std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), out);
}


template <typename T>
void init_sorted_vec(T first, T last){
    for ( T cur = first; cur != last; ++cur)
    {
        int i = cur - first;
        int value = 1000000000 + i;
        *cur = value;
    }
}

template <typename T>
void init_unsorted_vec(T first, T last){
    for ( T cur = first; cur != last; ++cur)
    {
        int i = rand() % 200000 + 1;
        i *= 10;

        int value = 1000000000 + i;
        *cur = value;
    }
}

struct resize_and_shuffle {
    resize_and_shuffle(int size) : size(size) {}

    void operator()(std::vector<int>& vec){
        vec.resize(size);

    }
    int size;
};

int main()
{
    srand ( time(NULL) );
    std::vector<int> out(100000);

    std::vector<int> sortedvec1(100000);
    std::vector<int> sortedvec2(1000);

    init_sorted_vec(sortedvec1.begin(), sortedvec1.end());
    init_unsorted_vec(sortedvec2.begin(), sortedvec2.end());
    std::sort(sortedvec2.begin(), sortedvec2.end());

    std::vector<int> unsortedvec1(sortedvec1.begin(), sortedvec1.end());
    std::vector<int> unsortedvec2(sortedvec2.begin(), sortedvec2.end());

    std::random_shuffle(unsortedvec1.begin(), unsortedvec1.end());
    std::random_shuffle(unsortedvec2.begin(), unsortedvec2.end());

    std::vector<int> vecs1[1000];
    std::vector<int> vecs2[1000];

    std::fill(vecs1, vecs1 + 1000, unsortedvec1);
    std::fill(vecs2, vecs2 + 1000, unsortedvec2);

    std::set<int> set1(sortedvec1.begin(), sortedvec1.end());
    std::set<int> set2(sortedvec2.begin(), sortedvec2.end());

    std::tr1::unordered_set<int> uset1(sortedvec1.begin(), sortedvec1.end());
    std::tr1::unordered_set<int> uset2(sortedvec2.begin(), sortedvec2.end());

    DWORD start, stop;
    DWORD delta[4];

    start = GetTickCount();
    for (int i = 0; i < 1000; ++i){
        stl_intersect(set1, set2, out.begin());
    }
    stop = GetTickCount();
    delta[0] = stop - start;

    start = GetTickCount();
    for (int i = 0; i < 1000; ++i){
        stl_intersect(uset1, uset2, out.begin());
    }
    stop = GetTickCount();
    delta[1] = stop - start;

    start = GetTickCount();
    for (int i = 0; i < 1000; ++i){
        stl_intersect(sortedvec1, sortedvec2, out.begin());
    }
    stop = GetTickCount();
    delta[2] = stop - start;

    start = GetTickCount();
    for (int i = 0; i < 1000; ++i){
        sort_stl_intersect(vecs1[i], vecs1[i], out.begin());
    }
    stop = GetTickCount();
    delta[3] = stop - start;

    std::cout << "std::set_intersection on std::set: " << delta[0] << "ms\n";
    std::cout << "std::set_intersection on tr1::unordered_set: " << delta[1] << "ms\n";
    std::cout << "std::set_intersection on sorted vectors: " << delta[2] << "ms\n";
    std::cout << "std::set_intersection on unsorted vectors: " << delta[3] << "ms\n";


    return 0;
}

لا يوجد سبب يجعل لغة C++ دائمًا أسرع من لغة C#.تتمتع لغة #C ببعض المزايا الأساسية التي تتطلب الكثير من العناية للتنافس معها في لغة C++.الشيء الأساسي الذي يمكنني التفكير فيه هو أن التخصيصات الديناميكية رخيصة بشكل يبعث على السخرية في .NET-land.في كل مرة يتعين على ناقل C++ أو set أو unordered_set (أو أي حاوية أخرى) تغيير حجمها أو توسيعها، يكون ذلك مكلفًا للغاية malloc عملية.في .NET، يعد تخصيص الكومة أكثر قليلاً من مجرد إضافة إزاحة إلى المؤشر.

لذلك، إذا كنت تريد أن يتنافس إصدار C++، فمن المحتمل أن يتعين عليك حل هذه المشكلة، مما يسمح للحاويات الخاصة بك بتغيير حجمها دون الحاجة إلى إجراء عمليات تخصيص الكومة الفعلية، ربما باستخدام مخصصات مخصصة للحاويات (ربما يكون Boost::pool جيدًا الرهان، أو يمكنك محاولة المتداول بنفسك)

قضية أخرى هي أن set_difference يعمل فقط على المدخلات المصنفة، ومن أجل إعادة إنتاج نتائج الاختبارات التي تتضمن الفرز، يتعين علينا عمل نسخة جديدة من البيانات غير المصنفة في كل تكرار، وهو أمر مكلف (على الرغم من أن استخدام المخصصات المخصصة سيساعد كثيرًا مرة أخرى).لا أعرف الشكل الذي ستتخذه مدخلاتك، ولكن من الممكن أن تتمكن من فرز مدخلاتك مباشرة، دون نسخها، ثم تشغيلها set_difference مباشرة على ذلك.(سيكون من السهل القيام بذلك إذا كان إدخالك عبارة عن مصفوفة أو حاوية STL على الأقل.)

إحدى المزايا الرئيسية لـ STL هي أنها مرنة جدًا، ويمكنها العمل على أي تسلسل إدخال تقريبًا.في C#، يتعين عليك إلى حد كبير نسخ الإدخال إلى قائمة أو قاموس أو شيء من هذا القبيل، ولكن في C++، قد تتمكن من الهروب من التشغيل std::sort و set_intersection على المدخلات الخام.

وأخيرًا، بالطبع، حاول تشغيل التعليمات البرمجية من خلال ملف التعريف وانظر بالضبط أين يتم قضاء الوقت.قد ترغب أيضًا في تجربة تشغيل الكود من خلال دول مجلس التعاون الخليجي بدلاً من ذلك.لدي انطباع بأن أداء STL في MSVC يكون أحيانًا غريبًا بعض الشيء.قد يكون من المفيد الاختبار تحت مترجم آخر فقط لمعرفة ما إذا كنت ستحصل على توقيتات مماثلة هناك.

أخيرًا، قد تجد منشورات المدونة هذه ذات صلة بأداء C++ مقابل C#:http://blogs.msdn.com/ricom/archive/2005/05/10/416151.aspx

الروح المعنوية لهؤلاء هي في الأساس أنه نعم، يمكنك الحصول على أداء أفضل في لغة C++، لكنه يتطلب قدرًا مدهشًا من العمل.

Answer 2

إحدى المشاكل التي أراها على الفور هي أنك تقوم بتمرير المجموعات في C++ حسب القيمة وليس حسب المرجع الثابت.لذا فأنت تقوم بنسخها في كل مرة تقوم بتمريرها!

أيضًا، لن أستخدم مجموعة لهدف set_intersection.سأستخدم شيئًا مثل

int runSetIntersection(const set<int>& set1, const set<int>& set2)
{   
    vector<int> intersection;
    intersection.reserve(10000) // or whatever the max is

    set_intersection(set1.begin(),set1.end(), set2.begin(), set2.end(), back_inserter(intersection));

    return intersection.size(); 
}

ومع ذلك، لا يزال هذا الرمز يخصص داخل الوظيفة.حتى أسرع سيكون

int runSetIntersection(const set<int>& set1, const set<int>& set2, vector<int>& scratch)
{   
    scratch.reserve(10000) // or whatever the max is

    set_intersection(set1.begin(),set1.end(), set2.begin(), set2.end(), back_inserter(scratch));

    return scratch.size(); 
}

ثم قم بتخصيص نقطة الصفر قبل بدء تشغيل المؤقت.

ومع ذلك، إذا كنت تبحث فقط عن الحجم، فإن حلقة for المكتوبة بخط اليد، بالإضافة إلى set::find قد تعطي نتائج أفضل.

Answer 3

استخدم هذا...

vector<int> set1(10000);
vector<int> set2(1000);

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

Answer 4

أود تغيير "runIntersectionTest" C++ لأخذ مراجع ثابتة للحاويات بدلاً من نسخها في كل مكالمة.(سيستخدم رمز C# المراجع.)

Answer 5

قد يكون من المفيد أيضًا النظر إلى التعزيز مجموعة مفككة الحاوية، والتي تم تحسينها خصيصًا لأنواع معينة من عمليات المجموعة الكبيرة.

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

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

Answer 6

بالمناسبة, إذا كان لديك كبيرة فرز مجموعات std::set_intersection ليس أسرع من خوارزمية.الأمراض المنقولة جنسيا::set_intersection يستغرق ما يصل إلى 2*(م+ن)-1 المقارنات ولكن خوارزميات مثل واحد من بايزا-ييتس يمكن أن يكون أسرع.الصغيرة م ، بايزا-ييتس O(m * log(n)) ، في حين ن = ألفا * m هي O(n).الفكرة الأساسية هي أن تفعل هذا النوع من 2 طريقة البحث الثنائية.

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91.7899&rep=rep1&type=pdf

التجريبية تحليل سريع تقاطع خوارزمية فرز تسلسل ريكاردو بايزا-ييتس و اليخاندرو سالينغر

أو

R.بايزا-ييتس.بسرعة تعيين تقاطع خوارزمية فرز متواليات.في إجراءات 15 الندوة السنوية على اندماجي نمط مطابقة (CPM 2004) ، الوثاب LNCS 3109, pp 400-408, اسطنبول, تركيا, تموز / يوليه 2004.

وفيما يلي شرحا تنفيذ إريك فراي حيث أنه يظهر بشكل أسرع النتائج من الأمراض المنقولة جنسيا::set_intersection مع ثنائي التحقيق.لم أحاول رمز له حتى الآن.
http://fawx.com/

1. اختيار الوسيط عنصر ، ، مجموعة أصغر.
2. البحث عن الإدراج-موقف العنصر ، ب ، أكبر مجموعة.
3. إذا كان A و B تساوي إلحاق العنصر النتيجة.
4. كرر الخطوات من 1-4 على غير فارغة مجموعات فرعية على جانبي عناصر A و B.

;

/*
* baeza_intersect
*/
قالب< قالب فئة التحقيق ، 
 فئة RandomAccessIterator الدرجة OutputIterator>
الفراغ baeza_intersect(RandomAccessIterator begin1, RandomAccessIterator end1,
 RandomAccessIterator begin2, RandomAccessIterator end2,
 OutputIterator الخروج)
{
 RandomAccessIterator probe1, probe2;

إذا كان ( (end1 - begin1) < ( end2 - begin2 ) )
{
 إذا ( begin1 == end1 )
 العودة ؛ probe1 = begin1 + ( ( end1 - begin1 ) >> 1 );probe2 = lower_bound< مسبار >( begin2, end2, *probe1 );baeza_intersect< مسبار >(begin1, probe1, begin2, probe2،);// التداخل اليسار
 إذا (!(probe2 == end2 || *probe1 < *probe2 ))
 *الخروج++ = *probe2++;baeza_intersect< مسبار >(++probe1, end1, probe2, end2،);// التداخل الحق
}
آخر
{
 إذا ( begin2 == end2 )
 العودة ؛ probe2 = begin2 + ( ( end2 - begin2 ) >> 1 );probe1 = lower_bound< مسبار >( begin1, end1, *probe2 );baeza_intersect< مسبار >(begin1, probe1, begin2, probe2،);// التداخل اليسار
 إذا (!(probe1 == end1 || *probe2 < *probe1 ))
 *الخروج++ = *probe1++;baeza_intersect< مسبار >(probe1, end1, ++probe2, end2،);// التداخل الحق
}
}

/*
* مع المقارنة
*/
 قالب< قالب فئة التحقيق ، 
 فئة RandomAccessIterator الدرجة OutputIterator ، والطبقة المقارنة >
 الفراغ baeza_intersect(RandomAccessIterator begin1, RandomAccessIterator end1,
 RandomAccessIterator begin2, RandomAccessIterator end2,
 OutputIterator ، المقارنة cmp)
{
 RandomAccessIterator probe1, probe2;

  if ( (end1 - begin1) < ( end2 - begin2 ) )
  {
    if ( begin1 == end1 )
      return;
    probe1 = begin1 + ( ( end1 - begin1 ) >> 1 );
    probe2 = lower_bound< Probe >( begin2, end2, *probe1, cmp );
    baeza_intersect< Probe >(begin1, probe1, begin2, probe2, out, cmp); // intersect left
    if (! (probe2 == end2 || cmp( *probe1, *probe2 ) ))
      *out++ = *probe2++;
    baeza_intersect< Probe >(++probe1, end1, probe2, end2, out, cmp); // intersect right
  }
  else
  {
    if ( begin2 == end2 )
      return;
    probe2 = begin2 + ( ( end2 - begin2 ) >> 1 );
    probe1 = lower_bound< Probe >( begin1, end1, *probe2, cmp );
    baeza_intersect< Probe >(begin1, probe1, begin2, probe2, out, cmp); // intersect left
    if (! (probe1 == end1 || cmp( *probe2, *probe1 ) ))
      *out++ = *probe1++;
    baeza_intersect< Probe >(probe1, end1, ++probe2, end2, out, cmp); // intersect right
  }
}


// التحقيق.hpp

/**
* ثنائي التحقيق:اختيار العنصر التالي عن طريق اختيار نقطة منتصف الطريق بين انخفاض وارتفاع
*/
قالب< فئة RandomAccessIterator ، فئة T >
البنية binary_probe
{
 RandomAccessIterator المشغل()(RandomAccessIterator تبدأ ، RandomAccessIterator الغاية ، const T & قيمة)
{
 عودة begin + ( (نهاية begin) >> 1);}
};

/**
* lower_bound:مثل المحكمة lower_bound ولكن مع أنواع مختلفة من التحقيق
* ملاحظة ظهور نادر قالب المعلمة القالب!*/
قالب< قالب فئة التحقيق ، فئة RandomAccessIterator ، فئة T >
RandomAccessIterator lower_bound(RandomAccessIterator تبدأ ، RandomAccessIterator الغاية ، const T & قيمة)
{
 RandomAccessIterator حفرة ؛ التحقيق< RandomAccessIterator ، T > pfunc;// مسبار-functor (يريد الحصول على وظائفها قد يصل)

في حين أن ( تبدأ < end )
{
 حفرة = pfunc(begin, end, value);إذا ( *حفرة < قيمة )
 begin = حفرة + 1;آخر
 end = حفرة ؛ }
 عودة لتبدأ ؛ }

/*
* هذه المرة مع للمقارنة!*/
قالب< قالب فئة التحقيق ، فئة RandomAccessIterator, T فئة, فئة المقارنة >
RandomAccessIterator lower_bound(RandomAccessIterator تبدأ ، RandomAccessIterator الغاية ، const T & القيمة المقارنة cmp)
{
 RandomAccessIterator حفرة ؛ التحقيق< RandomAccessIterator ، T > pfunc;

في حين أن ( تبدأ < end )
{
 حفرة = pfunc(begin, end, value);إذا ( cmp(*حفرة ، قيمة) )
 begin = حفرة + 1;آخر
 end = حفرة ؛ }
 عودة لتبدأ ؛ }

Answer 7

نظرًا لأنك تستخدم Visual Studio، فيجب عليك التحقق مما إذا كان لديك _SECURE_SCL اضبط على 1 (عادةً إذا لم تقم بتعيينه بشكل صريح فسيكون 1).إذا تم ضبطه، فسيتم فحص نطاق جميع رموز STL، حتى في إصدارات الإصدار.عادةً ما يتم إبطاء الكود بنسبة 10-15٪.

يبدو أن Microsoft لم تكن على علم بأن std::vector على سبيل المثال لديه واجهة بالفعل إذا كنت تريد التحقق من النطاق:الأمراض المنقولة جنسيا::vector::at()!

(آسف، كان علي أن أخرجه من صدري).

على أي حال، فإن عدم الكفاءة الرئيسي هو أنك تقوم بنسخ الحاويات بدلاً من تمريرها حسب القيمة.استخدم المراجع (لمحاولة) مقارنة التفاح والتفاح بدلاً من التفاح والموز.

Answer 8

أعرف أن الحل الخاص بك يعمل بشكل جيد، ولكن هل حاولت استخدام تطبيقات STL:

• يشمل
• set_intersection

ربما تم تحسينه لمنصتك بالفعل، لذا سأجربه

Answer 9

هل تم تشغيل إشارات تحسين C++؟

Answer 10

حسنًا، بعد الكثير من التعليقات، قمت بتحديث السؤال الأصلي عدة مرات:

• يتم الآن إجراء الاختبارات 1000 مرة
• يستخدم كود C# الآن مؤقتًا بدقة أعلى
• يتم الآن ملء هياكل البيانات قبل الاختبارات

والنتيجة حتى الآن هي أن لغة C# لا تزال أسرع بنحو 5 مرات من لغة C++.

شكرا للجميع على أفكارك / اقتراحاتك.

Answer 11

تحديث:

لقد قمت بتعديل كود set_intersection لاستخدام المتجهات وفرزها (بدلاً من استخدام فئة المجموعة التي تم فرزها)، وأصبح الأمر أسرع بكثير الآن:

Found the intersection of 319 values (using unordered_map) 1000 times, in 22187.5ms
Found the intersection of 315 values (using set_intersection) 1000 times, in 2401.62ms

تذكر:يتم إنشاء المجموعة الأكبر مرتبة، لذا قد لا يستغرق الفرز الكثير من الوقت في هذا المثال.

كود سي++:

// MapPerformance.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <hash_map>
#include <vector>
#include <iostream>
#include <time.h>
#include <algorithm>
#include <set>

#include <boost\unordered\unordered_map.hpp>

#include "timer.h"

using namespace std;
using namespace stdext;
using namespace boost;

int runIntersectionTest(vector<int> set1, vector<int> set2)
{
    // hash_map<int,int> theMap;
    // map<int,int> theMap;
    unordered_map<int,int> theMap;

    // Now intersect the two sets by populating the map
    for ( vector<int>::iterator iterator = set1.begin(); iterator != set1.end(); iterator++ )
    {
        int value = *iterator;

        theMap[value] = 1;
    }

    int intersectionSize = 0;

    for ( vector<int>::iterator iterator = set2.begin(); iterator != set2.end(); iterator++ )
    {
        int value = *iterator;

        unordered_map<int,int>::iterator foundValue = theMap.find(value);

        if ( foundValue != theMap.end() )
        {
            theMap[value] = 2;

            intersectionSize++;
        }
    }

    return intersectionSize;

}

int runSetIntersection(vector<int> set1, vector<int> set2)
{   
    sort(set1.begin(),set1.end());
    sort(set2.begin(),set2.end());

    set<int> intersection;

    set_intersection(set1.begin(),set1.end(), set2.begin(), set2.end(), inserter(intersection, intersection.end()));

    return intersection.size(); 
}



int _tmain(int argc, _TCHAR* argv[])
{
    srand ( time(NULL) );

    vector<int> set1;
    vector<int> set2;

    set1.reserve(10000);
    set2.reserve(1000);

    // Create 100,000 values for set1
    for ( int i = 0; i < 100000; i++ )
    {
        int value = 1000000000 + i;
        set1.push_back(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.push_back(value);
    }

    int intersectionSize = 0;


    Timer timer;
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runIntersectionTest(set1, set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using unordered_map) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    timer.Reset();
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runSetIntersection(set1,set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using set_intersection) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    getchar();

    return 0;
}

Answer 12

أنت لا تزال تمرر المتجهات حسب القيمة.والذي سيكون جيدًا إذا لم تقم بنسخها أيضًا.

لم يكن المُدرج يضع القيم في نهاية المتجه حيث يكون سريعًا.لقد فعلت ذلك فقط في الإدخال الأول بعد ذلك قامت بإدراج القيمة في بداية المصفوفة (حيث تستخدم النهاية للإشارة).

يمكنك البحث عن القيمة مرتين في إصدار خريطة التجزئة، عند تحديث القيمة.لماذا يتم تحديث حدث القيمة هذا؟

قم بتشغيل هذا الرمز ونشر التوقيت الخاص بك.

// MapPerformance.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <hash_map>
#include <vector>
#include <iostream>
#include <time.h>
#include <algorithm>
#include <set>

#include <boost\unordered\unordered_set.hpp>

#include "timer.h"

using namespace std;
using namespace stdext;
using namespace boost;

int runIntersectionTest(const vector<int>& set1, const vector<int>& set2)
{
    // hash_map<int,int> theMap;
    // map<int,int> theMap;
    unordered_set<int> theSet;      

     theSet.insert( set1.begin(), set2.end() );

    int intersectionSize = 0;

    vector<int>::const_iterator set2_end = set2.end();

    for ( vector<int>::const_iterator iterator = set2.begin(); iterator != set2_end; ++iterator )
    {
        if ( theSet.find(*iterator) != theSet.end() )
        {
                intersectionSize++;
        }
    }

    return intersectionSize;
}

int runSetIntersection( vector<int> set1, vector<int> set2)
{   
    // Sort the data
    sort(set1.begin(),set1.end());
    sort(set2.begin(),set2.end());

    vector<int> intersection;
    intersection.reserve(1000);

    set_intersection(set1.begin(),set1.end(), set2.begin(), set2.end(), back_inserter(intersection));

    return intersection.size(); 
}

void createSets( vector<int>& set1, vector<int>& set2 )
{
    srand ( time(NULL) );

    set1.reserve(100000);
    set2.reserve(1000);

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

    // Try to get half of our values intersecting
    float ratio = 200000.0f / RAND_MAX;


    // Create 1,000 values for set2
    for ( int i = 0; i < 1000; i++ )
    {
        int random = rand() * ratio + 1;

        int value = 1000000000 + random;
        set2.push_back(value);
    }

    // Make sure set1 is in random order (not sorted)
    random_shuffle(set1.begin(),set1.end());
}

int _tmain(int argc, _TCHAR* argv[])
{
    int intersectionSize = 0;

    vector<int> set1, set2;     
    createSets( set1, set2 );

    Timer timer;
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runIntersectionTest(set1, set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using unordered_map) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    timer.Reset();
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runSetIntersection(set1,set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using set_intersection) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    getchar();

    return 0;
}

Answer 13

أحدث المعايير:

Found the intersection of 504 values (using unordered_map) 1000 times, in 28827.6ms
Found the intersection of 495 values (using set_intersection) 1000 times, in 9817.69ms
Found the intersection of 504 values (using unordered_set) 1000 times, in 24769.1ms

أعتقد أن الفرق 504 - 495 يحدث بسبب وجود قيمتين مزيفتين.

Code:

// MapPerformance.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <hash_map>
#include <vector>
#include <iostream>
#include <time.h>
#include <algorithm>
#include <set>
#include <unordered_set>

#include <boost\unordered\unordered_map.hpp>

#include "timer.h"

using namespace std;
using namespace stdext;
using namespace boost;
using namespace tr1;


int runIntersectionTest2(const vector<int>& set1, const vector<int>& set2)
{
    // hash_map<int,int> theMap;
    // map<int,int> theMap;
    unordered_set<int> theSet;      

     theSet.insert( set1.begin(), set1.end() );

    int intersectionSize = 0;

    vector<int>::const_iterator set2_end = set2.end();

    for ( vector<int>::const_iterator iterator = set2.begin(); iterator != set2_end; ++iterator )
    {
        if ( theSet.find(*iterator) != theSet.end() )
        {
                intersectionSize++;
        }
    }

    return intersectionSize;
}

int runIntersectionTest(const vector<int>& set1, const vector<int>& set2)
{
    // hash_map<int,int> theMap;
    // map<int,int> theMap;
    unordered_map<int,int> theMap;  

    vector<int>::const_iterator set1_end = set1.end();

    // Now intersect the two sets by populating the map
    for ( vector<int>::const_iterator iterator = set1.begin(); iterator != set1_end; ++iterator )
    {
        int value = *iterator;

        theMap[value] = 1;
    }

    int intersectionSize = 0;

    vector<int>::const_iterator set2_end = set2.end();

    for ( vector<int>::const_iterator iterator = set2.begin(); iterator != set2_end; ++iterator )
    {
        int value = *iterator;

        unordered_map<int,int>::iterator foundValue = theMap.find(value);

        if ( foundValue != theMap.end() )
        {
            theMap[value] = 2;

            intersectionSize++;
        }
    }

    return intersectionSize;

}

int runSetIntersection(const vector<int>& set1_unsorted, const vector<int>& set2_unsorted)
{   
    // Create two vectors
    std::vector<int> set1(set1_unsorted.size());
    std::vector<int> set2(set2_unsorted.size());

    // Copy the unsorted data into them
    std::copy(set1_unsorted.begin(), set1_unsorted.end(), set1.begin());
    std::copy(set2_unsorted.begin(), set2_unsorted.end(), set2.begin());

    // Sort the data
    sort(set1.begin(),set1.end());
    sort(set2.begin(),set2.end());

    vector<int> intersection;
    intersection.reserve(1000);

    set_intersection(set1.begin(),set1.end(), set2.begin(), set2.end(), back_inserter(intersection));

    return intersection.size(); 
}

void createSets( vector<int>& set1, vector<int>& set2 )
{
    srand ( time(NULL) );

    set1.reserve(100000);
    set2.reserve(1000);

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

    // Try to get half of our values intersecting
    float ratio = 200000.0f / RAND_MAX;


    // Create 1,000 values for set2
    for ( int i = 0; i < 1000; i++ )
    {
        int random = rand() * ratio + 1;

        int value = 1000000000 + random;
        set2.push_back(value);
    }

    // Make sure set1 is in random order (not sorted)
    random_shuffle(set1.begin(),set1.end());
}

int _tmain(int argc, _TCHAR* argv[])
{
    int intersectionSize = 0;

    vector<int> set1, set2; 
    createSets( set1, set2 );

    Timer timer;
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runIntersectionTest(set1, set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using unordered_map) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    timer.Reset();
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runSetIntersection(set1,set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using set_intersection) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    timer.Reset();
    for ( int i = 0; i < 1000; i++ )
    {
        intersectionSize = runIntersectionTest2(set1,set2);
    }
    timer.Stop();

    cout << "Found the intersection of " << intersectionSize << " values (using unordered_set) 1000 times, in " << timer.GetMilliseconds() << "ms" << endl;

    getchar();

    return 0;
}