Schnelle Schnittmenge: C ++ vs C #

StackOverflow https://stackoverflow.com/questions/1060648

Frage

Auf meinem Rechner (Quad-Core, 8gb ram), läuft Vista x64 Geschäft, mit Visual Studio 2008 SP1, ich versuche, sehr schnell zwei Reihen von Zahlen zu schneiden.

Ich habe zwei Ansätze in C ++ implementiert und eine in C #. Der C # Ansatz ist schneller, so weit, ich mag den C ++ Ansatz zu verbessern, um seine schneller als C #, die ich C ++ erwarten tun können.

Hier ist die C # Ausgabe: (Release Build) 

Found the intersection 1000 times, in 4741.407 ms

Hier ist der erste C ++ Ausgang für zwei verschiedene Ansätze (Release x64 build): 

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

Hier ist die neueste C ++ Ausgabe, für drei Ansätze (Release x64 build):

Aktuelle Benchmark: 

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

So ist der set_intersection Ansatz jetzt ca. 2x langsamer als C #, aber 2x schneller als die ursprünglichen C ++ Ansätze.

Die neueste 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 # -Code: 

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

Ok, hier ist die neueste, mit einigen Änderungen:

  • Die C ++ Sets sind jetzt korrekt eingerichtet, so dass sie eine 50% ige Kreuzung (wie der C #)
    • haben
  • Set1 wird neu gemischt so dass ihr nicht sortiert wurde set2 schon nicht sortiert
  • Die set_intersection Implementierung verwendet nun Vektoren und sortiert sie zuerst

C ++ (Release, x64) Ergebnisse: 

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

So sein 2x langsamer als C #. @Jalf: Sie bekommen ein paar ziemlich schnell Zahlen, ist es etwas, was ich falsch hier tue?

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;
}
War es hilfreich?

Lösung

Es gibt mehrere Probleme mit Ihrem Test.

Als erstes werden Sie nicht Schnitt Probierset, sondern „erstellen ein paar Arrays, füllen sie mit Zufallszahlen, und dann Satz Kreuzung durchführen“. Sie sollten nur den Teil des Codes Zeit, die Sie in wirklich interessiert sind. Selbst wenn Sie diese Dinge wollen, tun werden, sollten sie hier nicht verglichen werden. Messen Sie eine Sache zu einer Zeit, zu Unsicherheit zu reduzieren. Wenn Sie Ihre C ++ Implementierung wollen bessere Leistungen zu erbringen, müssen Sie zuerst wissen, welche ein Teil davon ist langsamer als erwartet. Was bedeutet, müssen Sie Setup-Code von Schnitttest trennen.

