Быстрый C ++ контейнер, такой как C # HashSet <T> и Dictionary <K, V>?

Я много использовал HashSet и Dictionary в C # и нашел их очень быстро ...

Я пытался использовать std :: map и std :: hash_map, и сравнивал их очень медленно. Похоже ли это на ожидаемое поведение? Есть ли что-то, что я могу делать неправильно при использовании std :: hash_map?

Или есть лучший C ++ Hash-контейнер?

Я хеширую int32, обычно около 100 000 из них.

Обновление: я создал репродукцию в C # и C ++. Он запускает два испытания, они занимают 19 мс и 13 мс в C # и около 11 000 мс в C ++. Должно быть что-то действительно не так с моим кодом C ++ :)

(Оба были запущены как сборки Release, оба являются консольными приложениями)

Выход C #:

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

Выход C ++:

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

Вывод C ++ (используя stdext :: hash_map вместо std :: map)

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

Вывод C ++ (с использованием stdext :: hash_map, выпуск x64 build)

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

Заметки:

Set2 is not getting populated quite as I wanted in C++, I was expecting it to have a 50% intersection with Set1 (as it does in C#), but I had to multiply my random number by 10 for some reason to even get them to partially not intersect

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>
 Alex Black29 июн. 2009 г., 04:52
Что, возможно, занимает 10 мс в C #, кажется, занимает 1000 мс в C ++. Завтра я попытаюсь сделать более контролируемое сравнение, возможно, напишу код для каждого C # и C ++.
 Alex Black29 июн. 2009 г., 15:40
Я опубликовал несколько тестов.
 Alex Black30 июн. 2009 г., 04:40
@ Дэвид: Спасибо, что поделились. Нам удалось разобраться в этом, см .: / Stackoverflow.com вопросы / 1060337 / .... Что происходит, когда вы подключаете отладчик, используется другая (DEBUG) куча памяти - вы можете отключить ее, если хотите.
 Todd Gardner29 июн. 2009 г., 04:49
Не могли бы вы дать некоторые критерии?
 David Seiler30 июн. 2009 г., 04:32
@ Alex: Хотя я недостаточно знаком с внутренними компонентами Visual Studio, чтобы быть конкретными, похоже, проблема в инструментах, которые добавляет отладчик, а не в коде, сгенерированном компилятором. Фактор замедления 100, безусловно, ошибка; доложите об этом

Ответы на вопрос(6)

: map в своем коде C ++, который имеет время вставки и поиска O (log (n)). Попробуйте провести тестирование с помощью hash_map, чтобы получить лучшее сравнение.

 Alex Black29 июн. 2009 г., 15:46
Я переключил std :: map для stdext :: hash_map и получил НАИБОЛЕЕ лучшие результаты, но все еще ужасный по сравнению с C #. Найдено 300 значений на перекрестке, за 383,552 мс. Найдено 306 значений на перекрестке, за 2277,02 м
Решение Вопроса

Unordered_map а также Unordered_set скорее всего скоро будут стандартными версиями. Не имея репродуктора, я не думаю, что это далеко продвинется. Под капотом у них одинаковые структуры данных, поэтому они должны иметь одинаковую производительность.

Я скомпилировал предоставленный пример в MS Visual Studio 2008 v9.0.30729.1, как Visual C ++ -> Win32 -> Консольное приложение (хотя я выбрал свой собственный класс Timer, потому что я не был уверен, что вы используете). При отладке я получил время 1000 мс, но компиляция при выпуске была 50 м

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

(Я бы попробовал с unordered_map, но в моей версии его нет). Я подозреваю, что в вашей настройке для C ++ есть какая-то проблема.

 GManNickG29 июн. 2009 г., 07:45
Примечание: Boost предлагает реализацию обоих.
 Alex Black29 июн. 2009 г., 22:24
Я кое-что понял: если я присоединяю отладчик к сборкам RELEASE или DEBUG (например, нажимаю F5 в IDE), то у меня ужасные времена.

Почему мой код STL работает так медленно, когда у меня подключен отладчик / IDE?

Что происходит, когда вы присоединяете отладчик, используется другая (DEBUG) куча памяти - вы можете отключить ее, если хотите.

но вам нужно собрать больше деталей, прежде чем мы действительно сможем помочь. Чью реализацию hash_map вы используете? Вы указали на него профилировщиком, и если да, что он вам сказал?

В общем, если реализация хеш-таблицы работает плохо по непонятной причине, обычно это потому, что хеш-функция, используемая таблицей, работает плохо для вашего конкретного ввода. Это может быть вашей проблемой - в hash_map C ++ используется хеш-функция, которая отображает ваши ключи в небольшой диапазон блоков, а в C # HashSet нет - или это может быть что-то совершенно иное.

std :: map обычно реализован в виде дерева и поэтому будет иметь разные характеристики производительности. Опять же, детали реализации и входные данные имеют значение.

 Alex Black29 июн. 2009 г., 15:39
пример кода опубликован.
 David Seiler29 июн. 2009 г., 05:00
Команда VC ++ очень хорошо разбирается в подобных вещах IME, что заставляет меня думать, что это менее вероятно, будет проблема с хэш-функцией. Я рассмотрю проблему более подробно после того, как вы опубликуете пример кода завтра.
 Alex Black29 июн. 2009 г., 04:54
Когда я использовал hash_map, я полагаю, что использовал Microsoft ... Я просто запустил VS 2008 и набрал #include <hash_map>. Любые советы по хорошей хэш-функции с hash_map для чисел Int32? Я займусь поиском.

Google Sparcehash может подойти

C # набор хэшей, который равен O (1), что означает почти постоянный и независимый от размера ввода,

versus C ++ vector .... значение (размер входных данных) умноженное на константу ...

В этом мало практического смысла.

Вы должны попытаться использовать эквивалент хэш-набора в C ++, который (я думаю, после tr1 в 2007 году) std :: tr1 :: unordered_set <...> (и std :: tr1 :: unordered_set <...>)

Wikipedia ссылка на TR1

Также обратите внимание, что согласноэта страниц Visual Studio имеет собственную субоптимальную реализацию stl tr1. (не имею личного опыта, нашел егоВо)

Ваш ответ на вопрос