c++ - 如果在已知值范围内评估变量，如何改善其他条件？

Question

有什么办法可以将下面的代码转换为更具可扩展性的代码？我已经简化了它，但是我真正的人必须检查几个不同的值，并且它要求重构。

     if (x < 0) foo1();
else if (x < 3) foo2();
else if (x < 8) foo3();
else            foo4();

我尝试了以下方法:

struct Ptr2foo {
    void (*foo_x)();
}

Ptr2foo ptr2foo_x[4] {
    foo1,
    foo2,
    foo3,
    foo4
}

ptr2foo_x[someMagicWithMy_X_AndMyKnownValues].foo_x();

这些值在编译之前是已知的，并且循环内的条件数量会降低性能。

这是解决此问题的最佳方法吗？对其解释的任何替代解决方案都表示赞赏

Answer 1

在一般情况下，您有一些[a1, a2), [a2, a3), ..., [an, infty)间隔，并且想找到x所在的间隔，您可以使用最坏情况的log n比较来实现(相对于您的if-else链具有最坏情况的n比较)。您可以通过对间隔进行二进制搜索来实现。因此，您将首先检查x是否小于a(n/2)，然后进一步检查if -case中较小的间隔和else -case中较大的间隔。对于上面的示例，进行转换

     if (x < 0) foo1();
else if (x < 3) foo2();
else if (x < 8) foo3();
else            foo4();

最长路径上有4个比较，最短路径上有1个比较

if( x < 3 ) {
  if( x < 0 ) foo1();
  else        foo2();
} else {
  if( x < 8 ) foo3();
  else        foo4();
}

它在所有路径上都有2个比较。

请注意，在最坏的情况下进行较少的比较不一定会更快。如果 x大致均匀分布，则速度会更快。如果 x在90％的情况下为负，则您的第一个版本会更快，因为它只会使用一个比较，而我的版本总是使用2。

这就是为什么您还应该考虑一下此代码中的热路径(即最常见的路径)是什么。如果在大多数情况下 x至少为8，则应该首先检查它，依此类推。