Pourquoi set_intersection en STL est-il si lent?

Question

Je croise un ensemble de 100 000 nombres et un ensemble de 1 000 nombres en utilisant set_intersection en STL et en prenant 21s, où il faut 11ms en C#.

C++ code:

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, j'obtiens 2734 millisecondes pour l'ensemble de la fonction runIntersectionTestAlgo, dans une version de débogage avec des optimisations désactivées. J'ai compilé avec VS2008 SP1.

Si j'accepte les optimisations, j'obtiens 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"; 
} 

Désactivation _SECURE_SCL fait aucune différence 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. Donc, je conclus qu'il y a quelque chose qui ne va pas avec vos tests de performance.

Answer 2

Un couple de choses feraient vos deux exemples plus comparables. Tout d'abord, votre exemple en STL n'est pas tout à fait correct, d'une part, les deux ensembles doivent être triés par ordre croissant (en STL, on parle d'un "strict weak ordering"). Deuxièmement, vous utilisez des «ensembles» qui sont implémentés comme des arbres dans la liste STL, par opposition aux «listes» qui sont des listes liées. Les insertions aléatoires dans un ensemble sont plus coûteuses que l'insertion à la fin d'une liste. Essayez d'utiliser une liste d'ints dans l'exemple C++ et de trier la liste en premier (sinon l'insertion ne fonctionnera pas correctement) et je pense que vous verrez des résultats plus favorables.

Answer 3

Je 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. Dans le cas où vous utilisez MSVC assurez-vous que vous avez répertorié _SECURE_SCL=0 (voir msdn) dans les définitions de compilation. Sinon, toutes les opérations de l'itérateur STL sont lentes.

Answer 4

J'ai mis à jour votre exemple pour utiliser un code de minuteur 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 » insérer les éléments dans le premier set, 50 microsecondes pour insérer les éléments dans le deuxième ensemble et un tiers de ms pour effectuer l'intersection.

Je ne parviens pas à exécuter votre exemple C# sur ma machine, donc je ne peux pas comparer le timing, mais ce n'est certainement pas 21s lorsque vous postez.

Answer 5

Vos codes C# et C++ fonctionnent différemment. Le code C# utilise des astuces de hachage magiques pour la vitesse, votre code C++ utilise des astuces 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 hash_map de l'une des deux collections.
2. Effectuez une itération sur chaque élément de la deuxième collection. Si hash_map1 contient cet élément, ajoutez-le à votre résultat.