Rapide conteneur C ++ comme le C # HashSet et Dictionnaire ?

StackOverflow https://stackoverflow.com/questions/1056366

  •  20-08-2019
  •  | 
  •  

Question

Je l'ai utilisé HashSet et Dictionnaire beaucoup en C #, et les ai trouvés très vite ...

Je l'ai essayé d'utiliser std :: carte et std :: hash_map et je les trouver très lent en comparaison. Est-ce son comme comportement attendu? Y at-il quelque chose que je pourrais faire mal dans mon utilisation de std :: hash_map?

Ou, est-il un meilleur C ++ contenant Hash là-bas?

Je hachant INT32, généralement autour de 100 000 d'entre eux.

Mise à jour: J'ai créé un repro en C # et C ++. Il gère deux essais, ils prennent 19ms et 13ms en C #, et environ 11,000ms en C ++. Il doit y avoir quelque chose de vraiment mal avec mon code C ++:)

(Les deux ont été exploités comme construit de presse, les deux sont des applications de la console)

C # Sortie: 

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

La sortie C de: 

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

Sortie C ++ (en utilisant stdext :: hash_map au lieu de std :: carte) 

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

La sortie C de (en utilisant stdext :: hash_map, une libération de construction x64) 

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

Notes:

  • Set2 ne reçoit pas rempli tout à fait comme je le voulais en C ++, je l'attendais d'avoir une intersection de 50% avec Set1 (comme il le fait en C #), mais je devais multiplier mon nombre aléatoire de 10 pour une raison quelconque, même les amener à ne pas en partie recouper

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;
}
Était-ce utile?

La solution

hash_map et hash_set ne sont pas standard, unordered_map et < a href = "http://msdn.microsoft.com/en-us/library/bb982739.aspx" rel = "nofollow noreferrer"> unordered_set sont les plus susceptibles d'être bientôt des versions standard. Sans avoir un reproducer, je ne pense pas que cela va aller bien loin cependant. Sous le capot, ils sont les mêmes structures de données, de sorte qu'ils devraient avoir des performances similaires.

Je compilé l'échantillon fourni sous MS Visual Studio 2008 v9.0.30729.1, comme Visual C ++ -> Win32 -> Application console (si je roulais ma propre classe Timer parce que je ne sais pas ce que vous utilisiez). Sous debug, je suis temps de 1000 ms, mais la compilation en liberté est de 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;
}

(je voudrais essayer de unordered_map mais ma version ne pas l'avoir). Je pense qu'il ya un problème dans la configuration C ++.

Autres conseils

Nous avons réussi à aller au fond de ce sujet, voir:

Pourquoi mon code STL fonctionner si lentement quand je le débogueur / IDE attaché

Qu'est-ce qui se passe est lorsque vous connectez le débogueur un autre (debug) tas de mémoire est utilisée - vous pouvez le désactiver si vous voulez.

Il ne semble pas prévu, mais vous aurez besoin de recueillir quelques détails avant de pouvoir vraiment aider. Dont la mise en œuvre hash_map utilisez-vous? Est-ce que vous pointez un profileur à elle, et si oui qu'est-ce qu'il vous a dit?

En général, si une implémentation de table de hachage est peu performant sans raison évidente, il est généralement parce que la fonction de hachage que la table utilise mal arrive à effectuer pour votre entrée particulière. Cela pourrait être votre problème - le C ++ hash_map arrive d'utiliser une fonction de hachage qui associe vos clés à une petite gamme de godets et le C # HashSet ne fonctionne pas -. Ou il pourrait être tout autre chose

std :: carte est généralement mis en œuvre comme un arbre, et aura ainsi des caractéristiques de performance. Encore une fois, les détails de la question des données de mise en œuvre et l'entrée.

Je ne ai jamais utilisé, mais Google Sparcehash peut être un bon ajustement

Vous utilisez std :: carte dans votre code C ++, qui a des temps d'insertion et de consultation de O (log (n)). Essayez de tester avec hash_map pour obtenir une meilleure comparaison.

Ce que vous comparez vraiment est

Set C # de hachage qui est O (1), ce qui signifie pratiquement constant et indépendant de la taille d'entrée,

par rapport à C ++ vecteur .... signification (taille de l'entrée) constante fois ...

Cela fait peu de sens pratique.

Vous devriez essayer d'utiliser l'équivalent de HashSet en C ++ qui est (après TR1 en 2007 je pense) std :: tr1 :: unordered_set <...> (et std :: tr1 :: unordered_set <...>)

wikipedia lien sur TR1

A noter également que, selon cette page Visual Studio a leur propre implémentation de TR1 stl suboptimale. (Sans expérience personnelle, trouvé )

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top