C++:什么更快 - 在 hashmap 或 switch 语句中查找?
我有一个将一个整数转换为另一个整数的代码模式.就像这样:
I have a code pattern which translates one integer to another. Just like this:
int t(int value) {
switch (value) {
case 1: return const_1;
case 3: return const_2;
case 4: return const_3;
case 8: return const_4;
default: return 0;
}
}
目前大约有 50 个条目，以后可能会有更多，但可能不会超过一百或两个.所有的值都是预定义的，当然我可以按它们的值排序 case 标签.所以问题是，什么会更快 - 这种方法或将其放入哈希映射(我无法访问 std::map，所以我在谈论我的 SDK 中可用的自定义哈希映射)并在该表中执行查找?不过，也许这有点过早的优化......但我只需要你的意见.
It has about 50 entries currently, maybe later on there will be some more, but probably no more than hundred or two. All the values are predefined, and of course I can order case labels by their values. So the question is, what will be faster - this approach or put this into hash map (I have no access to std::map, so I'm speaking about custom hash map available in my SDK) and perform lookups in that table? Maybe it's a bit of premature optimization, though... But I just need your opinions.
提前致谢.
编辑:我的案例值将在 0 到 0xffff 的范围内.以及关于哈希映射更好可读性的点.我不确定它是否真的具有更好的可读性，因为我仍然需要用值填充它，所以我的代码中仍然需要有一张常量映射表.
EDIT: My case values are going to be in range from 0 to 0xffff. And regarding the point of better readability of hash map. I'm not sure it really will have better readability, because I still need to populate it with values, so that sheet of constants mapping is still needs to be somewhere in my code.
EDIT-2:已经给出了许多有用的答案，非常感谢.我想在这里添加一些信息.我的散列键是整数，而我的整数散列函数基本上只是一个整数溢出的乘法:
EDIT-2: Many useful answers were already given, much thanks. I'd like to add some info here. My hash key is integer, and my hash function for integer is basically just one multiplication with integral overflow:
EXPORT_C __NAKED__ unsigned int DefaultHash::Integer(const int& /*aInt*/)
{
_asm mov edx, [esp+4]
_asm mov eax, 9E3779B9h
_asm mul dword ptr [edx]
_asm ret
}
所以应该很快.
推荐答案
switch 构造更快(或至少不慢).
A switch construct is faster (or at least not slower).
这主要是因为 switch 构造向编译器提供静态数据，而像哈希映射这样的运行时结构却没有.
That's mostly because a switch construct gives static data to the compiler, while a runtime structure like a hash map doesn't.
在可能的情况下，编译器应该将 switch 构造编译为代码指针数组:数组的每个项目(由您的索引索引)都指向相关的代码.在运行时，这需要 O(1)，而哈希映射可能需要更多:平均情况下为 O(log n)，最坏情况下为 O(n)，通常情况下，无论如何，内存访问的常数数量更大.
When possible compilers should compile switch constructs into array of code pointers: each item of the array (indexed by your indexes) points to the associated code. At runtime this takes O(1), while a hash map could take more: O(log n) at average case or O(n) at worst case, usually, and anyway a bigger constant number of memory accesses.
相关文章