Zweitens sollten Sie den Test eine große Anzahl von Zeiten laufen kann Caching-Effekte und andere Unsicherheiten zu berücksichtigen. (Und wahrscheinlich Ausgang einer Gesamtzeit für, sagen wir, 1000 läuft, anstatt eine individuelle Zeit für jeden. Sie können die Unsicherheit aus dem Timer verringern, die begrenzte Auflösung haben könnte und ungenaue Ergebnisse berichten, wenn im 0-20ms Bereich verwendet.

Ferner soweit ich aus der docs lesen kann, sollte die Eingabe in set_intersection sortiert werden, was set2 wird nicht sein. Ein scheint es keinen Grund zu sein unordered_map zu verwenden, wenn unordered_set ein weit besseres Spiel wäre für das, was Sie tun.

Über die Setup-Code benötigt wird, beachten Sie, dass Sie wahrscheinlich nicht müssen Vektoren, um zu bevölkern die Kreuzung zu laufen. Sowohl Ihre eigene Implementierung und set_intersection Arbeit auf Iteratoren bereits, so können Sie sie einfach ein Paar von Iteratoren auf die Datenstrukturen Ihre Eingaben zu übergeben sind in bereits.

Noch ein paar spezifischen Kommentare zu Ihrem Code:

  • Verwenden Sie ++iterator statt iterator++
  • anstatt vector.end () aufgerufen wird bei jeder Schleifeniterationslatenzzeit, nennen Sie es einmal und cachen das Ergebnis
  • Experiment mit der Verwendung sortiert Vektoren vs std :: set vs unordered_set (nicht unordered_map)

Edit:

Ich habe Ihre C # Version nicht versucht, so kann ich die Zahlen richtig nicht zu vergleichen, aber hier ist mein modifizierter Test. Jedes Zimmer ist 1000-mal ausgeführt werden, auf einen Core 2 Quad 2,5 GHz mit 4 GB RAM: 

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

Die letzte ist ein bisschen unfair, weil sie beide haben zu kopieren und die Vektoren sortieren. Idealerweise sollte nur die Art Teil der Benchmark sein. Ich versuchte, eine Version zu schaffen, die ein Array von 1000 unsortierten Vektoren verwendet (so woudln't Ich habe die unsortierten Daten in jeder Iteration kopieren), aber die Leistung war ungefähr die gleiche oder etwas schlechter, da diese Konstante Cache-Fehltreffer führen würde , so kehrte ich auf diese Version zurück

Und mein Code: 

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

Es gibt keinen Grund, warum C ++ immer schneller als C # sein sollte. C # hat einige entscheidende Vorteile, die viel Sorgfalt erfordern mit in C ++ zu konkurrieren. Die primär ich denken kann, ist, dass dynamische Zuweisungen lächerlich billig sind in .NET-Land. Jedes Mal, wenn ein C ++ Vektor, eingestellt oder unordered_set (oder ein anderer Behälter) hat, um die Größe oder zu erweitern, ist es ein sehr teurer malloc Betrieb. In .NET ist eine Heapzuordnung wenig mehr als das Hinzufügen eines Offset auf einen Zeiger.

Wenn Sie also die C ++ Version wollen zu konkurrieren, werden Sie wahrscheinlich, dass zu lösen haben, Ihre Container ermöglicht, ohne, um die Größe, die tatsächlichen Heapzuweisungen auszuführen, die wahrscheinlich von benutzerdefinierten Verteilern unter Verwendung für die Behälter (vielleicht boost :: Pool könnte sein eine gute Wette, oder Sie können versuchen, Ihre eigenen) rollen

Ein weiteres Problem ist, dass set_difference nur auf sortierten Eingang arbeitet, und um Testergebnisse zu reproduzieren, die eine Art beinhalten, müssen wir eine neue Kopie der unsortierten Daten in jeder Iteration machen, was teuer ist (obwohl wieder, individuelle Verwendung Verteilern wird viel) helfen. Ich weiß nicht, welche Form Ihre Eingabe verwendet, aber es ist möglich, dass Sie Ihre Eingabe direkt sortieren können, ohne sie zu kopieren, und dann laufen set_difference direkt darauf. (Das wäre einfach zu tun, wenn Sie Ihre Eingabe ein Array oder ein STL-Container zumindest.)

Ein the Schlüsselvorteile der STL ist, dass es so flexibel ist, kann es ziemlich jede Eingabesequenz arbeiten. In C # Sie haben ziemlich viel um die Eingabe zu einer Liste oder Wörterbuch oder so etwas, aber in C ++ zu kopieren, können Sie in der Lage sein, um wegzukommen mit std::sort und set_intersection auf dem Roh-Eingang ausgeführt wird.

Schließlich natürlich versuchen, den Code durch einen Profiler laufen und genau sehen, wo die Zeit ausgegeben wird. Vielleicht haben Sie auch den Code durch GCC laufen anstatt zu versuchen. Es ist mein Eindruck, dass STL Leistung in MSVC ist manchmal ein wenig schrullig. Es könnte nur die Prüfung unter einem anderen Compiler wert sein, um zu sehen, wenn Sie es ähnliche Timings erhalten.

Schließlich könnten Sie diese Blog-Beiträge relevant für die Leistung von C ++ vs C # finden: http://blogs.msdn.com/ricom/archive/2005 /05/10/416151.aspx

Die Moral davon ist im Wesentlichen, dass ja, können Sie eine bessere Leistung in C ++, aber es ist eine überraschende Menge an Arbeit.

Andere Tipps

Ein Problem, das ich sofort sehen, ist, dass Sie die Sätze in C ++ von Wert vorbei sind und nicht durch konstante Referenz. So Sie kopieren sie jedes Mal, wenn sie herum passieren!

Auch würde ich nicht einen Satz für das Ziel von set_intersection verwenden. Ich würde so etwas wie verwenden 

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(); 
}

Dieser Code jedoch weist nach wie vor innerhalb der Funktion. Noch schneller wäre 

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(); 
}

