c# - 在 Func 值的开关与字典中，哪个更快，为什么？

Question

假设有如下代码:

private static int DoSwitch(string arg)
{
    switch (arg)
    {
        case "a": return 0;
        case "b": return 1;
        case "c": return 2;
        case "d": return 3;
    }
    return -1;
}

private static Dictionary<string, Func<int>> dict = new Dictionary<string, Func<int>>
    {
        {"a", () => 0 },
        {"b", () => 1 },
        {"c", () => 2 },
        {"d", () => 3 },
    };

private static int DoDictionary(string arg)
{
    return dict[arg]();
}

通过迭代这两种方法并进行比较，我发现字典稍微快一些，即使在“a”、“b”、“c”、“d”扩展为包含更多键时也是如此。为什么会这样？

这与圈复杂度有关吗？是因为抖动只将字典中的return语句编译一次为native code？是不是因为字典的查找是O(1)，即may not be the case for a switch statement ？ (这些只是猜测)

Answer 1

简短的回答是 switch 语句以线性方式执行，而字典以对数方式执行。

在 IL 级别，一个小的 switch 语句通常被实现为一系列 if-elseif 语句，比较切换变量和每个 case 的相等性。因此，该语句的执行时间与 myVar 的有效选项数量成线性比例；这些案例将按照它们出现的顺序进行比较，最坏的情况是尝试所有比较并且最后一个匹配或都不匹配。因此，对于 32 个选项，最坏的情况是它们都不是，代码将进行 32 次比较来确定这一点。

另一方面，字典使用索引优化的集合来存储值。在 .NET 中，字典基于哈希表，它具有有效的恒定访问时间(缺点是空间效率极差)。通常用于“映射”集合(如字典)的其他选项包括平衡树结构，如红黑树，它提供对数访问(和线性空间效率)。这些中的任何一个都将允许代码找到对应于集合中正确“case”的键(或确定它不存在)比 switch 语句可以做同样的事情快得多。

编辑:其他答案和评论者已经谈到了这一点，所以为了完整起见，我也会这样做。正如我最初推断的那样，Microsoft 编译器并不总是将开关编译为 if/elseif。它通常对少量案例和/或“稀疏”案例(非增量值，如 1、200、4000)这样做。对于较大的相邻案例集，编译器将使用 CIL 语句将开关转换为“跳转表”。对于大量稀疏案例，编译器可以实现二分搜索来缩小范围，然后“通过”少量稀疏案例或为相邻案例实现跳转表。

但是，编译器通常会选择性能和空间效率最佳折衷的实现，因此它只会在大量密集情况下使用跳转表。这是因为跳转表在内存中需要的空间与它必须覆盖的情况范围的顺序相同，对于稀疏情况而言，这在内存方面非常低效。通过在源代码中使用字典，您基本上是在强制编译器的手；它会按照您的方式进行，而不是为了提高内存效率而牺牲性能。

因此，我希望在大多数情况下，可以在源代码中使用 switch 语句或字典，以便在使用字典时表现得更好。 switch 语句中的大量 case 无论如何都要避免，因为它们的可维护性较差。