C语言switch
很久很久以前，我在某本书看到C里面的switch是跳转表实现的，效率比ifelse高。
想想switch的参数都是可以转化成int的那种觉得也是正确的。然后我就可以到处炫耀说我知道switch的效率比ifelse高，因为他是跳转表实现的不用每次比较。
然后晚上的时候小马问我为什么switch不可以是string，下意识说出跳转表。。但是突然又感觉不对了。
为什么呢，case x:所有的x是连续的那好说，但是如果x差别很大呢，比如1 2 3 4 97 98 100 1000这样呢？
难道要开那么大的表？想也知道肯定不是，但是上网查发现大部分人说的都是跳转表。
然后就自己试验一下看，反正汇编还是看得懂的。
ifelse
首先这样的代码
switch(x)
{
case 1:
x += 1; break;
case 2:
x += 2; break;
case 3:
x += 3; break;
default:
x += x;
}
得到的汇编代码是：
cmpl $2, %eax ; 先比较第二个case
je .L4
cmpl $3, %eax
je .L5
cmpl $1, %eax ; 第一个case留到最后
jne .L8
怎么变成ifelse一样了。开始我还很兴奋地想，我发现switch不是跳转表实现的我好厉害。。
实际上是gcc在处理小于4个case的时候就用ifelse方法实现了，想想这样挺正常的，就像实现归并排序的时候当数量小到一定程度就直接用冒泡反而还快。
跳转表
我试了4个case的情况。结果是二分，二分后面说。
然后是5个case的时候，出现跳转表了！
cmpl $5, %eax
ja .L2
movl .L8(,%eax,4), %eax
jmp *%eax
.section .rodata
.align 4
.align 4
.L8:
.long .L2 ; L2 是 default
.long .L3 ; 对应case 1：
.long .L4 ; 对应case 2:
.long .L5 ; 3:
.long .L6 ; 4:
.long .L7 ; 5:
.text
跳转表填充
然后如果稍微把case的值隔开呢？
; case 分别为 1 2 3 4 8
cmpl $8, %eax
ja .L2
movl .L8(,%eax,4), %eax
jmp *%eax
.section .rodata
.align 4
.align 4
.L8:
.long .L2
.long .L3
.long .L4
.long .L5
.long .L6
.long .L2
.long .L2
.long .L2
.long .L7
.text
结果是4和8之间都用default的表填充了。
二分查找
然后我把case的值换成1 2 3 4 100。结果汇编中出现二分查找了，太长就懒得贴汇编代码了。
虽然二分没有直接跳转快但是时间效率也有O(logN)的，依旧帅气，而且空间节约了。
END
总得来说C里面的switch分别是用遍历，跳转表，二分三种方法实现的。具体取决于case的情况。
但是！至少我现在还没有见到那么长的switch可以让跳转表或者二分的优势体现出来啊。
有时候还真不能人云亦云，自己去试验一下看看代码什么的最靠谱。
PS. 还有一个东西，就是switch的时候如果第一个命中的话效率是最慢的，第二个是最快的！看第一个例子的汇编代码就知道了。
PSS. Go里面是支持string之类的表达式的，文档里也说了他实际上是ifelse的实现。