Быстрый контейнер C++ как C# HashSet <T> и Словарь <K, V>?
Проще говоря: P Если безопасно выполнить несколько потоков в блоке кода, это потокобезопасно *
* применяются условия
Условия упоминаются другими ответами, такими как 1. Результат должен быть таким же, если вы выполняете один поток или несколько потоков над ним и т. Д.
5 ответов
Hash_map и hash_set нестандартны, 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 ++ возникла проблема.
Звучит неожиданно, но вам нужно собрать больше деталей, прежде чем мы действительно сможем помочь. Чью реализацию hash_map вы используете? Вы указали на него профилировщик, и если да, то что он вам сказал?
В общем, если реализация хеш-таблицы работает плохо без очевидной причины, обычно это связано с тем, что хеш-функция, которую использует таблица, выполняет плохо для вашего конкретного входа. Это может быть вашей проблемой - C ++ hash_map использует хэш-функцию, которая сопоставляет ваши ключи с небольшим диапазоном сегментов, а C # HashSet - нет - или это может быть что-то совершенно другое.
std :: map обычно реализован в виде дерева, поэтому будет иметь разные характеристики производительности. Опять же, важны детали реализации и входные данные.
Я никогда не использовал его, но Google Sparcehash может подойти
Вы используете std :: map в своем коде C ++, для которого время вставки и поиска равно O (log (n)). Попробуйте протестировать с помощью hash_map, чтобы получить лучшее сравнение.
Нам удалось разобраться в этом, см.:
Почему мой код STL работает так медленно, когда у меня подключен отладчик / IDE?
Что происходит когда вы подключаете отладчик, используется другая куча памяти (DEBUG) - вы можете отключить ее, если хотите.