If-else-if与地图

Question

假设我有一个if/else-if链:

if( x.GetId() == 1 )
{
}
else if( x.GetId() == 2 )
{
}
// ... 50 more else if statements

我想知道的是,如果我保留地图,它在性能方面会更好吗？(假设键是整数)

Answer 1

地图(通常)是使用红黑树实现的,当树不断保持平衡时,它会提供O(log N)查找.你的if语句的线性列表将是O(N)最坏的情况.所以,是的,地图的查找速度要快得多.

许多人建议使用switch语句,这可能不会更快,具体取决于您的实际if语句.编译器有时可以通过使用跳转表来优化切换,跳转表是O(1),但这仅适用于未定义标准的值; 因此,这种行为可能有点不确定.虽然有一篇很棒的文章,其中有一些关于优化switch语句的技巧,这里有优化C和C++代码.

从技术上讲,你甚至可以手动制定一个平衡的树,这最适合静态数据,我刚刚创建了一个函数来快速找到一个字节中设置的位(这是在I/O引脚中断的嵌入式应用程序中使用的)并且必须快速,99%的时间只在字节中设置1位):

unsigned char single_bit_index(unsigned char bit) {
    // Hard-coded balanced tree lookup
    if(bit > 0x08)
        if(bit > 0x20)
            if(bit == 0x40)
                return 6;
            else
                return 7;
        else
            if(bit == 0x10)
                return 4;
            else
                return 5;
    else
        if(bit > 0x02)
            if(bit == 0x04)
                return 2;
            else
                return 3;
        else
            if(bit == 0x01)
                return 0;
            else
                return 1;
}

这为8个值中的任何一个提供了3个步骤的恒定查找,这给了我非常确定的性能,线性搜索 - 给定的随机数据 - 将平均4步查找,最佳情况为1,最差情况为8脚步.

这是编译器可能不会优化到跳转表的范围的一个很好的例子,因为我搜索的8个值相距很远:1,2,4,8,16,32,64和128.它将不得不创建一个非常稀疏的128位置表,只有8个元素包含一个目标,这在具有大量RAM的PC上可能不是什么大问题,但在微控制器上它将是杀手.

Answer 2

为什么不使用开关？

swich(x.GetId())
{
  case 1: /* do work */ break; // From the most used case
  case 2: /* do work */ break; 
  case ...: // To the less used case
}

编辑:

将最常用的案例放在交换机的顶部(如果x.GetId通常等于50,则会出现性能问题)