J'ai beaucoup utilisé HashSet et Dictionary en C#, et je les ai trouvés très rapidement ...Conteneur C++ rapide comme le C# HashSet <T> et le Dictionnaire <K,V>?
J'ai essayé d'utiliser std :: map et std :: hash_map et je les trouve très lents en comparaison. Est-ce que cela ressemble à un comportement attendu? Y a-t-il quelque chose que je puisse faire de mal dans mon utilisation de std :: hash_map?
Ou, y a-t-il un meilleur conteneur C++ Hash?
Je suis hash int32s, généralement autour de 100 000 d'entre eux.
Mise à jour: J'ai créé un repro en C# et C++. Il court 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é exécutés comme builds 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
de sortie de C:
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 :: map)
Found 300 values in the intersection, in 383.552ms
Found 306 values in the intersection, in 2277.02ms
C++ sortie (en utilisant stdext :: hash_map, une version build 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 à se croisent partiellement non
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;
}
Pourriez-vous fournir quelques repères? –
Ce qui prend peut-être 10 ms en C# semble prendre 1000ms en C++. Je vais essayer de faire une comparaison plus contrôlée demain, peut-être du code postal pour chaque C# et C++. –
J'ai posté quelques benchmarks. –