Switch语句中case的顺序是否会影响性能？

Question

Switch语句中case的顺序是否会影响性能？

c#performancemicro-optimizationswitch-statement

24

假设我有以下的switch语句

switch(alphabet) {

    case "f":
        //do something
        break;

    case "c":
        //do something
        break;

    case "a":
        //do something
        break;

    case "e":
        //do something
        break;

}

现在假设我知道 Alphabet 中字母 e 的出现频率最高，其次是 a、c 和 f。因此，我重新排列了 case 语句的顺序，使它们如下所示：

switch(alphabet) {

    case "e":
        //do something
        break;

    case "a":
        //do something
        break;

    case "c":
        //do something
        break;

    case "f":
        //do something
        break;
}

第二个 switch 语句会比第一个更快吗？如果是，那么如果在我的程序中我需要多次调用此 switch 语句，那么这是否会有实质性的改进？如果不是，那么我如何使用我的频率知识来提高性能？

- Bipul

5

你不应该尽可能清晰明了地书写，包含真实世界中的场景，并在必要时进行优化吗？ - Jay Bazuzi

4个回答

3

这取决于编译器如何实现switch语句。

首先，您不能任意排列顺序；如果您在类C语言（C、C ++、C＃、Java等）中有一个case块，并且该case块没有以break结尾，则无法重新排列case，因为缺少break意味着编译器必须实现到下一个case的转移。如果我们忽略这种特殊情况，您可以重新排列其余的case。

如果case的数量很少，编译器可能会通过一系列比较来实现case测试。如果case的数量适中，它可能会从case构建一个平衡二叉树。如果case的数量很大，则大多数编译器在switch值来自密集集合时实现索引分支。如果case值集的某些部分是密集的，而其他部分不是，则编译器可能使用二叉树将case分成组，以选择哪个密集集合，以及在密集集合内进行索引跳转。（实际上，编译器可能技术上执行任何将控制传递给适当case的操作，但大多数情况下是以上述方法之一）。

您可以看到顺序可能很重要，也可能不重要，这取决于编译器如何实现switch。对于大多数良好的编译器，这并不重要。

- Ira Baxter

1

为了清晰起见，该问题被标记为C#，而C#不支持如此描述的“fall through”情况（每个case必须以break或return终止）。 - Dusty

有趣。所以人们在C#中不必要地编写“break”（例如，参见OP的示例）。这并没有真正改变我的答案。 - Ira Baxter

不，C# 在这方面有点啰嗦，你必须显式地终止 case 块；需要使用 break（或 return）（可能是为了防止未来实现的 fall-through cases 变成破坏性更改）。我同意，你的答案仍然是正确和有用的。 - Dusty

必须使用break来标识语句的结束，因为您可以将相同的语句用于2个或更多的标签。 case "null": case "0": case "": ...处理“空”场景... break; case "foo1": ... break; case "foo2": ... break; - frenchone

2

它们在相对较小的值集上具有相同的性能。我曾经尝试过检查C程序的汇编代码，编译器会从switch语句中所有的值中创建一个跳转表。但是如果case的值太多，它们很可能会退化为if else if结构，所以将case 'E'放在顶部肯定会加快速度。

这也适用于C#，C#也会针对一组小的连续值生成switch语句的跳转表，因此它的时间复杂度为O(1)，即使第一个值不匹配，也不会进行多次测试。

- Michael Buen

-3

我认为 switch case 的工作方式是从上到下循环遍历所有的 case，以找到匹配项。如果匹配成功，它就会停在那里。

因此，如果您进行了更改以优先考虑频率较高的 case，答案是肯定的，它可以在某种程度上提高性能。但我相信这不会带来太大的帮助。

- vodkhang

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dean Harding · Accepted Answer

不用过于担心，这当然不是可以被预测的事情。

对于字符串case标签，编译器实际上使用一个内部哈希表将字符串映射为跳转表中的索引。因此，操作实际上是O(1) - 与标签数目无关。

对于整数标签，我认为所生成的实际代码取决于标签数目以及数字是否连续（或“几乎”连续）。如果它们是连续的（1、2、3、4...），那么它们将直接被转换为跳转表。如果有很多标签，则将使用Hashtable+跳转表（就像字符串一样）。如果只有几个标签而且它们不能立即转换为跳转表，则仅在这种情况下它们将被转换为一系列if...then...else语句。

总的来说，您应该编写能够自己阅读的代码，而不是让编译器生成“更快”的代码。

（注意，我上面的描述是C#编译器内部工作的实现细节：您不应该依赖它总是像那样工作 - 实际上，它甚至可能不会现在完全像那样工作，但至少这是一般的想法）。