11

如果switch超过 5000会发生什么case。有什么缺点以及我们如何用更快的东西代替它？

注意：我不希望使用数组来存储案例，因为它是相同的。

4

4 回答 4

13

除了 switch/case 语句之外，没有什么特别的理由认为你想要其他任何东西（而且我确实希望它没有帮助）。编译器应该创建有效的调度代码，这可能涉及静态[稀疏]表和直接索引、二进制分支等的某种组合；它可以深入了解案例的静态值，并且应该做得很好（每次更改案例时都会即时重新调整它，而新值不适合手工制作的方法 - 例如差异很大的值当您进行了非常紧凑的数组查找时 - 可能需要重新编写代码或默默地导致内存膨胀或性能下降）。

当 C 试图赢得铁杆汇编程序员的支持时，人们真的很关心这种事情……编译器负责生成好的代码。换句话说 - 如果它没有（可测量地）损坏，请不要修复它。

更一般地说，很高兴对这种事情感到好奇并了解人们对替代方案及其性能影响的想法，但如果你真的关心并且性能差异可能会对你的程序产生有用的影响（特别是如果分析表明它）那么总是与您的程序进行实际工作的基准测试。

于 2012-09-12T07:22:54.803 回答
11

作为深思熟虑的食物......以防有人可能会被旧的/错误的/低效的编译器所困，或者只是喜欢黑客攻击。

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 有一个非标准特性，称为标签作为值，它可以帮助您获取指向标签的指针。

要完成该示例，您可以使用“标签作为值”功能编写第二个 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 个案例，最好编写一段代码来为您创建此代码 - 这可能是维护此类软件的唯一方法。

作为结束语；这会改善您的日常工作吗？不会。这会提高你的技能吗？是的，根据经验，我曾经发现自己仅通过优化案例值就改进了智能卡中的安全算法。这是一个奇怪的世界。

于 2012-09-12T08:30:49.443 回答
3

尝试将 Dictionary 类与 Delegate 值一起使用。至少它使代码更具可读性。

于 2012-09-12T07:20:48.647 回答
1

大 switch 语句，通常是自动生成的，可能需要很长时间才能编译。但我喜欢编译器优化 switch 语句的想法。

拆分 switch 语句的一种方法是使用分桶，

int getIt(int input)
{
  int bucket = input%16;
  switch(bucket)
  {
    case 1:
      return getItBucket1(input);
    case 2:
      return getItBucket2(input);
    ...
    ...
  }
  return -1;
}

所以在上面的代码中，我们将 switch 语句分成了 16 个部分。在自动生成的代码中更改存储桶的数量很容易。

此代码增加了一层间接或函数调用的运行时成本。. 但是考虑到不同文件中定义的桶，并行编译它们会更快。

于 2017-08-28T20:03:37.643 回答