如何榨干机器的最后一丝性能——leetcode实例

[boji123]

• 在计算机中的优化，算法的提升对复杂度的影响最大，但是同等复杂度下的性能优劣也不可忽视，这里简单总结几点代码中的优化细节。

• leetcode第7题：输入一个整形，返回这个整形的反转

  7. Reverse Integer
  Total Accepted: 180058
  Total Submissions: 759486
  Difficulty: Easy
  Contributors: Admin
  Reverse digits of an integer.
  
  Example1: x = 123, return 321
  Example2: x = -123, return -321

• 这一题乍一看十分简单，噌噌噌写好，心想一天一道算法今天这么快就收工了：

  input : x
  
  int reverse=0;
  for(int num;x;x/=10)
  {
    num=x%10;
    reverse=reverse*10+num;
  }
  return reverse;

• 提交不通过，发现没有考虑负数
• 考虑负数后再次提交仍然不通过，发现没有考虑溢出

• 考虑溢出后增加了许多判断条件，代码变得臃肿：

  class Solution 
  {
    public:
        int reverse(int x) 
        {
            int max=2147483647;//有符号int最大值
            int min=-2147483648;//有符号int最小值
            //转换为正数
            if(x==min)return 0;//x=mix不方便去符号，手动判断排除
            bool sign=x>0?true:false;
            if(sign==false)x=-x;
  
            int reverse=0;
            for(int num,tmp;x;x/=10)
            {
                num=x%10;
                tmp=reverse*10+num;
                if(reverse<=(max-num)/10) //a*b+c>max=>a>(max-c)/b
                {
                    reverse=tmp;
                }
                else
                {
                    return 0;
                }
            }
            return sign?reverse:-reverse;
        }
    };

• 提交后发现时间不是最优的，因此有优化空间，分析如下：
  • max与min会被多次访问，而其本身又是一个常量，如果放于函数中反复声明相比声明为类的常量消耗更多的机器周期（访问需要一次寻址，而声明并赋值又多了两次操作，对于1000个测试用例则多了2000次操作，这里只是粗略估计）
  • if(reverse<=(max-num)/10) //a*b+c>max=>a>(max-c)/b 这一行判断溢出的运算需要一次比较、额外的临时变量的一次赋值、一次减法、一次除法，因此相对复杂，而溢出问题只有在数字为10位时才会产生，因此如果可以维护一个计数器计数位数，仅当计数器在10时判断溢出，就可以减少9次乘法运算、9次赋值，然后再进入溢出判断

• 优化后代码如下：

  class Solution 
  {
    public:
        const int max=2147483647;//有符号int最大值
        const int min=-2147483648;//有符号int最小值
        int reverse(int x) {
            //转换为正数
            if(x==min)return 0;//x=mix不方便去符号，手动判断排除
            bool sign=x>0?true:false;
            if(sign==false)x=-x;
  
            int reverse=0;
            for(int num,tmp,count=0;x;x/=10)
            {
                num=x%10;
                if(++count==10)//减少判断频率节约时间，只有在长度在10位才有可能溢出
                {
                    tmp=reverse*10+num;
                    if(reverse<=(max-num)/10) //a*b+c>max=>a>(max-c)/b
                    {
                        reverse=tmp;
                    }
                    else
                    {
                        return 0;
                    }
                }
                else
                {
                    reverse=reverse*10+num;
                }
            }
            return sign?reverse:-reverse;
        }
    };

• 计算没有溢出判断时循环内的效率：一次判断、一次除法、一次求余、一次乘法、一次加法、两次赋值
• 有溢出判断时循环内的效率：两次判断、两次除法、一次乘法、一次加法、一次减法、一次求余、三次赋值，相比没有溢出判断多了一次判断、一次除法、一次减法、一次赋值
• 优化后的循环内效率：两次判断、两次加法、一次除法、一次求余、一次乘法、两次赋值，外加平均0.1份的(10位数只有最后一位会这样)一次赋值、一次减法、一次除法、一次判断，相比没有溢出判断多出了：一次判断、一次加法，平均0.1份的一次赋值、一次减法、一次除法、一次判断，性能明显优于优化前。
• 优化后时间基本达到最优（事实上仍然存在优化空间，比如加一个前置判断输入是否为10位，分支进入有溢出判断和无溢出判断的循环中，但这会导致代码体积继续增大）
• 总结
  • 这里只是一个很粗略的介绍，最然程序好坏算法占大头，但是细节也很重要，虽然O(n)和O(2n)是一个级别的，但是运行时间却相差一倍。
  • 大部分的优化会影响可读性，因此建议如果没有苛刻的性能要求，仅优化不影响可读性的部分，比如const int max的声明，这也是一种良好编码习惯。
  • 对于性能优化需要十分熟悉每个操作与机器周期的关系，但是实际运用中CPU与编译器会对你的代码做不同程度的优化，所以估计值和最终结果有出入
  • 看似简单的算法也应当认真对待、仔细考虑边界问题，否则会导致整个工程十分脆弱。在实际工程中不会有如此严密的测试用例，边界考虑是否完善也是区分一个工程师好坏的重要标准
  • 虽然这里可以使用长整形来检测溢出提高效率，但是实际应用中总是会遇到溢出的，这没有解决根本问题。

[beiweiqiang]

看了其他的，发现 JavaScript 最慢了。。。

[YunaQiu]

脚本语言本来就快不了，所以脚本很少拿来跑大数据量的运算。不过真要比的话，PHP好像比JS更慢吧。。。（虽然这两个也没啥可比性）