compiler-construction - switch-case 结构是否实现为二分搜索？

Question

我想知道如何 switch - case语句执行:

示例

说一个有以下代码:

Scanner sc = new Scanner(System.in);
int v = sc.nextInt();
switch(v) {
    case 0 :
        System.out.println("Zero");
        break;
    case 1 :
        System.out.println("One");
        break;
    case 2 :
        System.out.println("Two");
        break;
    //...
    default :
        System.out.println("No one digit number");
}

可以将其实现为:

if(v == 0) {
    System.out.println("Zero");
}
else if(v == 1) {
    System.out.println("One");
}
else if(v == 2) {
    System.out.println("Two");
}
//...
else {
    System.out.println("No one digit number");
}

但更有效的程序是:

if(v >= 0 && v <= 9) {
    if(v <= 5) {
        if(v <= 2) {
            if(v <= 1) {
                if(v == 0) {
                    System.out.println("Zero");
                }
                else {
                    System.out.println("One");
                }
            else {
                System.out.println("Two");
            }
        }
        //...
    }
    //...
}
else {
    System.out.println("No one digit number");
}

这很重要，因为有些程序(如编译器编译器)会编写 Java/C#/C++ 源代码，从而生成非常大的 switch 语句。

Answer 1

switch/case 语句根据 case 范围使用二叉决策树和跳转表的组合来实现。

对于简单的 switch 语句(2 - 3 种情况)，发出简单的 if 语句通常更有效，具体取决于值的密度(例如 1 2 3 与 1 2 9)。

对于具有单个密集组的较大基数开关，通常使用直接或间接基于测试值的跳转表。

对于稀疏组，或密集和稀疏组的混合，二叉决策树用于平分组列表，并在组内使用跳转表(树的叶子)。

所以答案是，是的，有时，但没那么简单。

可以使用默认跳转填充“空”案例槽以允许构建密集范围。对于小分支或针对非整数值的分支，开关被重写为条件语句(例如允许在字符串或正则表达式上切换的语言)。在您的示例中，数字 0-9 的情况肯定会被编码为查找表，因为它是一个密集组。

在所有情况下，二叉决策树都是发出高效 switch/case 结构的重要组成部分。

.NET CLR 甚至有一个接受跳转表的操作码，它隐藏了对默认情况的处理，这允许运行时在没有完整流程分析的情况下验证代码是否安全。