我们经常用if elseif else这种条件语句去做分支处理,之前遇到这种语句时就有点困惑,哪种条件语句放前面,哪种放后面,不同顺序是否有计算量和效率上的不同?在计算量小的时候,其实分别是不大的,但是随着代码量的不断增多,运算量越来越大,特别是将来大数据和机器学习等海量数据处理的时候,算法的优势就更加明显.Ps: alphaGo Zero用的处理器只有alphaGo的十分之一,算力不强大,但算法的优势却一举让它成功打败阿尔法狗,也印证了算法之于算力的关系,可见算法的重要性.这次用一个小例子来说明代码的计算量优化的问题.
假设我们有两个箱子,每个箱子里有从1到10一共10个球,同时从两个箱中分别取一个球,如果两个数都大于8,则中奖.现在要写一个代码,判断是否中奖.
思路:我们知道中奖的概率是(2/10)^2=0.04,是一个小概率事件,所以我们分别从两个方向来统计代码的计算量,一个从大概率开始判断,一个从小概率开始判断.
从大概率开始判断
//运算次数初始化 $times = 0; //先判断大概率事件 for ($i=1;$i<=10;$i++) { for ($j=1;$j<=10;$j++) { if ($i<=8 && $j<=8) { //如果两个数都小于等于8,则这次判断的运算量为3,运算量+3 $times += 3; } elseif ($i<=8 && $j>8) {/*如果第一个数小于等于8第二个数大于8,则这次判断的计算量为5 (因为它首先判断了自己不符合上一个条件都小于8的情况,此时计算量为3,然后在这里又做了 一个计算量为3的第二次判断,所以总共的计算量为6)*/ $times += 6; } elseif ($i>8 && $j<=8) {/*到达这里用了7次运算,这里第一个数大于8,所以在到达第一个条件时 的第一个判断时就为假,而由于php的短路与机制,后面的第二个判断就没有执行,所以第一个条件 执行了2次运算,同理,第二个条件也执行了2次运算,到达本条件时执行了3次运算,所以一共是7次运算*/ $times += 7; } else {//到这里一共经历了2+2+2=6次判断 $times += 6; } } } echo $times; //输出运算量,一共424次运算
从小概率开始判断
$times = 0; //先判断小概率事件 for ($i=1;$i<=10;$i++) { for ($j=1;$j<=10;$j++) { if ($i>8 && $j>8) { //如果两个数都大于8,则这次判断的运算量为3,运算量+3 $times += 3; } elseif ($i>8 && $j<=8) { /*如果第一个数大于8第二个数小于等于8,则这次判断的计算量为6 (因为它首先判断了自己不符合上一个条件都小于8的情况,此时计算量为3,然后在这里又做了 一个计算量为3的第二次判断,所以总共的计算量为6)*/ $times += 6; } elseif ($i<=8 && $j<=8) { /*到达这里用了7次运算,这里第一个数小于等于8,所以在到达第一个条件时 的第一个判断时就为假,而由于php的短路与机制,后面的第二个判断就没有执行,所以第一个条件 执行了2次运算,同理,第二个条件也执行了2次运算,到达本条件时执行了3次运算,所以一共是7次运算*/ $times += 7; } else { //到这里一共经历了2+2+2=6次判断 $times += 6; } } } echo $times; //652次判断
可以看出,从概率大的条件开始判断时,运算的次数要少,在这个案例中少20%,也就是说节约了20%的算力,如果是线性的话,则提升了25%的性能.
我们反过来试一试,假设两个球都小于2的时候为中奖,分别按大小概率实验一下.
小概率
$times = 0; //先判断小概率事件 for($i=1;$i<=10;$i++){ for($j=1;$j<=10;$j++){ if($i<=2 && $j<=2){ $times += 3; }elseif($i<=2 && $j>2){ $times += 6; }elseif($i>2 && $j<=2){ $times += 7; }else{ $times += 6; } } } echo $times; //496次判断
大概率
$times = 0; //先判断大概率事件 for($i=1;$i<=10;$i++){ for($j=1;$j<=10;$j++){ if($i>2 && $j>2){ $times += 3; }elseif($i>2 && $j<=2){ $times += 6; }elseif($i<=2 && $j<=2){ $times += 7; }else{ $times += 6; } } } echo $times; //412次判断
可以看到,从大概率开始判断仍然 比 从小概率开始判断 节省了算力,在这个案例中,节省了约19%.
但是,可以看出,无论是大概率还是小概率,以2为分界线的运算量 比 以8为分界线的运算量更少.
412/496 vs. 424/652,虽然中奖概率都是一样的.这是个很有意思的问题.
大概的原因是,从一开始判断的顺序问题,因为数字是从1到10这样排列的,而下面的方法从小数字开始判断的,所以就很容易进入前面的分支,节约了一些算力.
思考:
1, 大概率;
2, 顺着数字变化的方向来判断---所以在指定获奖规则的时候可以参考顺着数字变化顺序来;
3, 逻辑或(还有 or die这种),逻辑与的短路问题,节约时间.