Intersection rapide des ensembles: C ++ vs c #

Il peut aussi valoir la peine d'envisager le boost Set disjoint conteneur, qui est spécialement optimisé pour certains types d'opérations définies grandes.

Il fonctionne en traitant un groupe d'ensembles en tant que syndicats de plusieurs ensembles disjoints, permettant de construire d'autres ensembles, tels que des intersections ou des syndicats très à moindre coût, une fois que l'ensemble initial des ensembles disjoints est construit. Si vous prévoyez de faire beaucoup d'opérations définies sur des ensembles qui ne changent pas beaucoup, vous pouvez probablement vous attendre à ce que cela soit très rapide. Si, d'autre part, vous utiliserez chaque ensemble une fois et je vais le jeter, cela ne va probablement pas faire trop.

Quoi qu'il en soit, vous vous feriez de votre faveur pour expérimenter au moins cela pour voir si cela vous donne une bosse dans votre cas spécifique.

Vous passez toujours la valeur des vecteurs. Ce qui serait bien si vous ne les copiez pas aussi.

Inserteur ne mettait pas les valeurs à la fin du vecteur où est-il rapide. Cela n'a fait que cela sur le premier insert après cela, il a inséré la valeur au début de la matrice (où l'extrémité utilisée pour pointer). P>

Vous où recherchez la valeur deux fois dans la version de la carte de hachage, lorsque vous mis à jour la valeur. Pourquoi cette mission de valeur est-elle mise à jour? P>

Exécutez ce code et publiez vos horaires. P>

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

Dernier référence:

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

Au fait, si vous avez de grands ensembles triés STD :: Set_InterSection 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 peuvent être plus rapides. Pour les petits m, Baeza-Yates est O (m * journal (n)), tandis que pour n = alpha * m il est O (n). L'idée de base est de faire une sorte de recherche binaire à 2 voies.

http://citeeerx.ist.psu.edu/viewdoc/download?di=10.1.91.7899&rep=rep1&type=pdf

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

ou

r. Baeza-Yates. Un algorithme d'intersection réglé rapide pour les séquences triées. Dans Procédure du 15e symposium annuel sur la correspondance des motifs combinatoires (CPM 2004), Springer LNCS 3109, PP 400-408, Istanbul, Turquie, juillet 2004.

ci-dessous est une explication et une mise en œuvre d'Erik Frey où il présente des résultats significativement plus rapides que STD :: Set_InterSection avec une sonde binaire. Je n'ai pas encore essayé son code. de
http://fawx.com/

1. Choisissez l'élément médian, A, dans le ensemble plus petit.
2. recherche de son élément d'insertion-position, B, dans le plus grand ensemble.
3. Si A et B sont égaux, appendez l'élément à la résultat.
4. Répétez les étapes 1 à 4 sur des sous-ensembles non vides de chaque côté des éléments A et B.

   ;

   xxx