1

我有以下定义：

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 替代方案。

有什么更快的吗？m1~m14 的值是固定的，不能在连续的范围内。

谢谢。

4

7 回答 7

7

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

如果值不连续，编译器可以求助于具有 O(log(n)) 性能的静态二叉决策树。对于一个连续的值列表，它会构造一个跳转表，即O(1)。相比之下，if-else 构造是 O(n)。

我建议您在使用其他方法之前充分了解您可以从 switch 语句中得到什么。

于 2013-09-05T18:57:43.933 回答
6

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

if (valuesArray[x])
    YahooItsGood();

当然，如果你的范围很大，那是行不通的。

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

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

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

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

于 2013-09-05T18:26:38.437 回答
1

如果您可以保证输入为 8 位宽，这是一个简单的想法：创建一个大小为 256 的静态 int 数组，在您的枚举指定的索引处为 1，在其他任何地方为 0。然后你所要做的就是一个数组查找。

于 2013-09-05T18:27:11.657 回答
1

我更喜欢二进制搜索，因为这些值是有序的。

一个定义一个数组： 

  my_enums enumv[17] = {def, m1, m2, m3, m4, m5, m6, m7, m8, m9, m10, m11, m12, m13, m14, -1, -1};

（最后 2 个值是分号，它们对结果没有影响）。

然后进行二分查找： 

  int s = 0;
  for (int i = 8; i; i /= 2)
        if (p >= enumv[s+i])
           s += i;
  if ( p >= 0 && p == enumv[s])
     printf("Happy\n");
  else
     printf("Unhappy\n");

如果您不想要所有“for”的东西，并且由于您只有 15 个值，则可以展开并编写“手头”的算法，以更快： 

  int s = 0;
  s += 8*(p >= enumv[s+8]); 
  s += 4*(p >= enumv[s+4]);
  s += 2*(p >= enumv[s+2]);
  s +=   (p >= enumv[s+1]);

  if (p >= 0 && p == enumv[s])
     printf("Happy\n");
  else
     printf("Unhappy\n");
于 2013-09-05T20:09:08.913 回答
1

我的 2 美分 - 在 MSB 上使用按位运算分而治之。看到这里 32 接近中位数，首先将表格分成两半

    if (p & 32)

下一个级别是将错误情况与 (p & 4) 和真实情况与 (p & 64) 进行比较 - 这使您在每个分支中都只有 3 个选项（可以被逻辑或覆盖），除了介于32 和 64，可以使用 (p & 48) 进一步分解（这不是 2 的圆幂，所以它只适用于某些情况，我猜只有 MSB 相等的情况下）

这里的好处是您已经完成了二进制搜索（即使在最坏的情况下，您的数字是连续的，您也会陷入整个区域的二进制搜索，仍然是 log(MAX_N)），并且您正在使用便宜的can 编译器可能能够谓词的按位运算（或者您可以继续自己做）

于 2013-09-05T20:11:59.703 回答
0 
if(p/7==0 && (p%6!=3 ||p%6!=5))
 // p is present, p = 0,1,2,4,6
if(p==17||p==33.....remaining 7 numbers)
//p is present

so you got them reduced from 14 condition evaluations to 12... Maybe try to find some relations among the values like I did above.

于 2013-09-05T18:51:03.090 回答
0

由于您想要最快的，因此位操作应该比字节快。

你可以有 17 个八位字节。对于每个位，如果该位是您想要的，则将其标记为 1，否则标记为 0。对于每次查找，只需计算八位字节 id 和您要检查的位，然后检查它即可得到结果。

于 2013-09-05T18:53:54.143 回答