# [LeetCode 70] 从爬楼梯简单谈谈执行性能

爬楼梯这个问题,其实思路是很明确的:爬到当前楼梯的方法数 = 爬到上一级楼梯(然后再爬一级,只有这一种选择)的方法数 + 爬到上两级楼梯(然后再爬两级,只有这一种选择)的方法数,也就是:

这个其实是老生常谈了,它其实就是著名的斐波那契数列,可以循环或者递归求解,也可以用dp来剪枝,然后进一步对dp的数组进行优化(所谓的滚动数组),乃至矩阵快速幂、通项公式,或者更极端的直接打表(如果指定范围的话),就不一一解释了。

这里举个求通项公式的例子。我们可以看到这样一段代码:

function climbStairs(n: number): number {
  return (
    (((1 + Math.sqrt(5)) / 2) ** (n + 1) -
      ((1 - Math.sqrt(5)) / 2) ** (n + 1)) /
    Math.sqrt(5)
  );
}

可以看到,这段代码里有大量的重复计算,比如重复了三次的Math.sqrt(5)。但是,这段代码的执行结果,有时候却比不重复计算的快:

function climbStairs(n: number): number {
  const sqrt5 = Math.sqrt(5);
  return (((1 + sqrt5) / 2) ** (n + 1) - ((1 - sqrt5) / 2) ** (n + 1)) / sqrt5;
}

这个其实牵涉到V8的一些机制。V8作为著名的JIT引擎,会对“热点代码”进行编译,转化成汇编代码。也就是说,反复执行的代码就有概率会被编译成汇编;反复执行就是为了提醒v8,我这个代码你可以优化。即使是重复执行几次这种级别的汇编码,也比只执行一次的需要翻译的JS代码要快。这其实是很有意思的一件事,我在之前的文章里稍微提过一点。

但是整个过程是不能控制的,具体是否会被编译,如何编译,我们都无法控制,类似于数据库的优化器,以及cpp的inline机制,只是一个“请求”而已。并且,如果由于种种原因,编译过的代码被放弃,会造成大量的反优化的开销。所以为了稳定考虑,一般还是会提取一个变量来避免重复运算;毕竟我们不能把宝押在JS引擎上,不是吗。

最后更新于: 6/25/2020, 2:10:06 PM