Chinaunix

标题: 能否动态实现case语句 [打印本页]

作者: songtebo 时间: 2009-04-17 00:37
标题: 能否动态实现case语句
如下代码速度很快

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 时间: 2009-04-17 00:37
不知道你研究过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 时间: 2009-04-17 09:21
不知道用std::map<int,int>会不会更好一些:wink:

作者: songtebo 时间: 2009-04-17 09:29
试验过，std::map<int,int>比自己写的二分查找方法速度还慢一点点。

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

作者: action08 时间: 2009-04-17 09:40
这个优化太底层了

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

作者: marxn 时间: 2009-04-17 09:54
为啥不用hashtable

作者: songtebo 时间: 2009-04-17 10:23

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

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

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

思想 ...

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

非常感谢大家！！

作者: swxlion 时间: 2009-04-17 16:06
标题: 静态？动态？
不太清楚楼主所言“动态”是何意思？如果是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 时间: 2009-04-17 19:08
强贴留名，收货很大

作者: converse 时间: 2009-04-17 23:43
如果分支仅在这么小的范围内,而且你这么在意性能,为啥不用hash表呢.每个hash表以分支的数据为下标,存储的是函数指针.

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)