I've used HashSet and Dictionary a lot in C#, and found them very fast...
I've tried using std::map and std::hash_map and am finding them very slow in comparision. Does this sound like expected behaviour? Is there something I might be doing wrong in my use of std::hash_map?
Or, is there a better C++ Hash container out there?
I'm hashing int32s, usually around 100,000 of them.
Update: I created a repro in C# and C++. It runs two trials, they take 19ms and 13ms in C#, and about 11,000ms in C++. There must be something really wrong with my C++ code :)
(Both were run as Release builds, both are Console apps)
C# Output:
Found 511 values in the intersection, in 19 ms
Found 508 values in the intersection, in 13 ms
C++ Output:
Found 308 values in the intersection, in 11764.7ms
Found 316 values in the intersection, in 11742.8ms
C++ Output (using stdext::hash_map instead of std::map)
Found 300 values in the intersection, in 383.552ms
Found 306 values in the intersection, in 2277.02ms
C++ Output (using stdext::hash_map, a release x64 build)
Found 292 values in the intersection, in 1037.67ms
Found 302 values in the intersection, in 3663.71ms
Notes:
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;
}
For searching a particular value, with std::set and std::map it takes O(log N) time, while with the other two it takes O(N) time; So, std::set or std::map are probably better. Since you have access to C++0x, you could also use std::unordered_set or std::unordered_map which take constant time on average.
CTL is a fast compiling, type safe, header only, template-like container library for ISO C99/C11.
(And std::stack is always 50% faster than std::stack<T, vector<T>> .)
The time complexity for the insertion of a new element is O(log N). Vector is faster for insertion and deletion of elements at the end of the container. Set is faster for insertion and deletion of elements at the middle of the container.
Hash_map and hash_set are non-standard, unordered_map and unordered_set are the most likely soon to be standard versions. Without having a reproducer, I don't think this is going to get far though. Under the hood, they are the same data structures, so they should have similar performance.
I compiled the provided sample under MS Visual Studio 2008 v9.0.30729.1, as Visual C++ -> Win32 -> Console Application (though I rolled my own Timer class because I wasn't sure what you were using). Under debug, I got times of 1000 ms, but compiling under release was 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;
}
(I would try with unordered_map but my version doesn't have it). I suspect there is some problem in your setup for C++.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With