具有大量案例的switch语句

Question

如果switch超过5000,会发生什么case.有什么缺点以及如何用更快的东西替换它？

注意:我不希望使用数组来存储案例,因为它是相同的.

Answer 1

没有特别的理由认为除了转换/案例陈述之外你还想要任何其他东西(实际上我会积极地期望它没有用).编译器应该创建有效的调度代码,这可能涉及静态[稀疏]表和直接索引,二进制分支等的某种组合.它可以深入了解案例的静态值,并且应该做得很好(每次更改案例时都会重新调整它,而新的值不适合手工制作的方法 - 例如极不相同的值当你有一个非常紧凑的数组查找 - 可能需要重新编写代码或静默导致内存膨胀或性能下降).

当C试图赢得核心汇编程序员时,人们真正关心这种事情......编译器对生成好的代码负责.换句话说 - 如果它没有(可测量地)坏了,就不要修理它.

更一般地说,对这种事情感到好奇并获得人们关于替代方案及其性能影响的想法是很棒的,但是如果你真的关心并且性能差异可以对你的程序产生有用的影响(特别是如果分析表明它)那么总是基准你的程序做实际工作.

Answer 2

作为思考的食物......如果一个人可能会被一个旧的/错误/低效的编译器困住,或者只是喜欢黑客攻击.

switch陈述的内在工作由两部分组成.寻找跳跃的地址,并在那里跳得很好.对于第一部分,您需要使用表来查找地址.如果案例数增加,表格变大 - 搜索地址跳转需要时间.这是编译器尝试优化的点,结合了几种技术,但一种简单的方法是直接使用表,这取决于案例值空间.

在卫生巾背面的例子;

switch (n) {
    case 1: foo(); break;
    case 2: bar(); break;
    case 3: baz(); break;
}

使用这样的代码编译器可以创建一个jump_addresses数组,并通过array [n]直接获取地址.现在搜索只需要O(1).但如果您有如下所示的开关:

switch (n) {
    case 10: foo(); break;
    case 17: bar(); break;
    case 23: baz(); break;
    // and a lot other
}

编译器需要生成一个包含case_id,jump_address对和代码的表来搜索该结构,其中最差的实现可以采用O(n).(体面的编译器通过启用优化标志到你需要调试大脑开始炒的优化代码的程度时,完全释放出这种情况,从而优化了这种情况.)

那么问题是你可以在C级自己做这件事来击败编译器吗？有趣的是,在创建表格和搜索它们时似乎很容易,goto在标准C中跳转到变量点是不可能的.因此,如果由于开销或代码结构而不打算使用函数指针,则有可能被卡住......如果你不使用的话GCC.GCC有一个名为Labels as Values的非标准功能,可帮助您获取标签指针.

要完成该示例,您可以使用"标签为值"功能编写第二个switch语句,如下所示:

const void *cases[] = {&&case_foo, &&case_bar, &&case_baz, ....};
goto *labels[n];
case_foo:
    foo();
    goto switch_end;
case_bar:
    bar();
    goto switch_end;
case_baz:
    baz();
    goto switch_end;
// and a lot other
switch_end:

当然,如果您正在讨论5000个案例,那么如果您编写一段代码来为您创建此代码会好得多 - 而且它可能只是维护此类软件的方法.

作为结尾语; 这会改善你的日常工作吗？不会.这会提高你的技能吗？是的,从经验谈起,我曾经发现自己只是通过优化案例值来改进智能卡中的安全算法.这是一个奇怪的世界.