Fibonacci Implementations (v13)

Revision 13 of this benchmark created on


Setup

// 求值
const Num = 100000;

Test runner

Ready to run.

Testing in
TestOps/sec
Cache Mode
/**
 * 普通递归+缓存优化版
 * 运行结果:
 * [NodeJS] 爆栈的临界值是n在 `[10471-10473]` 左右,time cost 10ms 上下
 */
// const NonPrimitiveModeNum = 100;
let fb_cachelize_call_count = 0
const cacheMap = new Map()
function fb_cachelize(n){
    fb_cachelize_call_count++
    if(n < 2){
        return 1 
    }
    if(cacheMap.has(n)){
        return cacheMap.get(n)
    }else{
        let res = fb_cachelize(n-1) + fb_cachelize(n-2)
        cacheMap.set(n, res)
        return res
    }
}
fb_cachelize(Num);
ready
Iterator Mode
/**
 * 递归改迭代(循环)版
 * 运行结果:
 * [NodeJS] 没有使用栈,纯粹计算耗时,在n=5kw时耗时才达到1s的级别,综合性能最优。
 */ 

function fb_iterator(n){
    if(n < 2){
        return 1
    }
    let results = [1, 1]
    for(let i = 2; i<n+1; i++){
        results[i] = results[i-2] + results[i-1]
    }
    return results[n]
}

fb_iterator(Num);
ready
Tail Call Mode
/**
 * 尾递归版
 * [NodeJS] 爆栈的临界值7390左右,耗时1ms左右(仍然发生爆栈错误说明还是保留了栈,并未完全去栈化)。
 *   其性能明显比非尾递归调用要更好,但是跟迭代版的远不在一个数量级。
 */

let fb_tail_call_count = 0
// (5, 1, 1) , (4, 1, 2), (3, 2, 3), (2, 3, 5), (1, 3, 5), (0, 5, 8)
function fb_tail_call(n, a=1, b=1){
    fb_tail_call_count++
    if(n < 1){
        return a
    }
    return fb_tail_call(n-1, b, a+b) 
}
fb_tail_call(Num);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.