在开关VS字典Func键的值，这是更快，为什么？ [英] In a switch vs dictionary for a value of Func, which is faster and why?

问题描述

假设有下面的代码：

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]();
}

通过遍历这两种方法，比较，我得到的解释是稍微快，即使当一，b，C，d被扩大，以包括更多的键。为什么会这样？

By iterating over both methods and comparing, I am getting that the dictionary is slightly faster, even when "a", "b", "c", "d" is expanded to include more keys. Why is this so?

这是否与圈复杂呢？是因为抖动编译在字典中return语句为本地代码只有一次？是不是因为词典的查找是O（1），其中可能并非如此switch语句的？ （这些都只是猜测）

Does this have to do with cyclomatic complexity? Is is because the jitter compiles the return statements in the dictionary to native code only once? Is it because the lookup of the dictionary is O(1), which may not be the case for a switch statement? (These are just guesses)

推荐答案

简短的答案是，switch语句线性的执行，而字典执行对数。

The short answer is that the switch statement executes linearly, while the dictionary executes logarithmically.

在IL层面，小switch语句通常是一系列的if-elseif的语句比较切换变量，每个案件的平等实现。因此，这份声明将在线性正比于对myVar的有效选项的数量一次执行;的情况下，将在它们出现的顺序进行比较，并在最坏的情况是，所有的比较都试过，要么是最后一个匹配或没有做。所以，带32的选择，在最坏的情况是，它是其中没有，和代码将取得32比较，以确定该

At the IL level, a small switch statement is usually implemented as a series of if-elseif statements comparing equality of the switched variable and each case. So, this statement will execute in a time linearly proportional to the number of valid options for myVar; the cases will be compared in the order they appear, and the worst-case scenario is that all the comparisons are tried and either the last one matches or none do. So, with 32 options, the worst case is that it's none of them, and the code will have made 32 comparisons to determine this.

一个字典，另一方面，使用索引优化的集合来存储值。在.NET中，一个字典是基于一个Hashtable，有效地持续访问时间（缺点是空间效率极差）。常用的像字典映射集合其他选项包括平衡树结构如红黑树，它提供了对数存取（和线性空间效率）。任何这些将允许代码以查找对应于该集合中的适当的的情况下键（或者确定它不存在）比switch语句可以做同样的速度要快得多。

A Dictionary, on the other hand, uses an index-optimized collection to store values. In .NET, a Dictionary is based on a Hashtable, which has effectively constant access time (the disadvantage being extremely poor space efficiency). Other options commonly used for "mapping" collections like Dictionaries include balanced tree structures like red-black trees, which provide logarithmic access (and linear space efficiency). Any of these will allow the code to find the key corresponding to the proper "case" in the collection (or determine it does not exist) much faster than a switch statement can do the same.

修改：其他的答案和评论者对这个感动，所以在完全的利益我会很好。微软编译器的不的始终编译开关的，如果/ elseif的，因为我原来的推断。它通常与少量的情况下，和/或用稀疏情况下（非增量值，例如1，200，4000）这样做。对于较大的套相邻的情况下，编译器将开关转换为使用CIL语句跳表。随着大型成套稀疏的情况下，编译可以实现二进制搜索缩小范围，然后少数稀疏的情况下，通过落或实施跳转表相邻的案件。

EDIT: Other answers and commenters have touched on this, so in the interest of completeness I will as well. The Microsoft compiler does not always compile a switch to an if/elseif as I inferred originally. It typically does so with small numbers of cases, and/or with "sparse" cases (non-incremental values, like 1, 200, 4000). With larger sets of adjacent cases, the compiler will convert the switch into a "jump table" using a CIL statement. With large sets of sparse cases, the compiler can implement a binary search to narrow the field, and then "fall through" a small number of sparse cases or implement a jump table for adjacent cases.

不过，编译器通常会选择是性能和空间效率的最佳平衡点的实施，因此它只会使用跳转表进行了大量的densely-包装的情况。这是因为跳转表需要它必须涵盖案件的范围，这对于稀疏的情况下是非常低效的记忆明智的顺序在内存的空间。在源代码中使用字典，你基本上强制编译器的手;它会做你的方式，而不是牺牲性能来获取内存使用效率。

However, the compiler will typically choose the implementation that is the best compromise of performance and space efficiency, so it will only use a jump table for a large number of densely-packed cases. This is because a jump table requires a space in memory on the order of the range of cases it must cover, which for sparse cases is terribly inefficient memory-wise. By using a Dictionary in source code, you basically force the compiler's hand; it will do it your way, instead of compromising on performance to gain memory efficiency.

所以，我希望在任何一个switch语句或字典可以在源使用字典时，可以使用有更好的表现大多数情况下。是无论如何避免switch语句的情况下大量地，因为他们不太维护。

So, I would expect most cases in which either a switch statement or a Dictionary could be used in source to perform better when using a Dictionary. Large numbers of cases in switch statements are to be avoided anyway, as they are less maintainable.

这篇关于在开关VS字典Func键的值，这是更快，为什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！