什么是更高效的开关case或std :: map [英] What is more efficient a switch case or an std::map

问题描述

我在这里考虑分词器。

每个令牌在分析器中调用不同的函数。

更有效的是：

• std :: functions / boost :: functions的地图


• 切换案例

解决方案

Visual Studio 2008附带的STL地图会为每个函数调用提供O（log（n）），因为它隐藏了一个树结构下面。
使用现代编译器（取决于实现），switch语句将给你O（1），编译器将其转换为某种查找表。

，请考虑以下事实：

b $ b

map和switch之间的区别是：Map可以动态构建，而switch不能。 Map可以包含任何任意类型作为键，而切换非常局限于c ++ Primitive类型（char，int，enum等）。

顺便说一句，你可以使用哈希映射实现近O（1）调度（虽然，根据哈希表实现，它有时可以是O（n）在最坏的情况下）。

$ b

我写的只是为了乐趣和讨论的事情

我可以建议一个不错的优化，但它取决于你的性质语言以及是否可以预期如何使用您的语言。

当您编写代码时：
您将令牌分为两组，一组将频繁使用，另一组使用频率低。您还排序高频率使用的令牌。
对于高频率令牌，你写一个if-else系列，最常用的是第一个。对于低频率使用，你写一个switch语句。

这个想法是使用CPU分支预测为了甚至避免另一个间接级别在if语句中几乎是无成本的）。
在大多数情况下，CPU会选择没有任何级别的间接正确的分支。他们将是少数情况下，该分支将去错误的地方。

编辑：由于下面的一些注释，根据你的语言的性质， Changed这句话告诉编译器会将开关切换到LUT。

I'm thinking about the tokenizer here.
Each token calls a different function inside the parser.
What is more efficient:

• A map of std::functions/boost::functions
• A switch case

解决方案

STL Map that comes with visual studio 2008 will give you O(log(n)) for each function call since it hides a tree structure beneath. With modern compiler (depending on implementation) , A switch statement will give you O(1) , the compiler translates it to some kind of lookup table. So in general , switch is faster.

However , consider the following facts:

The difference between map and switch is that : Map can be built dynamically while switch can't. Map can contain any arbitrary type as a key while switch is very limited to c++ Primitive types (char , int , enum , etc...).

By the way , you can use a hash map to achieve nearly O(1) dispatching (though , depending on the hash table implementation , it can sometimes be O(n) at worst case). Even though , switch will still be faster.

Edit

I am writing the following only for fun and for the matter of the discussion

I can suggest an nice optimization for you but it depends on the nature of your language and whether you can expect how your language will be used.

When you write the code: You divide your tokens into two groups , one group will be of very High frequently used and the other of low frequently used. You also sort the high frequently used tokens. For the high frequently tokens you write an if-else series with the highest frequently used coming first. for the low frequently used , you write a switch statement.

The idea is to use the CPU branch prediction in order to even avoid another level of indirection (assuming the condition checking in the if statement is nearly costless). in most cases the CPU will pick the correct branch without any level of indirection . They will be few cases however that the branch will go to the wrong place. Depending on the nature of your languege , Statisticly it may give a better performance.

Edit : Due to some comments below , Changed The sentence telling that compilers will allways translate a switch to LUT.

这篇关于什么是更高效的开关case或std :: map的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！