开关案例构造是否实现为二进制搜索？ [英] Are switch-case constructs implemented as binary search?

问题描述

我想知道如何实现开关-情况语句：

I'm wondering how a switch-case statement is implemented:

示例

假设一个人具有以下代码：

say one has the following code:

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语句。

This can be important since there are programs (like compiler compilers) that write Java/C#/C++ source code and thus generate very large switch statements.

推荐答案

Switch / case语句是通过二进制组合实现的决策树和跳转表，视情况而定。

Switch/case statements are implemented with a combination of binary decision trees and jump tables, depending on the case ranges.

1. 对于简单的switch语句（2-3种情况），通常取决于值的密集程度（例如1 2 3与1 2 9），可以更有效地发出简单的if语句。

1. For simple switch statements (2 - 3 cases) it is often more efficient to emit simple if statement, depending on how dense the values are (1 2 3 vs 1 2 9 for example).

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

For larger cardinality switches with a single dense group, it is common to use a jump table based directly or indirectly on the test value.

稀疏组或稠密和稀疏的混合使用组中，使用二元决策树将组列表一分为二，并在组（树的叶子）中使用跳转表。

With sparse groups, or mix of dense and sparse groups, binary decision trees are used to bisect the group lists and a jump table is used within the group (the leaf of tree).

所以答案是，是的，有时候，但是不是

So the answer is, yes, sometimes, but not that simple.

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

It is possible to fill in "empty" case slots with default jumps to allow construction of a dense range. For small branches, or branches against non-integer values switches are rewritten as if conditionals (such as languages that allow switching on strings or regular expressions). In your example, cases for digits 0-9 would certainly be encoded as a lookup table because it is a dense group.

在所有情况下，二进制决策树都是发出高效转换/案例构造的重要组成部分。

In all cases, binary decision trees are an important part of emitting efficient switch / case constructs.

.NET CLR甚至有一个接受跳转表的操作码，它隐藏了默认情况的处理，这使运行时无需进行全流程分析就可以验证代码的安全性。

The .NET CLR even has an opcode that accepts jumptables, and it hides the handling of the default case, this allows the runtime to validate the code as safe without full flow analysis.

这篇关于开关案例构造是否实现为二进制搜索？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！