如何改进一堆 else-if 条件来评估已知值范围内的变量？

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

您可以使用 interval_map。有一个示例实现 here 简单地说，它持有设定范围内任何事物的参考。您需要为您的案例填写边缘案例，例如：

m_map.insert(std::make_pair(0, foo1));
m_map.insert(std::make_pair(3, foo2));
m_map.insert(std::make_pair(8, foo3));

那么您可以通过 m_map[1] 简单地获得您想要的功能。这将 return 映射中的第一个函数。

注：我以 link 为例。实施可能会有问题。使用前最好测试一下。

Answer 2

在一般情况下，您有一些区间 [a1, a2), [a2, a3), ..., [an, infty) 并且想要找到 x 所在的区间，您可以使用最坏情况 log n 比较（与. 你的 if-else-chain 有最坏情况 n 比较）。您可以通过对间隔进行二进制搜索来做到这一点。因此，您将首先检查 x 是否小于 a(n/2)，然后进一步检查 if 情况下较小的间隔和 else 情况下较大的间隔。对于上面的示例，transform

     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，那么您一定要先检查它，依此类推。

如何改进一堆 else-if 条件来评估已知值范围内的变量？

How to improve a bunch of else-if conditions that evaluate a variable inside a range among known values?

c++

performance

if-statement

function-pointers