Contenitore C++ veloce come C# HashSet <T> e Dizionario <K,V>?

Question

Ho usato HashSet e Dizionario molto in C#, e li ho trovati molto veloce ...

Ho provato con std :: map e std :: hash_map e li sto trovando molto lenta in confronto. Questo suona come un comportamento previsto? C'è qualcosa che potrei sbagliare nel mio uso di std :: hash_map?

Oppure, c'è un contenitore Hash C++ migliore là fuori?

Sono hashing int32s, di solito circa 100.000 di loro.

Aggiornamento: ho creato una replica in C# e C++. Esegue due prove, prendono 19ms e 13ms in C# e circa 11.000ms in C++. Ci deve essere qualcosa di veramente sbagliato con il mio codice C++ :)

(Entrambi sono stati eseguiti come build di rilascio, entrambi sono applicazioni Console)

C# in uscita:

Found 511 values in the intersection, in 19 ms 
Found 508 values in the intersection, in 13 ms 

C++ in uscita:

Found 308 values in the intersection, in 11764.7ms 
Found 316 values in the intersection, in 11742.8ms 

Output C++ (utilizzando stdext :: hash_map invece di std :: map)

Found 300 values in the intersection, in 383.552ms 
Found 306 values in the intersection, in 2277.02ms 

C++ uscita (usando stdext :: hash_map, una build di rilascio x64)

Found 292 values in the intersection, in 1037.67ms 
Found 302 values in the intersection, in 3663.71ms 

Note:

• Set2 non è sempre popolata piuttosto come avrei voluto in C++, mi aspettavo di avere un incrocio al 50% con Set1 (come fa in C#), ma ho dovuto moltiplicare il mio numero a caso del 10 per qualche motivo per ottenere anche loro di parte non si intersecano

C#:

static void Main(string[] args) 
    { 
     int start = DateTime.Now.Millisecond; 
     int intersectionSize = runIntersectionTest(); 
     int duration = DateTime.Now.Millisecond - start; 

     Console.WriteLine(String.Format("Found {0} values in the intersection, in {1} ms", intersectionSize, duration)); 

     start = DateTime.Now.Millisecond; 
     intersectionSize = runIntersectionTest(); 
     duration = DateTime.Now.Millisecond - start; 

     Console.WriteLine(String.Format("Found {0} values in the intersection, in {1} ms", intersectionSize, duration)); 

     Console.ReadKey(); 
    } 

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

C++:

int runIntersectionTest() 
{ 
    std::map<int,int> theMap; 

    vector<int> set1; 
    vector<int> set2; 

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

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

     map<int,int>::iterator foundValue = theMap.find(value); 

     if (foundValue != theMap.end()) 
     { 
      theMap[value] = 2; 

      intersectionSize++; 
     } 
    } 

    return intersectionSize; 

} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    srand (time(NULL)); 

    Timer timer; 
    int intersectionSize = runIntersectionTest(); 
    timer.Stop(); 

    cout << "Found " << intersectionSize << " values in the intersection, in " << timer.GetMilliseconds() << "ms" << endl; 

    timer.Reset(); 
    intersectionSize = runIntersectionTest(); 
    timer.Stop(); 

    cout << "Found " << intersectionSize << " values in the intersection, in " << timer.GetMilliseconds() << "ms" << endl; 

    getchar(); 

    return 0; 
} 

Answer 1

Hash_map e hash_set sono non standard, unordered_map e unordered_set sono probabilmente le versioni standard più presto. Senza avere un riproduttore, non penso che arriverà molto lontano.Sotto il cofano, sono le stesse strutture dati, quindi dovrebbero avere prestazioni simili.

---

ho compilato l'esempio fornito con MS Visual Studio 2008 v9.0.30729.1, come Visual C++ -> Win32 -> applicazione console (anche se ho arrotolato la mia classe Timer perché non ero sicuro di quello che eri usando). Sotto debug, ho avuto tempi di 1000 ms, ma la compilazione in fase di rilascio era di 50 ms.

#include <vector> 
#include <iostream> 
#include <map> 
#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

#include <windows.h> 

typedef struct { 
    LARGE_INTEGER start; 
    LARGE_INTEGER stop; 
} stopWatch; 

