6

我在 Visual C 中有一个大的 switch 语句，大约有 250 个案例：

#define BOP -42
#define COP -823
#define MOP -5759

int getScarFieldValue(int id, int ivIndex, int rayIndex, int scarIndex, int reamIndex)
{
    int returnValue = INT_MAX;  
    switch (id)
    {       
        case BOP      : returnValue  = Scar[ivIndex][rayIndex].bop[scarIndex][reamIndex];    break;
        case COP        : returnValue  = Scar[ivIndex][rayIndex].cop[scarIndex][reamIndex];       break;
        case MOP         : returnValue  = Scar[ivIndex][rayIndex].mop[scarIndex][reamIndex];     break;
        .....
        default:  return(INT_MAX);
     }
}

您会注意到，#define 的范围很大，从 -1 到 -10,000。事情很慢，我想知道花几个小时将这 250 个定义重新定义为更窄（甚至连续）的范围是否可以加快速度。我一直认为编译器会以一种使它们的数值无关紧要的方式处理案例值，但我无法找到任何讨论来验证/无效该假设。

4

8 回答 8

2

反汇编编译后的代码，看看编译器做了什么。我查看了几个不同编译器的输出，大型 switch 语句总是被编译成二进制决策树或跳转表。跳转表是您可以获得的最优化的东西，如果您打开的值在一个狭窄的范围内，它们更有可能由编译器生成。它还有助于在某些编译器上使用默认语句（但在其他编译器上不是必需的）。

在这种情况下，反汇编是您唯一的好选择，这一级别的代码生成细节很少有很好的文档记录。

于 2013-07-10T07:12:44.383 回答
1

如果您查看代码的汇编输出，您可能会注意到您的switch语句正在被编译成类似于级联if语句的代码：

if (id == BOP) ...
else if (id == COP) ...
else if (id == MOP) ...
...
else ...

因此，加快switch语句速度的一个简单技巧是将最常命中的案例移到顶部附近。

如果对案例值进行了排序，则编译器可能能够生成二叉决策树，从而将复杂性从线性降低到对数。

在支持它的编译器的足够高的优化级别上，编译器可能能够生成计算goto样式代码。对于不连续的值，跳转到的偏移量将存储在哈希表中，并为案例值生成完美的哈希函数。对于连续值，不需要哈希函数，因为可以使用简单的索引数组来存储跳转偏移量。您必须检查优化代码的汇编器输出，以查看您的编译器是否支持此功能。

否则，最好在 case 值上创建自己的哈希值，而不是使用switch，您将自己进行哈希表查找以找到要使用的正确矩阵，然后获取您的值。

于 2013-07-10T06:35:09.370 回答
1

简单的解决方案：将开关盒分成多个部分。

if(id<=50)
{
    switch(id)
    {
      //All cases between 0 to 50
    }
}
else if (id>50 && id<=100)
{
    switch(id)
    {
      //All cases between 51 to 100
}
//and so on

范围的选择是你的。并且不要创建很多范围。这将确保代码比您当前的代码更快。或者，您可以使用函数指针并编写包含要在案例中执行的语句的函数。我会更喜欢这种方法。

typedef struct
{
    void(*Cur_FunctnPtr)();     
}CMDS_Functn;

void (*Cur_Func)();
CMDS_Functn FunctionArray[66] = {
                    /*00-07*/    (*Func1),(*Func2),(*Func3),...
                    /*08-0F*/       

                    /*40-47*/       };

void my_func()
{
...  //what ever code
    Cur_Func = FunctionArray[id].Cur_FunctnPtr; //Load current Function Pointer
        (*Cur_Func)();
... // what ever code
}
于 2013-07-10T06:45:33.023 回答
1

也许你应该使用哈希表，所以你可以搜索哈希表而不是“ switch case”。

于 2013-07-10T06:31:20.237 回答
1

阅读代码以找出switch编译的内容。

如果您有一个方便的哈希表实现，您可以尝试使用它，但它当然需要您将所有“操作”代码提取到您可以从哈希表查找结果中跳转到的内容中。

如果使用 GCC，我会做一个快速测试，将GCC 的计算 goto与一个简单的排序数组结合起来，这样你就可以使用良好的旧二分搜索。后者会将您的代码进行的最坏情况比较的数量从 250/2 减少到 log 2 (250)，即大约 8。

这将需要在编译时声明一个查找表（并且可能在运行时排序一次），这在内存开销方面可能比大多数哈希表所能管理的要好。

于 2013-07-10T07:08:14.723 回答
0

如果您知道可能的 id 值的分布特征，请在您的案例陈述中以最可能到最不可能的顺序测试它们。

如果这被频繁调用，您可能需要考虑将选择存储在字典中：它们无需串行比较即可解决，因此如果确实有 10,002 个选择，则可能会节省大量时间。

于 2013-07-10T06:27:32.490 回答
0

您的问题是 ID 的范围不连续。没有编译器可以比使用对数深度的级联条件做得更好，这里大约为 8。

解决此问题的一种方法是使用enum使您的 ID 连续的方法，然后编译器可以使用跳转表来加快速度。要真正知道这是否有效，您必须检查应用程序的其余部分以查看它是否支持更改值。

于 2013-07-10T06:28:24.153 回答
0

编译器只会使用它知道的技术进行优化，如果这些技术都不起作用，那么你会得到一些可怕的东西。

您可以自己实现某些东西，也可以尝试为编译器提供一些线索。在后一种情况下，您很有可能让编译器“得到它”，然后比您自己的实现进一步优化解决方案——并且编译器可以避免限制您自己的解决方案的 C 语法限制。

至于解决方案；显然最好的办法是将它们重新编号为连续的。

另一种方法是获取 250 个值并搜索完美的散列函数以将它们减少到 8 位数量。

#define PERFECT_HASH(x) ((x) & 0xff) /* some clever function of x */

switch (PERFECT_HASH(id))
{       
case PERFECT_HASH(BOP): returnValue  = Scar[ivIndex][rayIndex].bop[scarIndex][reamIndex];    break;
case PERFECT_HASH(COP): returnValue  = Scar[ivIndex][rayIndex].cop[scarIndex][reamIndex];       break;
case PERFECT_HASH(MOP): returnValue  = Scar[ivIndex][rayIndex].mop[scarIndex][reamIndex];     break;
.....
default:  return(INT_MAX);
}

但是，在剪切和粘贴该代码后，看起来您正在使用 switch 语句将其转换id为有效的指针值，指向数据结构的不同部分。如果所有案例都包含对同一种指针的单次读取，那么您肯定不想为此使用开关。您需要查看数据的形状并找到一种更直接地计算该指针的方法。或者简单地打开类型并单独计算地址。

于 2013-07-10T08:42:38.343 回答