从一段代码看缓存对性能的影响

有段时间,同事出了一些js基础题目,考js基础知识,比如闭包啊、递归算法等等之类的。
其中有一题是计算正整数n的阶乘。
大部分会考虑到用递归方式实现,代码如下:

const factorial = function(n) {
if (n === 1) return n;
return n * factorial(n - 1);
};

是不是标准答案呢?咋一看去,好像没什么问题。

但实际上,拿到浏览器运行

factorial(1000)

就发现扑街了。
输出 Infinity,得到的数值,显然已经超出最大允许范围,直接显示输出Infinity无穷大了。
实际上我试验了一下,到171就已经返回Infinity,无法得到正确的解了。

继续把参数调大,更糟糕了,抛出异常
VM200:1 Uncaught RangeError: Maximum call stack size exceeded

看来原生的方法无法满足较大的数字计算。虽然这个没有多大的实际意义,但我还是好奇,怎么实现计算一个比较大的数的阶乘。

于是,用for循环写了一个方法:

function factorialBig(n)
{
    let m = [1];
    let result;
    for (let i = 1; i <= n; i++) {
        for (let j = 0, k = 0; j < m.length || k != 0; j++) {
            let p;
            if( j < m.length){
                p = i * m[j] + k
            }else{
                p = k
            }
            m[j] = p % 10;
            k = (p - m[j]) / 10;
        }
    }
    result = m.reverse().join('');
    return result;
}

 

原理就是最原始的办法,每次计算把结果保存在数组中,数组中依次保存[个, 十,百,千,万,…]以次类推;

这样,每次都是计算的两位以内的乘法,而且用数组保存,最后输出字符串,就没有了数字类型的长度限制了。

上面的方法,可以计算更大的数了,但是当这个参数非常非常大的时候,估计计算的时间就非常长了。

现在如果我们想看看到底花多长时间,可以来打印出程序运行时间:

function factorialBig(n)
{
    let m = [1];
	let result;  
        let now = + new Date()
    for (let i = 1; i <= n; i++) {
        for (let j = 0, k = 0; j < m.length || k != 0; j++) {
            let p;
            if( j < m.length){
                p = i * m[j] + k
            }else{
                p = k
            }
            m[j] = p % 10;
            k = (p - m[j]) / 10;
        }
    }
            result = m.reverse().join('');
console.log('计算耗时:' + (+new Date() - now));
    return result;
}

好了,来感受下

factorialBig(200)
06:53:32.452 VM943:19 计算耗时:4

factorialBig(2000)
06:53:36.989 VM943:19 计算耗时:52

factorialBig(20001)
06:53:49.050 VM943:19 计算耗时:5502

factorialBig(20002)
06:56:35.323 VM943:19 计算耗时:5649

看看吧,计算五位数已经要花很长的时间了!后面的我真的不敢在测试了,怕把浏览器给卡死了。。。

你会发现,计算耗时几乎是成指数上升的!!

我想到一个问题,使用缓存优化。

于是改写了一下方法:

const factorialBig = function() {
    const cache = {} // cache 作为私有变量封装
    return function(){
        let now = + new Date()
        let result
        if(!arguments.length){
            throw Error('need Number as a argument ')
        }
        const n = arguments[0]
        if(cache && cache[n]){
            result =  cache[n]
        }else{
            let m = [1];
            for (let i = 1; i <= n; i++) {
                for (let j = 0, k = 0; j < m.length || k != 0; j++) {
                    let p;
                    if( j < m.length){
                        p = i * m[j] + k
                    }else{
                        p = k
                    }
                    m[j] = p % 10;
                    k = (p - m[j]) / 10;
                }
            }
            
            result = m.reverse().join('');
            cache[n] = result;
            // return result;
        }
        console.log('计算耗时:' + (+new Date() - now));
        return result
    }
};

在浏览器运行

var f = factorialBig()

f(10001)
07:05:27.225 VM1844:31 计算耗时:1310

然后再输入

f(10001)
07:06:37.653 VM1844:31 计算耗时:0

f(20001)
09:32:56.312 VM2129:31 计算耗时:5525

再次运行:

f(20001)
09:33:07.469 VM2129:31 计算耗时:0

我们在计算输出n的阶乘后,通过缓存保存结果,

下次计算的时候如果命中缓存,直接输出缓存保存的结果,这样节省了大量的运算开销,所以看到耗时时0!

缓存的使用,使得运算快了很多,这就是缓存机制的带来的性能提升。

当然,我们这里的缓存是封装在闭包里面的私有变量,外部是没办法访问到的,这里的缓存,生命周期就是程序的生命周期,在实际中,页面unload生命周期之后会被销毁(也就是刷新页面后会清空),当然,也可以自己在代码中设置该缓存的有效时间。

虽然这里使用的缓存,没有从根本上解决第一次运算的耗时问题,但是却大大提升了第二次计算速度。

在实际的工作中,可能不会遇到要计算这么超出限制的计算题,而且我们还需要考虑缓存是否会超限的问题;毕竟,如果缓存超限,我们也没有办法正常读写缓存了。

但从这段代码,我们能感受到,恰到好处的缓存带来的性能提升。

 

发表评论

记录工作生活点滴。

返回
顶部