能否动态实现case语句

songtebo

如下代码速度很快

int foo(int a) {   switch(a)   {     case 1:       return 4;     case 8828042:       return 5;     case 4482232:       return 6;     default:       return 7;   } }

这是影响速度的关键函数，但问题是函数中的所有数字在程序运行中才能确定。a的值在0~4261478400之间，分支在4~100之间，返回结果在0~200之间。采用二分查找的方法性能还不达标。

能否实现动态的CASE语句？

nlylidb

不知道你研究过switch在编译时的优化没有。这是我简单测试得到的结果
http://blog.chinaunix.net/u3/94078/showart.php?id=1888387

在这种数据跨越度比较大的时候，gcc编译时会对case语句的数据进行自动优化。
switch在编译时会先获得case中的各值，然后进行排序，如果跨度（最大值与最小值之差与case个数比较）不是很大，会使用造表法（生成跳转表），这种速度是最快的，为O（1），但是空间复杂度为O（n）
如果跨度比较大，编译器会自动生成使用二分法优化的查找比较模式， 不妨直接使用case然后gcc －S看看汇编码就知道了，生成的汇编码与case中数据的排序方法无关，这时时间复杂度为O(log(n)),空间复杂度为O(1)。

而if-else嵌套使用需要程序员控制查找方法。最差为O(n)，但是if-else嵌套中的空间复杂度是一样的

[ 本帖最后由 nlylidb 于 2009-4-17 10:00 编辑 ]

flyingtime

不知道用std::map<int,int>会不会更好一些:wink:

songtebo

试验过，std::map<int,int>比自己写的二分查找方法速度还慢一点点。

CASE是O(1)。
std::map<int,int>，二分查找方法这些都应该是 O(log(n))

action08

这个优化太底层了

假设数据类型long是4B空间的，假设把数字表示成A-B-C-D(cd=256 *c+d...)（该思想可以直接优化成二分查找）

可以先判断A『最多256个空间，很快』，然后再判断B，，，共判断4次。

思想大概就是有原来的“一次查找”变成“四次查找”。分析一下业务，看看可以这样做不？)

switch(a && oxff000000)
{
case :...
       switch(a && oxff0000)
               {;//类似...}
case :...

}

===
其他方法都很底层，，我也想知道

[ 本帖最后由 action08 于 2009-4-17 09:45 编辑 ]

flyingtime

好像只有case是从0开始依次递增的情况时间复杂度才是O(1)吧
我这里找到一个在C#中关于对switch分析的一篇文章：
http://msdn.microsoft.com/zh-cn/downloads/dd310342.aspx
你可以看一下，我认为Dictionary<TKey,TValue>类似于std::map<key,value>

marxn

为啥不用hashtable

songtebo

原帖由 action08 于 2009-4-17 09:40 发表
这个优化太底层了

假设数据类型long是4B空间的，假设把数字表示成A-B-C-D(cd=256 *c+d...)（该思想可以直接优化成二分查找）

可以先判断A『最多256个空间，很快』，然后再判断B，，，共判断4次。

思想 ...

感觉这个速度和直接二分法应该一致，但增加了代码复杂程度。



非常感谢大家！！

swxlion

不太清楚楼主所言“动态”是何意思？如果是if-else的话，通过函数的调用拼接（虽然不够安全），是可以实现动态变化的case。但如果用switch的话，我的理解是：switch不论编译器再怎么优化，都是静态的。因为它不能再随运行期状态而变动case的数目和值。
如果优化后造表的话，的确是可以达到时间复杂度为O(1)，但从 nlylidb 给出的资料看来，这个O(1)仅存在于连续值的情况下，如果值不连续，那就退化为O(log2(n))的二分法。但不论是否退化，case的数目和条件在编译后已经转为静态，无法动态改变。如果需要动态改变的话，用AVL Tree、RB Tree等时间复杂度为O(log2(n))的二叉搜索树感觉应该是个不错的选择，就正如flyingtime 提议的本质。但是stl的问题就在于为了使用方便而对运行期执行效率作了妥协，所以可能还是自己写一个，或者使用其他的时间复杂度为O(log2(n))的树结构来的好。
另外一个疑问就是，gcc/g++能对switch-case的连续值进行查表优化，但如果换到其他编译器呢？而且，如果是连续值，而且连续值执行非常类似的操作的话，是否可以用一个类推逻辑替代switch-case、if-else和造表？因为类推逻辑的时间复杂度也是O(1)，而且还可以动态改变需要匹配的条目和数值。

xinglp

强贴留名，收货很大