class CStopWatch { 

private: 
    stopWatch timer; 
    LARGE_INTEGER frequency; 
    double LIToSecs(LARGE_INTEGER & L); 
public: 
    CStopWatch(); 
    void startTimer(); 
    void stopTimer(); 
    double getElapsedTime(); 
}; 

double CStopWatch::LIToSecs(LARGE_INTEGER & L) { 
    return ((double)L.QuadPart /(double)frequency.QuadPart) ; 
} 

CStopWatch::CStopWatch(){ 
    timer.start.QuadPart=0; 
    timer.stop.QuadPart=0; 
    QueryPerformanceFrequency(&frequency) ; 
} 

void CStopWatch::startTimer() { 
    QueryPerformanceCounter(&timer.start) ; 
} 

void CStopWatch::stopTimer() { 
    QueryPerformanceCounter(&timer.stop) ; 
} 

double CStopWatch::getElapsedTime() { 
    LARGE_INTEGER time; 
    time.QuadPart = timer.stop.QuadPart - timer.start.QuadPart; 
    return LIToSecs(time) ; 
} 

using namespace std; 
int runIntersectionTest() 
{ 
    std::map<int,int> theMap; 

    vector<int> set1; 
    vector<int> set2; 

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

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

     map<int,int>::iterator foundValue = theMap.find(value); 

     if (foundValue != theMap.end()) 
     { 
       theMap[value] = 2; 

       intersectionSize++; 
     } 
    } 

    return intersectionSize; 

} 

int main(int argc, char* argv[]) 
{ 
    srand (time(NULL)); 
    int tests = 2; 
    while(tests--){ 
     CStopWatch timer; 
     timer.startTimer(); 
     int intersectionSize = runIntersectionTest(); 
     timer.stopTimer(); 

     cout << "Found " << intersectionSize << " values in the intersection, in " << timer.getElapsedTime() << "s\r\n"; 
    } 

    getchar(); 

    return 0; 
} 

(Vorrei provare con unordered_map ma la mia versione non ce l'ha). Sospetto che ci sia qualche problema nel tuo setup per C++.

Answer 2

non suona previsto, ma avrete bisogno di raccogliere qualche dettaglio in più prima di poter davvero aiutare. Di chi è l'implementazione di hash_map? Hai indicato un profiler, e se sì cosa ti ha detto?

In generale, se un'implementazione della tabella hash funziona male per nessun motivo ovvio, di solito è perché la funzione di hash utilizzata dalla tabella si comporta male per il vostro input particolare. Questo potrebbe essere il tuo problema - l'hash_map del C++ capita di usare una funzione di hash che mappa le tue chiavi su una piccola gamma di bucket, e il C# HashSet no - o potrebbe essere qualcosa di completamente diverso.

std :: map è generalmente implementato come un albero e quindi avrà caratteristiche di prestazione diverse. Di nuovo, i dettagli dell'implementazione e dei dati di input sono importanti.

Answer 3

non l'ho mai usato, ma Google Sparcehash potrebbe essere una buona misura

Answer 4

Stai usando std :: map nel codice C++, che ha di inserimento e di ricerca tempi di O (log (n)). Prova a provare con hash_map per ottenere un confronto migliore.

Answer 5

Siamo riusciti ad andare a fondo di questo, si veda:

Why does my STL code run so slowly when I have the debugger/IDE attached?

ciò che accade è quando si collega il debugger una diversa (DEBUG) heap di memoria viene utilizzato - è possibile disattivarla se si volere.

Answer 6

Quello che stai veramente confrontando è

C# hash set che è O (1), che significa quasi costante e indipendente dalle dimensioni di ingresso,

contro C++ vettore .... che significa (dimensioni di ingresso) tempi costanti ...

Questo ha poco senso pratico.

Si dovrebbe provare a utilizzare l'equivalente di HashSet in C++ che è (dopo TR1 nel 2007 credo) std :: tr1 :: unordered_set < ...> (e std :: tr1 :: unordered_set < ... >)

wikipedia link on TR1

Si noti inoltre che in base alla this page Visual Studio ha una propria implementazione TR1 non ottimale stl. (non ho esperienza personale, l'ho trovato here)