黑马程序员技术交流社区

标题: switch和 if-else的效率问题 [打印本页]
作者: 周洋    时间: 2012-3-30 15:25
标题: switch和 if-else的效率问题
switch 和  if-else的效率，如何确保的？
作者: dangfei    时间: 2012-3-30 15:39
一般来说，switch比if效率高，但switch应用有局限性，只能用于int和枚举。
我们从比较次数可以推测出来，从概率上说，if平均要比较n/2次，switch一次就可定位。
lz说的确保效率，不是很明白，比较次数越少，代码效率越高。
作者: 肖发腾    时间: 2012-3-30 15:47
网上查阅了，总结如下：

switch与ifelse的区别：
switch...case与if...else的根本区别在于，switch...case会生成一个跳转表来指示实际的case分支的地址，而这个跳转表的索引号与switch变量的值是相等的。
从而，switch...case不用像if...else那样遍历条件分支直到命中条件，而只需访问对应索引号的表项从而到达定位分支的目的。
具体地说，switch...case会生成一份大小（表项数）为最大case常量＋1的跳表，程序首先判断switch变量是否大于最大case 常量，
若大于，则跳到default分支处理；否则取得索引号为switch变量大小的跳表项的地址（即跳表的起始地址＋表项大小＊索引号），程序接着跳到此地址执行，到此完成了分支的跳转。
//
int main()
{
unsigned int i,j;
i=3;
switch (i)
{
  case 0:
  j=0;
  break;
  case 1:
  j=1;
  break;
  case 2:
  j=2;
  break;
  case 3:
  j=3;
  break;
  case 4:
  j=4;
  break;
  default:
  j=10;
  break;
}

}
用gcc编译器，生成汇编代码（注意，不开编译器优化）
.file "shiyan.c"
.text
.globl main
.type main, @function
main:
leal 4(%esp), %ecx
andl $-16, %esp
pushl -4(%ecx)
pushl %ebp
movl %esp, %ebp
pushl %ecx
subl $20, %esp
movl $3, -8(%ebp)
cmpl $4, -8(%ebp)
ja .L2
movl -8(%ebp), %eax
sall $2, %eax
movl .L8(%eax), %eax
jmp *%eax
.section .rodata
.align 4
.align 4
.L8:
.long .L3
.long .L4
.long .L5
.long .L6
.long .L7
.text
.L3:
movl $0, -12(%ebp)
jmp .L11
.L4:
movl $1, -12(%ebp)
jmp .L11
.L5:
movl $2, -12(%ebp)
jmp .L11
.L6:
movl $3, -12(%ebp)
jmp .L11
.L7:
movl $4, -12(%ebp)
jmp .L11
.L2:
movl $10, -12(%ebp)
.L11:
addl $20, %esp
popl %ecx
popl %ebp
leal -4(%ecx), %esp
ret
.size main, .-main
.ident "GCC: (Ubuntu 4.3.3-5ubuntu4) 4.3.3"
.section .note.GNU-stack,"",@progbits

由此看来，switch有点以空间换时间的意思，而事实上也的确如此。
1.当分支较多时，当时用switch的效率是很高的。因为switch是随机访问的，就是确定了选择值之后直接跳转到那个特定的分支，
但是if。。else是遍历所以得可能值，知道找到符合条件的分支。如此看来，switch的效率确实比ifelse要高的多。
2.由上面的汇编代码可知道，switch...case占用较多的代码空间，因为它要生成跳表，特别是当case常量分布范围很大但实际有效值又比较少的情况，
switch...case的空间利用率将变得很低。
3.switch...case只能处理case为常量的情况，对非常量的情况是无能为力的。例如 if (a > 1 && a < 100)，是无法使用switch...case来处理的。
所以，switch只能是在常量选择分支时比ifelse效率高，但是ifelse能应用于更多的场合，ifelse比较灵活。


作者: 李井山    时间: 2012-3-30 18:28
查的，这个说的很好了。if 语句适用范围比较广，只要是 boolean 表达式都可以用 if 判断；而 switch 只能对基本类型进行数值比较。两者的可比性就仅限在两个基本类型比较的范围内。
说到基本类型的数值比较，那当然要有两个数。然后重点来了——
if 语句每一句都是独立的，看下面的语句：
if (a == 1) ...
else if (a == 2) ...
这样 a 要被读入寄存器两次，1 和 2 分别被读入寄存器一次。于是你是否发现其实 a 读两次是有点多余的，在你全部比较完之前只需要一次读入寄存器就行了，其余都是额外开销。但是 if 语句必须每次都把里面的两个数从内存拿出来读到寄存器，它不知道你其实比较的是同一个 a。
于是 switch case 就出来了，把上面的改成 switch case 版本：
switch (a) {
        case 0:
                break;
        case 1:
}
因为特定的规则，他一开始就知道你要比 a，于是 a 一次性读取，相比 if 节约了很多开销。



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2