Ich habe HashSet und Dictionary häufig in C # verwendet und sie sehr schnell gefunden ...

Ich habe versucht, std :: map und std :: hash_map zu verwenden und finde sie im Vergleich sehr langsam. Klingt dies wie erwartetes Verhalten? Gibt es etwas, was ich bei der Verwendung von std :: hash_map falsch machen könnte?

Oder gibt es da draußen einen besseren C ++ - Hash-Container?

Ich hasche int32s, normalerweise ungefähr 100.000 davon.

Update: Ich habe eine Reproduktion in C # und C ++ erstellt. Es werden zwei Versuche ausgeführt, die in C # 19 ms und 13 ms und in C ++ etwa 11.000 ms dauern. Es muss etwas wirklich falsch mit meinem C ++ - Code sein :)

(Beide wurden als Release-Builds ausgeführt, beide sind Konsolen-Apps)

C # Ausgabe:

<code>Found 511 values in the intersection, in 19 ms
Found 508 values in the intersection, in 13 ms
</code>

C ++ Ausgabe:

<code>Found 308 values in the intersection, in 11764.7ms
Found 316 values in the intersection, in 11742.8ms
</code>

C ++ - Ausgabe (mit stdext :: hash_map anstelle von std :: map)

<code>Found 300 values in the intersection, in 383.552ms
Found 306 values in the intersection, in 2277.02ms
</code>

C ++ - Ausgabe (mit stdext :: hash_map, einem Release x64-Build)

<code>Found 292 values in the intersection, in 1037.67ms
Found 302 values in the intersection, in 3663.71ms
</code>

Anmerkungen:

Set2 wird nicht so gefüllt, wie ich es in C ++ wollte. Ich hatte erwartet, dass es einen Schnittpunkt von 50% mit Set1 hat (wie es in C # der Fall ist), aber ich musste meine Zufallszahl aus irgendeinem Grund mit 10 multiplizieren, um sie überhaupt zu erhalten teilweise nicht schneiden

C #:

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

C ++:

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