如何使用Map()进行记忆

Question

我目前遇到了 JavaScript 中 memoize 函数的问题。最后 2 个测试未通过。我会非常乐意提供帮助。

问题如下：

• 编写一个 memoize 函数，该函数接受必需的回调函数和可选的解析器函数。 memoize 函数返回回调函数的记忆版本，其定义如下：

• 记忆函数的所有返回值都被缓存。如果使用现有缓存键（如下定义）调用记忆回调，则返回该缓存值，而无需再次调用回调。

• 缓存键是基于可选的解析器函数定义的。如果未提供解析器函数，则缓存键是将存储的函数参数作为数组传递给 JSON.stringify 的结果。如果提供了自定义解析器函数，则应将参数单独传递给该函数，并且其返回值将是缓存键（请注意，这可以是任何类型）。

• memoized 函数还应该有三个方法：clear()：清除缓存。 delete(...args)：删除与传递的参数对应的缓存条目（如果存在）。 has(...args)：如果缓存有与传递的参数相对应的条目，则返回布尔值 true，否则返回 false。为简单起见，您无需担心绑定 this 上下文（即，您可以假设回调不引用 this）。

回调函数如下所示：

const callback = (...args) => args;

这就是输入和应该返回的结果

const memoized = memoize(callback);
memoized(123); // calls callback, returns 123
memoized(123); // returns 123
memoized(123, 'abc'); // calls callback, returns [123, 'abc']

const memoized2 = memoize(callback, args => args[0]);
memoized2(123); // calls callback, returns 123
memoized2(123); // returns 123
memoized2(123, 'abc'); // returns 123
memoized('abc', 123); // calls callback, returns ['abc', 123]
memoized2('abc'); // returns ['abc', 123]

我已将所有参数存储在缓存中，当调用相同的参数时，结果将从缓存中返回。

这是我的代码

function memoize(cb) {
    const memo = new Map();

    return function (...args) {
        const key = JSON.stringify(args);
        if (!memo.has(args)) {
            memo.set(key, cb(...args));
            return memo.get(key);
        }
        return memo.get(key);
    };
}

这是测试

const chai = require("chai");
const spies = require("chai-spies");
const { expect } = chai;

chai.use(spies);
const spy = () => chai.spy(() => {});

const { memoize } = require("../memoize.js");

describe("memoize", () => {
    it("callback without parameters is never called twice", () => {
        const callback = spy(() => {});
        const memoized = memoize(callback);
        expect(callback).to.have.been.called.exactly(0);
        memoized();
        expect(callback).to.have.been.called.exactly(1);
        memoized();
        expect(callback).to.have.been.called.exactly(1);
        memoized();
        memoized();
        expect(callback).to.have.been.called.exactly(1);
    });

    it("callback with a single parameter is handled properly", () => {
        const callback = spy((val) => val * 2);
        const memoized = memoize(callback);
        expect(callback).to.have.been.called.exactly(0);
        const val1 = memoized(1);
        expect(callback).to.have.been.called.exactly(1);
        expect(val1).to.equal(2);

        const val2 = memoized(1);
        expect(callback).to.have.been.called.exactly(1);
        expect(val2).to.equal(2);

        const val3 = memoized(2);
        expect(callback).to.have.been.called.exactly(2);
        expect(val3).to.equal(4);

        const val4 = memoized(2);
        expect(callback).to.have.been.called.exactly(2);
        expect(val4).to.equal(4);

        const val5 = memoized(1);
        expect(callback).to.have.been.called.exactly(2);
        expect(val5).to.equal(2);
    });

    it("has function works as expected", () => {
        const callback = spy((...args) => args);
        const memoized = memoize(callback);

        expect(memoized.has()).to.be.false;
        expect(memoized.has(123)).to.be.false;
        expect(memoized.has(123, "abc")).to.be.false;

        memoized();
        expect(memoized.has()).to.be.true;

        memoized(123);
        expect(memoized.has(123)).to.be.true;

        memoized(123, "abc");
        expect(memoized.has(123, "abc")).to.be.true;

        expect(callback).to.have.been.called.exactly(3);
    });
});

Answer 1

我要给出的解决方案解决了 12 个测试，而不是 3 个，包括您的测试。

试试这个：

const defaultResolver = (...args) => JSON.stringify(args);

export function memoize(fn, resolver = defaultResolver) {
  const cache = new Map();
  const memoized = (...args) => {
    const key = resolver(...args);
    if (cache.has(key)) {
      return cache.get(key);
    }
    const result = fn(...args);
    cache.set(key, result);
    return result;
  };
  memoized.clear = () => cache.clear();
  memoized.delete = (...args) => {
    const key = resolver(...args);
    cache.delete(key);
  };
  memoized.has = (...args) => {
    const key = resolver(...args);
    return cache.has(key);
  }
  return memoized;
}

Answer 2

您实际上非常熟悉代码。只是有一件小事被忽略了。

function memoize(cb) {
    const memo = new Map();

    return function (...args) {
        const key = JSON.stringify(args);

        // Forgot to use the key here in the map
        if (!memo.has(key)) {
            memo.set(key, cb(...args));
            return memo.get(key);
        }
        return memo.get(key);
    };
}

您正在创建一个密钥，然后只需传递参数。

Answer 3

试试这个。它与 LeetCode 配合得很好

    function memoized(func){
      let cache = new Map();
      return function (...args) {
        let key = JSON.stringify(args);
        if (cache.has(key) {
          console.log(`I am from cache`);
          return cache.get(key);
        }
        let result = fn.call(this, ...args);
        cache.set(key,result)
        console.log(`I am first call`);
        return result;
       }
     }