Intersection rapide des ensembles :C++ contre C#

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

Question

Sur ma machine (Quad core, 8 Go de RAM), exécutant Vista x64 Business, avec Visual Studio 2008 SP1, j'essaie de croiser très rapidement deux ensembles de nombres.

J'ai implémenté deux approches en C++ et une en C#.L'approche C# est plus rapide jusqu'à présent, j'aimerais améliorer l'approche C++ pour qu'elle soit plus rapide que C#, ce que j'espère que C++ peut faire.

Voici la sortie C# :(version de version)

Found the intersection 1000 times, in 4741.407 ms

Voici la sortie C++ initiale, pour deux approches différentes (version Release x64) :

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

Voici la dernière sortie C++, pour trois approches (version Release x64) :

Dernier 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

Ainsi, l'approche set_intersection est désormais environ 2 fois plus lente que C#, mais 2 fois plus rapide que les approches C++ initiales.

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

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

Code C++ :

// 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, voici la dernière version, avec quelques modifications :

  • Les ensembles C++ sont désormais correctement configurés et ont donc une intersection de 50 % (comme le C#)
  • Set1 est mélangé donc il n'est pas trié, set2 n'était déjà pas trié
  • L'implémentation set_intersection utilise désormais des vecteurs et les trie en premier

Résultats C++ (version 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

C'est donc 2 fois plus lent que C#.@Jalf :Vous obtenez des chiffres assez rapides, y a-t-il quelque chose que je fais de mal ici ?

Code C++ :

// 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;
}
Était-ce utile?

La solution

Il y a plusieurs problèmes avec votre test.

Tout d'abord, vous n'êtes pas mis à l'essai intersection, mais « créer deux tableaux, les remplir avec des nombres aléatoires, puis effectuer le réglage intersection ». Vous ne devriez chronométrer la partie du code que vous êtes réellement intéressé. Même si vous allez vouloir faire ces choses, ils ne devraient pas être comparés ici. Mesurer une chose à la fois, de réduire l'incertitude. Si vous voulez que votre implémentation C ++ pour exécuter mieux, vous devez d'abord savoir quelle partie de celui-ci est plus lente que prévu. Ce qui signifie que vous devez code d'installation séparé de test d'intersection.

En second lieu, vous devez exécuter le test d'un grand nombre de fois pour prendre des effets de mise en cache possibles et d'autres incertitudes en compte. (Et probablement un temps total de sortie pour, disons, 1000 courses, plutôt que d'un temps individuel pour chacun. De cette façon, vous réduisez l'incertitude de la minuterie qui pourrait avoir une résolution limitée et faire rapport des résultats inexacts lorsqu'ils sont utilisés dans la gamme 0-20ms.

De plus, pour autant que je peux lire des documents, l'entrée set_intersection doivent être triés, qui set2 ne sera pas. Un il semble y avoir aucune raison d'utiliser unordered_map, quand serait un unordered_set match de beaucoup mieux pour ce que vous faites.

A propos du code de configuration étant nécessaire, notez que vous avez probablement ne pas doivent remplir des vecteurs pour exécuter l'intersection. À la fois votre propre mise en œuvre et le travail sur itérateurs set_intersection déjà, de sorte que vous pouvez simplement les passer une paire de itérateurs aux structures de données vos entrées sont déjà.

Quelques commentaires plus précis sur votre code:

  • Utilisez au lieu de ++iterator iterator++
  • plutôt que d'appeler vector.end () à chaque itération de la boucle, l'appeler une fois et mettre en cache le résultat
  • expérimenter en utilisant des vecteurs triés vs std :: set vs malloc (pas set_difference)

Modifier

Je ne l'ai pas essayé votre version C #, donc je ne peux pas comparer les chiffres correctement, mais voici mon test modifié. Chacun d'eux est exécuté 1000 fois, sur un Core 2 Quad 2,5 GHz avec 4 Go de 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

Le dernier est un peu injuste, car il doit à la fois copier et trier les vecteurs. Idéalement, seul le genre devrait faire partie de l'indice de référence. J'ai essayé de créer une version qui utilise un tableau de 1000 vecteurs non triés (donc je woudln't dois copier les données non triées dans chaque itération), mais la performance était sur le même ou un peu pire, parce que cela causerait misses cache constant , donc je revins revenir à cette version

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

Il n'y a aucune raison pour laquelle C ++ doit toujours être plus rapide que C #. C # a quelques avantages clés qui nécessitent beaucoup de soins pour concurrencer en C ++. Celui primaire, je peux penser est que les allocations dynamiques sont ridiculement pas cher en terre .NET. Chaque fois qu'un vecteur C ++, définir ou unordered_set (ou tout autre récipient) doit redimensionner ou se développer, il est une opération très coûteuse std::sort. Dans .NET, une allocation de tas est un peu plus que d'ajouter un décalage à un pointeur.

Donc, si vous voulez la version du C à la concurrence, vous aurez probablement à résoudre que, en permettant à vos conteneurs de redimensionner sans avoir à effectuer des allocations de tas réels, probablement à l'aide d'allocataires personnalisés pour les conteneurs (stimuler peut-être :: piscine pourrait être un bon pari, ou vous pouvez essayer rouler votre propre)

Une autre question est que ne fonctionne que sur <=> entrée triée, et afin de reproduire les résultats des essais qui impliquent une sorte, nous devons faire une nouvelle copie des données non triées dans chaque itération, ce qui est coûteux (bien qu'encore une fois, en utilisant allocateurs personnalisés vous aidera beaucoup). Je ne sais pas quelle forme votre entrée prend, mais il est possible que vous pouvez trier directement votre entrée, sans le copier, puis exécutez directement sur ce <=>. (Ce serait facile à faire si votre entrée est un tableau ou un conteneur STL au moins.)

L'un des principaux avantages de la STL est qu'il est si flexible, il peut fonctionner sur à peu près toute séquence d'entrée. En C #, vous avez à peu près à copier l'entrée à une liste ou dictionnaire ou quelque chose, maisen C ++, vous pourriez être en mesure de sortir avec en cours d'exécution et <=> sur l'entrée <=> brut.

Enfin, bien sûr, essayez d'exécuter le code par un profileur et voir exactement où le temps est passé. Vous pouvez également essayer d'exécuter le code par GCC à la place. Il est mon impression que la performance du TSL dans MSVC est parfois un peu bizarre. Il pourrait être intéressant de tester sous un autre compilateur juste pour voir si vous y horaires similaires.

Enfin, vous pouvez trouver ces messages de blog pertinents pour la performance de C ++ vs C #: http://blogs.msdn.com/ricom/archive/2005 /05/10/416151.aspx

Le moral de ceux-ci est essentiellement que oui, vous pouvez obtenir de meilleures performances en C ++, mais il est une quantité surprenante de travail.

Autres conseils

Un problème que je vois est bien loin que vous passez les ensembles en C ++ par valeur et non par référence const. Donc, vous les copier chaque fois que vous les transmettre autour de vous!

En outre, je ne voudrais pas utiliser un ensemble pour la cible de set_intersection. Je voudrais utiliser quelque chose comme 

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

Ce code, cependant, attribue encore à l'intérieur de la fonction. Encore plus rapide serait 

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

Et puis allouer zéro avant de commencer la minuterie.

Bien que, si vous êtes à la recherche de la taille, un écrit à la main pour la boucle, combinée avec l'ensemble :: trouver pourrait donner des résultats encore meilleurs.

Cette ... 

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

... pour obtenir des vecteurs de taille initiale non nulle. Merci de ne pas utiliser push_back, mais simplement mettre à jour les valeurs directement.

Je changerais le C ++ « runIntersectionTest » de prendre des références const aux conteneurs plutôt que de les copier-construits sur chaque appel. (Le code C # utilisera refs.)

Il peut également être utile de se pencher sur le coup de pouce disjoints Set récipient, qui est spécialement optimisée pour certains types de grandes opérations de réglage.

Il fonctionne en traitant un groupe d'ensembles comme les syndicats de plusieurs ensembles disjoints, permettant de construire d'autres ensembles, tels que les intersections ou les syndicats à très bon marché, une fois que la première série d'ensembles disjoints est construit. Si vous vous attendez à faire beaucoup d'opérations définies sur des ensembles qui ne changent pas beaucoup, vous pouvez vous attendre probablement que cela soit très rapide. Si, d'autre part, vous utiliserez chaque jeu une fois et le jeter, il ne va probablement pas faire trop.

Quoi qu'il en soit, vous seriez-vous en train de faire une faveur au moins expérimenter cela pour voir si elle vous donne une bosse dans votre cas.

Par ailleurs, si vous avez de grands ensembles std :: set_intersection triés n'est pas l'algorithme le plus rapide. std :: set_intersection prend jusqu'à 2 * (m + n) -1 comparaisons mais des algorithmes comme celui de Baeza-Yates peut être plus rapide. Pour les petits m, Baeza-Yates est O (m * log (n)), alors que pour n = alpha * m est O (n). L'idée de base est de faire une sorte de 2 voies recherche binaire.

http://citeseerx.ist .psu.edu / viewdoc / téléchargement? doi = 10.1.1.91.7899 & rep = rep1 & type = pdf

Analyse expérimentale d'une intersection rapide algorithme pour les séquences triées Ricardo Baeza-Yates et Alejandro Salinger

ou

R. Baeza-Yates. A l'intersection rapide Définir l'algorithme pour Sorted séquences. Dans Actes du 15e Symposium annuel sur Pattern Matching combinatoires (CPM 2004), Springer LNCS 3109, pp 400-408, Istanbul, Turquie, Juillet 2004.

Voici une explication et une mise en œuvre par Erik Frey où il montre des résultats beaucoup plus rapidement que std :: set_intersection avec une sonde binaire. Je ne l'ai pas encore essayé son code.
http://fawx.com/

  1. Choisir l'élément médian, A, dans la plus petit ensemble.
  2. Recherche pour son élément position d'insertion, B, en l'ensemble plus grand.
  3. Si A et B sont égaux, ajoutez l'élément à la résultat.
  4. Répéter les étapes 1 à 4 sur des sous-ensembles non vides de chaque côté des éléments A et 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 



 / **
* Sonde binaire: choisissez l'élément suivant en choisissant le point à mi-chemin entre bas et haut
* /
template 
struct binary_probe
{
  opérateur RandomAccessIterator () (RandomAccessIterator début, fin RandomAccessIterator, const T & valeur)
  {
    retour début + ((fin - commencer) >> 1);
  }
}; 



 / **
* Lower_bound: comme le lower_bound de stl mais avec différents types de sondage
* Noter l'apparition du modèle de paramètre rare modèle!
* /
template 
RandomAccessIterator lower_bound (RandomAccessIterator début, fin RandomAccessIterator, const T & valeur)
{
  fosse RandomAccessIterator;
  Sonde  pfunc; // sonde foncteur (veut se func'd vers le haut) 



 while (début 


 / *
* Cette fois avec un comparateur!
* /
template 
RandomAccessIterator lower_bound (RandomAccessIterator début, fin RandomAccessIterator, const T & valeur, cmp Comparator)
{
  fosse RandomAccessIterator;
  Sonde  pfunc; 



 while (début

Puisque vous utilisez Visual Studio vous devriez vérifier si vous avez mis à 1 _SECURE_SCL (généralement si vous n'avez pas défini explicitement ce sera 1). S'il est réglé tous STL code sera vérifiée gamme, même dans la version-construit. Typiquement, le ralentissement du code par un 10 à 15%.

Il semble Microsoft ne savait pas que, par exemple std :: vecteur a déjà une interface si vous voulez que la plage vérification: std :: vector :: à ()

(Désolé, a dû obtenir ma poitrine).

En tout cas l'inefficacité principale est que vous copiez les conteneurs au lieu de les passer par valeur. Utiliser des références à (essayer de) comparer des pommes et des pommes au lieu des pommes et des bananes.

Je sais que votre solution fonctionne très bien, mais avez-vous essayé d'utiliser les implémentations STL:

Il pourrait être optimisé pour votre plataform déjà, donc je lui donnerais un coup de feu

sont les drapeaux d'optimisation de C activée?

Ok, après de nombreux commentaires, j'ai mis à jour la question d'origine à plusieurs reprises :

  • Les tests sont désormais exécutés chacun 1 000 fois
  • Le code C# utilise désormais un timer de résolution plus élevée
  • Les structures de données sont désormais renseignées AVANT les tests

Le résultat jusqu’à présent est que C# est toujours environ 5 fois plus rapide que C++.

Merci à tous pour vos idées/suggestions.

Mise à jour:

Je modifié le code set_intersection d'utiliser des vecteurs, et de les trier (au lieu d'utiliser la classe ensemble trié), et il est beaucoup plus rapide maintenant: 

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

Gardez à l'esprit. Le plus grand ensemble est créé triée, si le tri pourrait ne pas prendre beaucoup de temps dans cet exemple

Le code C de: 

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

Vous passez toujours les vecteurs par valeur. Ce qui serait correct si vous ne les copier aussi bien.

introducteur n'a pas été Puting les valeurs à la fin du vecteur, où est-il rapide. Il ne fait que le premier insert après qu'il a inséré la valeur au début du tableau (où fin utilisé pour pointer).

vous où regardant la valeur deux fois dans la version de la carte de hachage, lorsque vous mis à jour la valeur. Pourquoi cet événement est de valeur mise à jour?

exécuter ce code et d'afficher vos horaires. 

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

Dernière référence: 

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

Je pense que la 504 - 495 différence se produit parce qu'il ya des valeurs Dupe couple

. 
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;
}
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top