V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
Meteor
JSLint - a JavaScript code quality tool
jsFiddle
D3.js
WebStorm
推荐书目
JavaScript 权威指南第 5 版
Closure: The Definitive Guide
JayLin1011
V2EX  ›  JavaScript

一个失败的 「Fibonacci Number」,想请教下为什么代理没有「正确使用」递归内部的缓存结果。

  •  
  •   JayLin1011 · 2020-06-14 07:18:10 +08:00 · 2145 次点击
    这是一个创建于 1383 天前的主题,其中的信息可能已经有所发展或是发生改变。
    const tailFibonacci = (n, y = 1, result = 1) =>
      n <= 1 ? result : tailFibonacci(n - 1, result, y + result);
    
    const proxyFibonacci = new Proxy(tailFibonacci, {
      apply(target, context, [n, ...args]) {
        !Reflect.has(target, 'cache') && Reflect.set(target, 'cache', new Map());
    	
        const cache = Reflect.get(target, 'cache');
    
        return cache.has(n)
          ? cache.get(n)
          : cache.set(n, Reflect.apply(target, context, [n, ...args])).get(n);
      },
    });
    
    console.log(proxyFibonacci(1));
    console.log(proxyFibonacci(2));
    console.log(proxyFibonacci(3));
    console.log(proxyFibonacci(4));
    console.log(proxyFibonacci(5));
    console.log(proxyFibonacci(5));
    console.log(proxyFibonacci(5));
    
    
    4 条回复    2020-06-14 21:56:26 +08:00
    calmzhu
        1
    calmzhu  
       2020-06-14 10:03:15 +08:00
    在你的每个 console.log 下面加一行这个
    console.log(tailFibonacci['cache'])
    你就发现递归链实际是断的。

    看倒数第三行。调用的是 Reflect.apply 。 也就是原来的未代理的 tailFibonacci 。
    也就是除非显示跑 1,2,3....99 的 proxyFibonacci(n)的全部。
    直接加一个 proxyFibonacci(100)的化.在 100 里面就直接跳转到 tailFibonacci ( 100 )上去了。所以递归链走的是 tailFibonacci 而非期望的 proxyFibonacci
    iintothewind
        2
    iintothewind  
       2020-06-14 11:20:48 +08:00
    没仔细看你的代码, 附上一段我之前 scala 写的递归版:
    def fibonacci(n: Int): Int = {
    @tailrec
    def fibTail(n: Int, a: Int, b: Int): Int = n match {
    case 0 => a
    case _ => fibTail(n - 1, b, a + b)
    }

    fibTail(n, 0, 1)
    }
    JayLin1011
        3
    JayLin1011  
    OP
       2020-06-14 21:54:23 +08:00
    @calmzhu 你说的对,这里只是缓存了部分计算结果,递归到代理。
    我的初衷是递归的时候原函数先尝试获取缓存,没有命中才真正执行计算,所以自以为每次递归原函数也会经过代理。
    但我尝试递归代理也没能真正读取到,感觉代理不适合这个场景。
    目前成功的方式是不用代理,将缓存和功能实现在原函数内部耦合。
    ```js
    let count = 0;
    const fibonacci = (N, cache = new Map()) => {
    cache.set(0, 1).set(1, 1);

    if (N <= 1) {
    return 1;
    }

    const memorize = n => {
    if (cache.has(n)) {
    count++;

    return cache.get(n);
    }

    return cache.set(n, memorize(n - 1) + memorize(n - 2)).get(n);
    };

    return memorize(N);
    };

    console.log(fibonacci(1));
    console.log(fibonacci(2));
    console.log(fibonacci(3));
    console.log(fibonacci(4));
    console.log(fibonacci(5));

    console.log('缓存命中数:', count);

    ```
    JayLin1011
        4
    JayLin1011  
    OP
       2020-06-14 21:56:26 +08:00
    @iintothewind 没仔细看你的代码,没学过 `scala` 。
    大致思路就是:尾递归 + 缓存。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3223 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 12:01 · PVG 20:01 · LAX 05:01 · JFK 08:01
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.