Warum ist set_intersection in STL so langsam?

Question

Ich überschneide eine Reihe von 100.000 Zahlen und eine Menge von 1.000 Zahlen mit set_intersection in STL und seine Einnahme von 21s, wo es 11ms in C# dauert.

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

Auf diesem alten 3GHz Pentium 4, bekomme ich 2734 Millisekunden für die gesamte runIntersectionTestAlgo Funktion, in einem Debug-Build mit deaktivierten Optimierungen. Ich habe mit VS2008 SP1 kompiliert.

Wenn ich Optimierungen aktivieren, bekomme ich 93 Millisekunden.

Hier ist mein 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"; 
} 

Deaktivieren _SECURE_SCL keinen Unterschied für die Release-Build gemacht, die um die 100 ms schwebte noch.

GetTickCount ist natürlich nicht ideal, aber es sollte gut genug sein, um 21 Sekunden von weniger als 100 Millisekunden zu unterscheiden.

Also ich schließe, dass etwas mit Ihren Benchmarks nicht stimmt.

Answer 2

Ein paar Dinge, würde Ihre zwei Beispiele besser vergleichbar machen.

Zuerst ist Ihr Beispiel in STL nicht ganz richtig, für eine Sache sollten beide Sätze in aufsteigender Reihenfolge sortiert werden (in STL spricht eine "strenge schwache Ordnung").

Zweitens, verwenden Sie "Sets", die als Bäume in STL implementiert sind, vs. "Listen", die verknüpfte Listen sind. Zufällige Einfügungen in ein Set sind teurer als das Einfügen am Ende einer Liste.

Versuchen Sie es mit einer Liste von Ints im C++ - Beispiel und sortieren Sie auch die Liste zuerst (ansonsten wird die Inersektion nicht richtig funktionieren) und ich denke, Sie werden bessere Ergebnisse sehen.

Answer 3

lief ich Ihre C++ Code auf meinem Linux-Box

$ time ./test 

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

21s mir bedeutet, dass Sie ohne Optimierungen zusammengestellt. Wenn Sie MSVC verwenden, stellen Sie sicher, dass Sie _SECURE_SCL=0 (siehe msdn) in den Kompilierdefinitionen aufgelistet haben. Ansonsten sind alle STL-Iterator-Operationen langsam.

Answer 4

Ich habe Ihr Beispiel aktualisiert, um einen Timercode zu verwenden, den ich beim Komponententest verwende. Auf meinem Rechner bekomme ich die folgenden Timings (basierend auf O3):

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

auf dieser Grundlage, wenn ich meine Dezimalstellen richtig gerade lese, ist es 4ms 'nimmt die Elemente in den ersten Satz einzufügen, 50 Mikrosekunden zum Einfügen der Elemente in den zweiten Satz und 1/3 ms zum Ausführen der Schnittmenge.

Ich kann Ihr C# -Beispiel nicht auf meinem Computer ausführen, daher kann ich das Timing nicht vergleichen, aber es sind definitiv keine 21s, wie Sie schreiben.

Answer 5

Ihr C# - und C++ - Code funktioniert anders. Der C# -Code verwendet magische Hashing-Tricks für Geschwindigkeit, Ihr C++ - Code verwendet Baumtricks für Geschwindigkeit.Eine Sache, die wahrscheinlich die Dinge beschleunigen wird bis (ohne Berücksichtigung der Tatsache, dass Ihre Tests scheint gebrochen zu werden) wäre Hashing verwendet wird, wie folgt:

1. erstellen hash_map von einem der beiden Sammlungen.
2. Iterieren über jedes Element in der 2. Sammlung. Wenn die `hash_map1 dieses Element enthält, fügen Sie es zu Ihrem Ergebnis hinzu.