Und dann kratzen zuweisen, bevor Sie den Timer zu starten.

Obwohl, wenn Sie gerade für die Größe, ein handgeschriebener for-Schleife, kombiniert mit einem Satz suchen :: finden könnte noch bessere Ergebnisse liefern.

Verwenden Sie diese Option ... 

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

... um Vektoren von Nicht-Null-Anfangsgröße. Dann verwenden Sie nicht push_back, sondern nur die Werte direkt aktualisieren.

Ich würde die C ++ ändern „runIntersectionTest“ const Verweise auf die Behälter zu nehmen, anstatt sie bei jedem Aufruf kopier aufgebaut ist. (Der C # -Code wird mit Refs sein.)

Es kann auch sinnvoll sein, bei dem Boost suchen disjunktes Set Container, die für bestimmte Arten von großen Mengenoperationen speziell optimiert ist.

Es funktioniert durch eine Gruppe von Sätzen, wie die Gewerkschaften aus mehreren disjunkten Mengen zu behandeln, die es ermöglichen, andere Sätze, wie Kreuzungen oder Gewerkschaften sehr billig zu bauen, sobald der anfängliche Satz von disjunkten Mengen aufgebaut ist. Wenn Sie erwarten viel von Set-Operationen auf Gruppen zu tun, die nicht viel ändern, können Sie wahrscheinlich erwarten, dass dies sehr schnell sein. Wenn auf der anderen Seite, werden Sie jeweils einmal eingestellt verwenden und werfen es weg, ist es wahrscheinlich nicht zu viel tun wird.

Wie auch immer, würden Sie sich selbst einen Gefallen zu mindestens Experiment mit tun dies, um zu sehen, ob es Ihnen jede Beule in Ihrem speziellen Fall gibt.

By the way, wenn Sie große sortierte Sätze std :: set_intersection haben, ist nicht der schnellste Algorithmus. std :: set_intersection nimmt bis zu 2 * (m + n) -1 Vergleiche aber Algorithmen wie die von Baeza-Yates schneller sein kann. Für kleine m, Baeza-Yates ist O (m * log (n)), während für n = alpha * m es O (n) ist. Die Grundidee ist es, eine Art von 2-Wege-binäre Suche zu tun.

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

Experimentelle Analyse einer schnellen Überschneidung Algorithmus für die Sorted Sequenzen Ricardo Baeza-Yates und Alejandro Salinger

oder

R. Baeza-Yates. Ein Fast Set Überschneidung Algorithmus für die Sorted Sequenzen. Im Proceedings des 15. Jahressymposium über kombinatorische Pattern Matching (CPM 2004), Springer LNCS 3109, Seiten 400-408, Istanbul, Türkei, Juli 2004.

Im Folgenden finden Sie eine Erklärung und eine Implementierung von Erik Frey, wo er deutlich schneller Ergebnisse als std :: zeigt set_intersection mit einer binären Sonde. Ich habe seinen Code noch nicht ausprobiert.
http://fawx.com/

  1. Wählen Sie das mittlere Element, A, in der kleinere Menge.
  2. Suchen Sie nach ihrem Insertion-Positionselement, B, in die größere Menge.
  3. Wenn A und B gleich sind, hängen Sie das Element an die Ergebnis.
  4. Wiederholen Sie Schritte 1-4 auf nicht-leere Teilmengen auf jeder Seite der Elemente A und B.

; 




/*
* baeza_intersect
*/
template< template  class Probe,
  class RandomAccessIterator, class OutputIterator>
void baeza_intersect(RandomAccessIterator begin1, RandomAccessIterator end1,
                     RandomAccessIterator begin2, RandomAccessIterator end2,
                     OutputIterator out)
{
  RandomAccessIterator probe1, probe2;



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



/*
* with a comparator
*/
 template< template  class Probe,
      class RandomAccessIterator, class OutputIterator, class Comparator >
    void baeza_intersect(RandomAccessIterator begin1, RandomAccessIterator end1,
                         RandomAccessIterator begin2, RandomAccessIterator end2,
                         OutputIterator out, Comparator 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
  }
}




// probe.hpp



/**
* binary probe: pick the next element by choosing the halfway point between low and high
*/
template< class RandomAccessIterator, class T >
struct binary_probe
{
  RandomAccessIterator operator()(RandomAccessIterator begin, RandomAccessIterator end, const T & value)
  {
    return begin + ( (end - begin) >> 1);
  }
};



/**
* lower_bound: like stl's lower_bound but with different kinds of probing
* note the appearance of the rare template parameter template!
*/
template< template  class Probe, class RandomAccessIterator, class T >
RandomAccessIterator lower_bound(RandomAccessIterator begin, RandomAccessIterator end, const T & value)
{
  RandomAccessIterator pit;
  Probe< RandomAccessIterator, T > pfunc; // probe-functor (wants to get func'd up)



while ( begin < end )
  {
    pit = pfunc(begin, end, value);
    if ( *pit < value )
      begin = pit + 1;
    else
      end = pit;
  }
  return begin;
}



/*
* this time with a comparator!
*/
template< template  class Probe, class RandomAccessIterator, class T, class Comparator >
RandomAccessIterator lower_bound(RandomAccessIterator begin, RandomAccessIterator end, const T & value, Comparator cmp)
{
  RandomAccessIterator pit;
  Probe< RandomAccessIterator, T > pfunc;



while ( begin < end )
  {
    pit = pfunc(begin, end, value);
    if ( cmp(*pit, value) )
      begin = pit + 1;
    else
      end = pit;
  }
  return begin;
}

Da Sie Visual Studio verwenden, sollten Sie prüfen, ob Sie auf 1 gesetzt haben _SECURE_SCL (in der Regel, wenn Sie nicht explizit festgelegt haben, wird es 1 sein). Wenn es alle STL-Code-Set Bereich geprüft wird, auch in Release-Builds. Typischerweise Code Verlangsamung durch ein 10-15%.

Es scheint Microsoft nicht bewusst war, dass zum Beispiel std :: vector bereits eine Schnittstelle hat, wenn Sie den Bereich Prüfung wollen: std :: vector :: at ()

(Sorry, hatte es weg, um meine Brust).

Wie auch immer die Haupt Ineffizienz ist, dass Sie die Behälter sind zu kopieren, anstatt sie durch Wert übergeben. Verwenden Sie Verweise auf (versuchen) vergleichen Äpfel und Äpfel statt Äpfel und Bananen.

Ich weiß, dass Ihre Lösung funktioniert gut, aber haben Sie die STL-Implementierungen versucht mit:

Es könnte für Ihre plataform bereits optimiert werden, also würde ich gebe ihm einen Schuss

C ++ Optimierungen eingeschaltet?

Ok, nach viel Feedback habe ich die ursprüngliche Frage mehrmals aktualisiert:

  • Die Tests sind jetzt laufen jeweils 1000 mal
  • Der C # -Code verwendet nun eine höhere Auflösung Timer
  • Die Datenstrukturen werden nun vor den Tests bevölkerten

Das Ergebnis dieser so weit ist, dass C # noch ~ schneller 5x als C ++.

Vielen Dank allen für Ihre Ideen / Vorschläge.

Update:

I modifiziert, um die set_intersection Codevektoren zu verwenden, und sie zu sortieren (anstelle der sortierten Satz Klasse verwendet wird), und seine viel schneller jetzt: 

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

Beachten Sie:. Die größere Menge sortiert erstellt wird, so Sortierung es nicht viel Zeit in diesem Beispiel nehmen könnte

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

Sie passieren STILL die Vektoren von Wert. Die in Ordnung wäre, wenn man sich nicht auch das Kopieren wurde.

Inserter wurde nicht die Werte am Ende des Vektors Puting, wo es schnell ist. Es hat nur das auf dem ersten Einsatz nach, dass es den Wert am Anfang des Arrays eingefügt (wo Ende-zu-Punkt verwendet wird).

Sie, wo der Wert zweimal in der Hash-Karte Version nach oben, wenn Sie den Wert aktualisiert. Warum wird dieser Wert Ereignis aktualisiert werden?

diesen Code ausführen und Ihre Timings veröffentlichen. 

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

Aktuelle Benchmark: 

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

Ich denke, der 504-495 Unterschied geschieht, weil es ein paar Betrogene Werte

. 
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;
}
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top