C ++:什么是更快的-在hashmap或switch语句中查找? [英] C++: What is faster - lookup in hashmap or switch statement?

问题描述

我有一个代码模式，可以将一个整数转换为另一个整数.就是这样:

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个条目，也许以后还会有更多，但可能不超过一百或两个.所有的值都是预定义的，当然我可以按它们的值对案例标签进行排序.所以问题是，什么会更快-这种方法还是将其放入哈希映射(我无法访问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.

这篇关于C ++:什么是更快的-在hashmap或switch语句中查找?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！