代码之家 › 专栏 › 技术社区 › jeanpaul62

记忆一个货币化的函数

memoization javascript

jeanpaul62 · 技术社区 · 7 年前

const f = (arg1) => (arg2) => { /* returns something */ }

是否可以就两个参数(即:

f(1)(2);
f(1)(3); // Cache not hit
f(4)(2); // Cache not hit
f(1)(2); // Cache hit

2 回复 | 直到 5 年前

Parzh from Ukraine 6 年前

你可以休息一下 Map 作为缓存并为以下所有参数获取嵌套映射。

它通过使用一个curried函数和一个可选函数来工作 地图 . 如果没有提供映射,将创建一个新映射,该映射将用作返回的闭包或最终结果的所有其他调用的基本缓存。

内部函数接受单个参数并检查此值是否在映射中。

如果不是,则调用curried函数并检查返回值
- 如果是函数,则在函数上创建一个新闭包和一个新映射,
- 如果没有函数取结果,
作为地图新元素的值。
最后从映射返回值。

const cached = (fn, map = new Map()) => arg => {
    const inCache = map.has(arg);
    const hint = inCache ? 'in cache' : 'not in cache';

    console.log(arg, hint);

    if (!inCache) {
        const value = fn(arg);
        const result = typeof value === 'function' ? cached(value, new Map()) : value;

        map.set(arg, result);
    }

    return map.get(arg);
};

const f = a => b => c => a * b * c; // the original curried function
const g = cached(f); // its cached variant

console.log(g(1)(2)(5)); // not not not 10
console.log(g(1)(3)(4)); //  in not not 12
console.log(g(4)(2)(3)); // not not not 24
console.log(g(1)(2)(6)); //  in  in not 12
console.log(g(4)(2)(3)); //  in  in  in 24

.as-console-wrapper { max-height: 100% !important; top: 0; }

Mark 7 年前

有趣的问题–您可以为每个函数设置独立的缓存。外部函数上的缓存将保存函数。每个内部函数都可以获得自己的独立缓存。这么叫 f(10)(1) f(10)(2) 将导致调用内部函数的缓存版本。使命感将再次命中两个缓存:

function getCachedF() {
  // outer cache holds functions keyed to argument
  let outer_memo = {}  
                
  const f = (arg1) => {
    if (!outer_memo.hasOwnProperty(arg1)) {
      // Create inner function on outer cache
      // each inner function needs its own cache
      // because it will return different values
      // given different outer function calls
      let inner_memo = {}                  
      console.log("outer cache miss")
      
      outer_memo[arg1] = (arg2) => {
        // just a normal memoized function
        // cache is simple key:value pair
        if (!inner_memo.hasOwnProperty(arg2)) {
          console.log("inner cache miss")
          inner_memo[arg2] = arg1 + arg2
        }
        return inner_memo[arg2]
      }
    }
    return outer_memo[arg1]
  }
  return f
}

let f = getCachedF()
// both caches miss
console.log("3+5", f(3)(5))

// cached result
console.log("3+5", f(3)(5))

// only inside cache hit
console.log("3+8", f(3)(8))

// inside cache only hits if both args are the same
console.log("10+8", f(10)(8))

另一种选择是使用包含两个参数组合的键的单缓存,但始终必须调用内部函数。

customcommander 5 年前

这可能不是标准的记忆功能。

cache 用于存储和检索以前结果的函数:

const sum = memo(cache => a => b => cache(`${a}+${b}`, () => a + b));
//               ^^^^^                    ^^^^^^^^^^^  ^^^^^^^^^^^
//               A                        B            C

隐藏物 功能由 memo 作用
(如有必要,记忆功能可以选择不缓存某些结果。)
B cache['1+2'] = 3
C -A 砰这将返回结果。
(因此,我们可以在计算它之前检查它是否已经存在。)

这既支持curried函数和non-curried函数,也支持将函数作为值返回的函数。

这个 备忘录 该功能可实现如下:

const memo = fn => {
  const ns = Symbol();
  const cache = (key, thunk) => cache[ns][key] ??= thunk();
  cache[ns] = {};
  return fn(cache);
};

logical nullish assignment 用于管理缓存的运算符:

a ??= answer()

右侧的表达式将被计算并指定给 a 当且仅当 A. 尚未定义。然后它返回 :

const answer = () => (console.log('returning the answer'), 42);

let a;

a ??= answer();
//=> LOG: returning the answer
//=> 42

a ??= answer();
//=> 42

a ??= 40;
//=> 42

我使用了一个符号来隐藏服务器上的实际缓存集 隐藏物 作用枚举对象的属性时不返回符号:

const foo = {};
const key1 = Symbol();
const key2 = 'bar';

foo[key1] = 42;
foo[key2] = 41;

Object.keys(foo);
//=> ['bar']

Object.entries(foo);
//=> [['bar', 41]]

演示

// curried memoized function
const sum = memo(cache => a => b =>
  cache(`${a}+${b}`,
    () => (console.log(`computing ${a}+${b}â¦`), a+b)));
  
console.log(sum(1)(2));
console.log(sum(1)(2));
console.log(sum(1)(2));

// non-curried memoized function
const mul = memo(cache => (a, b) =>
  cache(`${a}*${b}`,
    () => (console.log(`computing ${a}*${b}â¦`), a*b)));
  
console.log(mul(2, 3));
console.log(mul(2, 3));
console.log(mul(2, 3));

// function-returning function
const deferred_sum = memo(cache => a => b =>
  cache(`${a}+${b}`,
    () => (console.log(`defer computing ${a}+${b}â¦`), () => a+b)));
    
console.log(deferred_sum(1)(2)());
console.log(deferred_sum(1)(2)());
console.log(deferred_sum(1)(2)());

<script>
const memo = fn => {
  const ns = Symbol();
  const cache = (key, thunk) => cache[ns][key] ??= thunk();
  cache[ns] = {};
  return fn(cache);
};
</script>

-1

SashaSemanyuk 6 年前

不能将映射传递给每个函数。

const memoize = fn => {
  const cache = {};
  return (...args) => {
    const curriedFn = fn(...args);
    return (...next) => {
      const key = // generate your key
      if (key in cache) return cache[key];
      return (cache[key] = curriedFn(...next));
    }
  }
}