切换案例或std::map的效率更高是什么?

Visual Studio 2008附带的STL映射将为每个函数调用提供O(log(n)),因为它在下面隐藏了一个树结构。 使用现代编译器(取决于实现),switch语句将为您提供O(1),编译器将其转换为某种查找表。 所以总的来说,切换速度更快。

然而 ,考虑以下事实:

MAP和交换机的区别在于:MAP可以动态构建,而交换机不能。Mmap可以包含任意类型的密钥,而交换机非常受限于C++原始类型(char、int、eNUM等)。

顺便说一下,您可以使用散列映射来实现接近O(1)的调度(不过,根据散列表的实现,在最坏的情况下,它有时可能是O(N)。尽管如此,切换速度还是会更快。

编辑

我写以下文章只是为了好玩和讨论这个问题

我可以为您提出一个很好的优化建议,但这取决于您的语言的性质以及您是否可以期望如何使用您的语言。

编写代码时: 您将令牌分为两组,一组使用频率非常高,另一组使用频率较低。您还可以对频繁使用的令牌进行排序。 对于高频率令牌,您可以编写一个if-else系列,其中使用频率最高的是coming-first。对于经常使用的低位,编写switch语句。

其思想是使用CPU分支预测来避免另一个间接级别(假设if语句中的条件检查几乎没有成本)。 在大多数情况下,CPU将选择正确的分支,而不需要任何间接级别。然而,他们将很少出现分支机构会去错地方的情况。 根据语言的性质,统计上它可能会提供更好的性能。

编辑 :由于下面的一些注释,更改了语句,告诉编译器将始终将开关翻译为LUT。

我建议你阅读 switch() vs. lookup table? 来自Joel的软件。特别是,这种反应很有趣:

“人们浪费时间的主要例子 尽量优化 意义重大。”

是和否。在虚拟机中,通常 调用每个函数都非常 很少。不是电话/回电 那伤害你和序言一样多 以及每个功能的清理程序 通常占很大比例 执行时间。这一直是 研究到死亡,特别是 已经实现线程的人 口译员。

在虚拟机中,存储要调用的计算地址的查找表通常优先于交换机。(直接线程或“标记为值”。直接调用存储在查找表中的标签地址),这是因为它允许在某些情况下减少 branch misprediction 这在长的流水线CPU中是非常昂贵的(它强制刷新管道)。然而,它使得代码不那么可移植。

这个问题已经在虚拟机社区进行了广泛的讨论,如果您想更多地了解它,我建议您在这个领域寻找学者论文。Ertl&Gregg在2001年写了一篇关于这个主题的伟大文章, The Behavior of Efficient Virtual Machine Interpreters on Modern Architectures

但如前所述,我确信这些细节与 你的 代码。这些都是小细节,你不应该过分关注它。python解释器正在使用开关,因为它们认为这会使代码更具可读性。你为什么不选择最适合的用法呢?性能影响很小,现在最好关注代码的可读性;)

编辑 :如果重要,使用哈希表将 总是 比查找表慢。对于查阅表格,您使用“keys”的枚举类型,并使用单个间接跳转检索值。这是一个单独的组装操作。O(1)。哈希表查找首先需要计算一个哈希,然后检索值,这样做成本更高。

使用存储函数地址并使用枚举值访问的数组是很好的。但是使用哈希表做同样的事情会增加一个重要的开销

综上所述,我们有:

• 成本(哈希表)>>成本(直接查找表)
• 如果编译器将开关转换为查找表,则cost(direct_lookup_table)~=cost(switch)。
• 成本(开关)>>成本(直接查找表)(O(N)vs O(1)),如果您的编译器不转换开关并使用条件,但我想不出任何编译器会这样做。
• 但是,内联直接线程使代码的可读性变差。

你对“高效”的定义是什么?如果您的意思是更快,那么您可能应该为一个确定的答案配置一些测试代码。如果您需要灵活且易于扩展的代码,那么请帮自己一个忙并使用map方法。其他的一切只是过早的优化…

正如Yossi1981所说,一个开关可以被优化为一个快速查找表,但不能保证,每个编译器都有其他算法来决定是将开关实现为连续的if's,还是作为快速查找表,或者两者的结合。

要获得快速切换,您的值应符合以下规则: 它们应该是连续的,例如0、1、2、3、4。您可以去掉一些值,但像0、1、2、34、43这样的值极不可能被优化。

真正的问题是:在您的应用程序中,性能是否具有如此重要的意义? 动态地从文件加载其值的映射是否比跨越多页代码的大型语句更易于读取和维护?

你不知道你的代币是什么类型的。如果它们不是整数,您就没有选择-开关只能用于整数类型。

C++标准没有说明其性能的要求,只是功能应该在那里。

这些关于哪个更好、更快或更有效的问题没有意义,除非你陈述 实施 你说的是。例如,在特定版本的某个JavaScript实现中的字符串处理非常糟糕,但您不能将其推断为相关标准的一个特性。

我甚至会说,无论实现如何,它都无关紧要,因为 switch 和 std::map 是不同的(尽管有重叠)。

在我看来,这种微观优化几乎从来没有必要。