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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐关注

› Meteor

› JSLint - a JavaScript code quality tool

› jsFiddle

› D3.js

› WebStorm

推荐书目

› JavaScript 权威指南第 5 版

› Closure: The Definitive Guide

这是一个创建于 1631 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

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

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

2020-06-14 21:56:26 +08:00

@iintothewind 没仔细看你的代码,没学过 `scala` 。
大致思路就是：尾递归 + 缓存。

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

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