2630. 记忆函数 II
2630. 记忆函数 II
题目
Given a function fn
, return a memoized version of that function.
A **memoized **function is a function that will never be called twice with the same inputs. Instead it will return a cached value.
fn
can be any function and there are no constraints on what type of values it accepts. Inputs are considered identical if they are ===
to each other.
Example 1:
Input:
getInputs = () => [[2,2],[2,2],[1,2]]
fn = function (a, b)
Output: [{"val":4,"calls":1},{"val":4,"calls":1},{"val":3,"calls":2}]
Explanation:
const inputs = getInputs();
const memoized = memoize(fn);
for (const arr of inputs) {
memoized(...arr);
}
For the inputs of (2, 2): 2 + 2 = 4, and it required a call to fn().
For the inputs of (2, 2): 2 + 2 = 4, but those inputs were seen before so no call to fn() was required.
For the inputs of (1, 2): 1 + 2 = 3, and it required another call to fn() for a total of 2.
Example 2:
Input:
getInputs = () => [[{},{}],[{},{}],[{},{}]]
fn = function (a, b) { return ({...a, ...b}); }
Output: [{"val":{},"calls":1},{"val":{},"calls":2},{"val":{},"calls":3}]
Explanation:
Merging two empty objects will always result in an empty object. It may seem like there should only be 1 call to fn() because of cache-hits, however none of those objects are === to each other.
Example 3:
Input:
getInputs = () => { const o =
fn = function (a, b) { return ({...a, ...b}); }
Output: [{"val":{},"calls":1},{"val":{},"calls":1},{"val":{},"calls":1}]
Explanation:
Merging two empty objects will always result in an empty object. The 2nd and 3rd third function calls result in a cache-hit. This is because every object passed in is identical.
Constraints:
1 <= inputs.length <= 10^5
0 <= inputs.flat().length <= 10^5
inputs[i][j] != NaN
题目大意
现给定一个函数 fn
,返回该函数的一个 记忆化 版本。
一个 记忆化 的函数是一个函数,它不会被相同的输入调用两次。而是会返回一个缓存的值。
函数 fn
可以是任何函数,对它所接受的值类型没有任何限制。如果两个输入值在 JavaScript 中使用 ===
运算符比较时相等,则它们被视为相同。
示例 1:
输入:
getInputs = () => [[2,2],[2,2],[1,2]]
fn = function (a, b)
输出:[{"val":4,"calls":1},{"val":4,"calls":1},{"val":3,"calls":2}]
解释:
const inputs = getInputs();
const memoized = memoize(fn);
for (const arr of inputs) {
memoized(...arr);
}
对于参数为 (2, 2) 的输入: 2 + 2 = 4,需要调用 fn() 。
对于参数为 (2, 2) 的输入: 2 + 2 = 4,这些输入之前已经出现过,因此不需要再次调用 fn()。
对于参数为 (1, 2) 的输入: 1 + 2 = 3,需要再次调用 fn(),总共调用了 2 次。
示例 2:
输入:
getInputs = () => [[{},{}],[{},{}],[{},{}]]
fn = function (a, b)
输出:[{"val":{},"calls":1},{"val":{},"calls":2},{"val":{},"calls":3}]
解释:
将两个空对象合并总是会得到一个空对象。尽管看起来应该缓存命中并只调用一次 fn(),但是这些空对象彼此之间都不是 === 相等的。
示例 3:
输入:
getInputs = () => { const o =
fn = function (a, b) { return ({...a, ...b}); }
输出:[{"val":{},"calls":1},{"val":{},"calls":1},{"val":{},"calls":1}]
解释:
将两个空对象合并总是会得到一个空对象。因为传入的每个对象都是相同的,所以第二个和第三个函数调用都会命中缓存。
提示:
1 <= inputs.length <= 10^5
0 <= inputs.flat().length <= 10^5
inputs[i][j] != NaN
解题思路
本道题的难点在于,仅当两个输入值使用 ===
运算符比较时相等被视为相同,因此不能使用 JSON.stringify
来做缓存的 key
,而是要采用一种树形嵌套缓存,以支持对对象引用的严格比较:
- 使用
Map
作为缓存数据结构,支持对对象引用的严格比较。 - 由于 JavaScript 中的对象和数组引用是通过引用来判断相等的,所以我们可以直接将这些引用作为
Map
的键。 - 使用递归地遍历参数,构建一个嵌套的
Map
,每个层级的键都是当前参数的引用。 - 在每个参数的最终
Map
中存储一个特殊的值(如Symbol('__res')
)以表示计算结果。 - 在每层中,检查是否存在结果。如果存在,直接返回;如果不存在,调用原函数并缓存结果。
复杂度分析
- 时间复杂度:
O(n)
,n
是输入参数的数量,但由于缓存机制,实际调用次数通常会更少。 - 空间复杂度:
O(n)
,取决于参数的种类和数量。
代码
/**
* @param {Function} fn
* @return {Function}
*/
function memoize(fn) {
let cache = new Map();
const RES = Symbol('__res');
return function (...params) {
let curCache = cache;
for (let param of params) {
if (!curCache.has(param)) {
curCache.set(param, new Map());
}
curCache = curCache.get(param);
}
if (curCache.has(RES)) return curCache.get(RES);
const result = fn(...params);
curCache.set(RES, result);
return result;
};
}
/**
* let callCount = 0;
* const memoizedFn = memoize(function (a, b) {
* callCount += 1;
* return a + b;
* })
* memoizedFn(2, 3) // 5
* memoizedFn(2, 3) // 5
* console.log(callCount) // 1
*/
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
2623 | 记忆函数 | [✓] | ||
2632 | 柯里化 🔒 | [✓] |