pourquoi est-set_intersection en LIST si lent?

Question

J'intersection un ensemble de 100.000 numéros et un ensemble de 1000 numéros à l'aide set_intersection en LIST et ses prise 21s, où il prend 11ms en C #.

Le code C de:

int runIntersectionTestAlgo()
{   

    set<int> set1;
    set<int> set2;
    set<int> intersection;


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

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

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

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

    return intersection.size(); 
}

C # Code:

static int runIntersectionTest()
    {
        Random random = new Random(DateTime.Now.Millisecond);

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

        List<int> set1 = new List<int>();
        List<int> set2 = new List<int>();

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

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

            // Now intersect the two sets by populating the map
        foreach( int value in set1 )
            {
                theMap[value] = 1;
            }

            int intersectionSize = 0;

        foreach ( int value in set2 )
        {
            int count;
            if ( theMap.TryGetValue(value, out count ) )
            {
                intersectionSize++;
                theMap[value] = 2;
            }
            }

            return intersectionSize;
    }
}

Answer 1

Sur cet ancien Pentium 4 3GHz, je reçois 2734 millisecondes pour l'ensemble de la fonction runIntersectionTestAlgo, dans une mise au point de construire avec des optimisations désactivées. Je compilé avec VS2008 SP1.

Si j'activer les optimisations, je reçois 93 millisecondes.

Voici mon code:

#include <set>
#include <algorithm>

using namespace std;

int runIntersectionTestAlgo()
{   

    set<int> set1;
    set<int> set2;
    set<int> intersection;


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

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

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

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

    return intersection.size(); 
}

#include <windows.h>
#include <iostream>

int main(){
    DWORD start = GetTickCount();

    runIntersectionTestAlgo();

    DWORD span = GetTickCount() - start;

    std::cout << span << " milliseconds\n";
}

La désactivation fait aucune différence _SECURE_SCL pour la construction de la libération, qui planait toujours autour des 100 ms.

GetTickCount n'est pas idéal, bien sûr, mais il devrait être assez bon pour distinguer 21 secondes de moins de 100 millisecondes.

Je conclus donc qu'il ya quelque chose de mal avec vos repères.

Answer 2

Un couple de choses feraient vos deux exemples plus comparables.

D'abord, votre exemple STL n'est pas tout à fait raison, d'une part les deux ensembles devraient être classés dans l'ordre croissant (en STL parler une « stricte de commande faible »).

En second lieu, à l'aide de vos « ensembles » qui sont mises en œuvre comme des arbres en STL, par rapport aux « listes » qui sont des listes liées. inserts aléatoires dans un jeu est plus cher que l'insertion sur la fin d'une liste.

Essayez d'utiliser une liste de ints dans l'exemple C et de trier les première liste (inersection indication contraire ne fonctionnera pas correctement) et je pense que vous verrez les résultats plus favorables.

Answer 3

J'ai couru votre code C ++ sur mon linux

$ time ./test

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

21s signifie pour moi vous compilez sans optimisations. Si vous utilisez MSVC vérifiez que vous avez énumérés  _SECURE_SCL=0 (voir msdn) dans le compiler les définitions. Sinon toutes les opérations STL iterator sont chien lent.

Answer 4

Je mis à jour votre exemple d'utiliser un code de minuterie que j'utilise lors des tests unitaires. Sur ma machine, je reçois les horaires suivants (sur la base -O3):

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

Sur cette base, si je lis mes décimales correctement, il faut « 4ms » pour insérer les éléments dans le premier set, 50 microsecondes pour insérer les éléments dans le deuxième set et un tiers d'un ms pour effectuer l'intersection.

Je ne peux pas exécuter votre exemple C # sur ma machine, donc je ne peux pas comparer le moment, mais il est certainement pas 21 ans que vous publiez.

Answer 5

Votre C # et le travail de code C différemment. Le code C # utilise des tours de hachage magiques pour la vitesse, votre code C ++ utilise des tours d'arbres pour la vitesse. Une chose qui va accélérer les choses sans doute (en ignorant le fait que votre test semble être rompu) serait d'utiliser le hachage, comme suit:

1. Créer une d'une des hash_map deux collections.
2. itérer sur chaque élément dans la 2ème collection. Si le `hash_map1 contient cet élément, l'ajouter à votre résultat.