if-else或switch-case的最快替代品

Question

我有以下定义:

typedef enum
{
    def   = 0,
    m1    = 1,
    m2    = 2,
    m3    = 4,
    m4    = 6,
    m5    = 17,
    m6    = 33,
    m7    = 41,
    m8    = 47,
    m9    = 50,
    m10   = 51,
    m11   = 58,
    m12   = 89,
    m13   = 132,
    m14   = 135
} my_enums;

我正在寻找一种最快的方法来检查函数的参数是否属于其中一个值m1..m14.显而易见的实现是if(p == m1 || p == m2 ...)或switch-case alternative.

有更快的东西吗？m1~m14的值是固定的,不能在连续的范围内.

谢谢.

Answer 1

我能想到的最快的是从0到135的字节数组.如果该项是您的有效枚举之一,则将值设置为1,如果不是,则将值设置为0.然后你可以写:

if (valuesArray[x])
    YahooItsGood();

当然,如果您的范围很大,这不起作用.

如果传入的值可能超出该范围,那么您将需要更多逻辑:

if (x >= 0 && x < 136 && valuesArray[x])
    YahooItsGood();

当然,每个项目实际上只需要一个位,因此可以使用大小为1/8的数组来节省大量内存.测试值的逻辑变得更加复杂,但它仍然比一系列if/else或二进制搜索更快.

如果你有一个更大的集合,那么你可能想要构建一个哈希表.它不会像直接查找那么快,但是当值范围大得多时,它会使用更少的内存.

Answer 2

switch语句是更好的选择.它有助于了解编译器可以使用的技巧使switch语句非常优化(在大多数情况下).很多时候,比你自己想出的更好.

如果值是非连续的,则编译器可以求助于具有O(log(n))性能的静态二进制决策树.对于连续值列表,它将构造一个跳转表,即O(1).相比之下,if-else结构是O(n).

我建议你在使用其他方法之前完全理解你可以从switch语句中得到什么.