当前位置： 文江博客话题详情

如何使这个高阶记忆函数适用于递归函数？

发布于 2025-01-11 08:43:55 字数 1015 浏览 0 评论 0原文

我有一个基本的记忆函数，编写为

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

它不适用于递归调用自身的函数。例如：

const fibonacci = (n) => {
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}

const memoizedFib = memo(fibonacci)
memoizedFib(20)

在斐波那契内部，它仍然进行大量重复计算。

我想避免这种情况的一种方法是将记忆插入到函数的实现中。

const cache = new Map();
const memoFibonacci = (n) => {
  if (memory.has(n)) return memory.get(n);
  if (n <= 1) return 1;
  const result = memoFibonacci(n - 1) + memoFibonacci(n - 2);
  memory.set(n, result);
  return result;
};

我想知道是否有一种方法可以使高阶 util 函数与斐波那契这样的递归函数一起使用？

原文

I have a basic memoization function written as

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

It doesn't work with functions that recursively calls itself. For example:

const fibonacci = (n) => {
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}

const memoizedFib = memo(fibonacci)
memoizedFib(20)

Here inside fibonacci, it still does a lot of duplicate calculations.

I guess a way to avoid that is to insert the memoization into the implementation for the function.

const cache = new Map();
const memoFibonacci = (n) => {
  if (memory.has(n)) return memory.get(n);
  if (n <= 1) return 1;
  const result = memoFibonacci(n - 1) + memoFibonacci(n - 2);
  memory.set(n, result);
  return result;
};

I wonder if there is a way to make the higher order util function work with recursive functions like fibonacci?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（3）

溺深海 2025-01-18 08:43:55

这是一个非记忆递归函数作为基准：

const fibonacci = (n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}

const result = fibonacci(5);

console.log("result:", result);
.as-console-wrapper { max-height: 100% !important }

直接定义一个记忆函数

您可以定义函数和记忆，这将使所有递归调用都使用记忆版本：

它看起来如何

const fibonacci = memo((n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
});

演示

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

const fibonacci = memo((n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
});

const result = fibonacci(5);

console.log("result:", result);
.as-console-wrapper { max-height: 100% !important }

用记忆的内容替换原始内容

您也可以稍后通过替换原始绑定来记忆它。为此，该函数不应定义为 const。这仍然会使将来的调用使用记忆版本：

它看起来如何

let fibonacci = (n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

或

function fibonacci(n) {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

演示

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

let fibonacci = (n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

const result = fibonacci(5);

console.log("result:", result);
.as-console-wrapper { max-height: 100% !important }

警告

请注意，这仅适用于引用您可以控制的绑定的递归函数。并非所有递归函数都是这样。几个例子：

命名函数表达式

例如，如果函数是用本地名称定义的，则只有它可以用来引用自身：

它看起来如何

let fibonacci = function fibonacci(n) {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

演示

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

let fibonacci = function fibonacci(n) {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

const result = fibonacci(5);

console.log("result:", result);
.as-console-wrapper { max-height: 100% !important }

这是因为函数表达式的名称可以在函数体内使用，并且不能从外部覆盖。实际上，它与制作它相同：

let fibonacci = function recursive(n) {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return recursive(n - 1) + recursive(n - 2)
};

fibonacci = memo(fibonacci);

内部函数

它也不适用于使用内部递归助手的函数：

let fibonacci = (n) => {
  const fibonacciHelper = (n) => {
    console.log(`fibonacci(${n})...`);
    if (n <= 1) return 1;
    return fibonacciHelper(n - 1) + fibonacciHelper(n - 2)
  }
  
  return fibonacciHelper(n);
};

fibonacci = memo(fibonacci);

演示

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

let fibonacci = (n) => {
  const fibonacciHelper = (n) => {
    console.log(`fibonacci(${n})...`);
    if (n <= 1) return 1;
    return fibonacciHelper(n - 1) + fibonacciHelper(n - 2)
  }
  
  return fibonacciHelper(n);
};

fibonacci = memo(fibonacci);

const result = fibonacci(5);

console.log("result:", result);
.as-console-wrapper { max-height: 100% !important }

模块/其他范围

如果您无权访问函数的定义，那么您无法真正控制它用于调用自身的绑定。使用模块时最容易看到：

fibonacci.js

index.js

export let fibonacci = (n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}

这不会影响递归函数

import { fibonacci as fib } from "./fibonacci.js"

//assume memo() exists here

let fibonacci = memo(fib);
fibonacci(5);

，因为它仍然从模块范围引用自身。

Here is a non-memoised recursive function as a benchmark:

const fibonacci = (n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}

const result = fibonacci(5);

console.log("result:", result);
.as-console-wrapper { max-height: 100% !important }

Directly define a memoised function

You can define the function and memoise which would make all recursive calls use the memoised version:

How it looks

const fibonacci = memo((n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
});

Demo

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

const fibonacci = memo((n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
});

const result = fibonacci(5);

console.log("result:", result);
.as-console-wrapper { max-height: 100% !important }

Replace original with memoised

You can also memoise it later by replacing the original binding for it. For this to work, the function should not be defined as const. This would still make future calls use the memoised version:

How it looks

let fibonacci = (n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

OR

function fibonacci(n) {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

Demo

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

let fibonacci = (n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

const result = fibonacci(5);

console.log("result:", result);
.as-console-wrapper { max-height: 100% !important }

Warnings

Be aware that this will only work for recursive functions that refer to a binding that you can control. Not all recursive functions are like that. Few examples:

Named function expressions

For example if the function is defined with a local name which only it can use to refer to itself:

How it looks

let fibonacci = function fibonacci(n) {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

Demo

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

let fibonacci = function fibonacci(n) {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
};

fibonacci = memo(fibonacci);

const result = fibonacci(5);

console.log("result:", result);
.as-console-wrapper { max-height: 100% !important }

This is because the name of the function expression is usable in the body of the function and cannot be overwritten from the outside. Effectively, it is the same as making it:

let fibonacci = function recursive(n) {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return recursive(n - 1) + recursive(n - 2)
};

fibonacci = memo(fibonacci);

Inner functions

It would also not work for functions that use an inner recursion helper:

let fibonacci = (n) => {
  const fibonacciHelper = (n) => {
    console.log(`fibonacci(${n})...`);
    if (n <= 1) return 1;
    return fibonacciHelper(n - 1) + fibonacciHelper(n - 2)
  }
  
  return fibonacciHelper(n);
};

fibonacci = memo(fibonacci);

Demo

function memo(func) {
  const cache = new Map()

  return function (...args) {
    const cacheKey = args.join('-')
    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }

    return cache.get(cacheKey)
  }
}

let fibonacci = (n) => {
  const fibonacciHelper = (n) => {
    console.log(`fibonacci(${n})...`);
    if (n <= 1) return 1;
    return fibonacciHelper(n - 1) + fibonacciHelper(n - 2)
  }
  
  return fibonacciHelper(n);
};

fibonacci = memo(fibonacci);

const result = fibonacci(5);

console.log("result:", result);
.as-console-wrapper { max-height: 100% !important }

Modules / other scopes

If you do not have access to the definition of the function, then you cannot really control the binding it uses to call itself. Easiest to see when using modules:

How it looks

fibonacci.js

export let fibonacci = (n) => {
  console.log(`fibonacci(${n})...`)
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}

index.js

import { fibonacci as fib } from "./fibonacci.js"

//assume memo() exists here

let fibonacci = memo(fib);
fibonacci(5);

This will not affect the recursive function since it still refers to itself from the module scope.

回复 原文
流心雨 2025-01-18 08:43:55

注意：这并没有涵盖@VLAZ 的答案中提到的所有可能性。只是陈述一种可能的方式。另外，使用eval()不是一个好主意。

With this we don't have to replace the original function:

function memo(func) {
  const cache = new Map()
  let myFunc = null;
  let funcDef = func.toString().replaceAll(func.name, 'myFunc');
  func = eval(`(${funcDef})`);

  myFunc = function(...args) {
    const cacheKey = args.join('-')

    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }
    return cache.get(cacheKey)
  }

  return myFunc;
}


// Demo
let fibonacci = (n) => {
  console.log(' ', n);
  if (n <= 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2)
}

const memoizedFib = memo(fibonacci);
console.log('memoizedFib(3)');
console.log('result: ', memoizedFib(3));

console.log('memoizedFib(4): ');
console.log('result: ', memoizedFib(4));

// we can still use original fibonacci function
console.log('fibonacci(4): original function ');
console.log('result: ', fibonacci(4));


const sum = (n) => {
  console.log(' ', n);
  if (n <= 1) return 1;
  return sum(n - 1) + n;
}

const memorizedSum = memo(sum);
console.log('memorizedSum(3): ');
console.log('result: ', memorizedSum(3));
console.log('memorizedSum(5): ');
console.log('result: ', memorizedSum(5));

为了支持非箭头函数，我们可以检索它们的代码并使用 eval 将它们转换为箭头函数。

Note: this doesn't cover all the possibilities mentioned in @VLAZ's answer. Just stating one possible way. Also, using eval() is not a good idea.

With this we don't have to replace the original function:

function memo(func) {
  const cache = new Map()
  let myFunc = null;
  let funcDef = func.toString().replaceAll(func.name, 'myFunc');
  func = eval(`(${funcDef})`);

  myFunc = function(...args) {
    const cacheKey = args.join('-')

    if (!cache.has(cacheKey)) {
      const value = func(...args)
      cache.set(cacheKey, value)
      return value
    }
    return cache.get(cacheKey)
  }

  return myFunc;
}


// Demo
let fibonacci = (n) => {
  console.log(' ', n);
  if (n <= 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2)
}

const memoizedFib = memo(fibonacci);
console.log('memoizedFib(3)');
console.log('result: ', memoizedFib(3));

console.log('memoizedFib(4): ');
console.log('result: ', memoizedFib(4));

// we can still use original fibonacci function
console.log('fibonacci(4): original function ');
console.log('result: ', fibonacci(4));


const sum = (n) => {
  console.log(' ', n);
  if (n <= 1) return 1;
  return sum(n - 1) + n;
}

const memorizedSum = memo(sum);
console.log('memorizedSum(3): ');
console.log('result: ', memorizedSum(3));
console.log('memorizedSum(5): ');
console.log('result: ', memorizedSum(5));

To support non-arrow functions we can retrieve their code and convert them to arrow functions using eval.

回复 原文
走野 2025-01-18 08:43:55

当参数未以独特方式字符串化或其中包含连字符时，记忆功能将无法正常工作

@trincott 的参数时，记忆功能将无法正常工作，解决方案是使用 <我在下面演示的基于代码>映射的“链接列表”

@VLAZ已经涵盖了记忆化，并强调，这个答案只是简单地保存各种类型的参数可能存在于列表中论点

let unknown=Symbol(null) //a symbol for a value NOT EXISTING
/*example structure of list(the only known arguments are [], [5,9] and [5,2]):
OBJECT{
  value:'nothing',
  next:MAP{
    5:OBJECT{
      value:unknown, //[5] isn't a recorded argument
      next:MAP{
        9:OBJECT{
          value:59,
          next:MAP{}
        },
        2:OBJECT{
          value:52,
          next:MAP{}
        }
      }
    }
  }
}
yes, so the result for arguments [arg1,arg2,arg3] would be list->arg1->arg2->arg3
*/
function read(args,head){ 
  for(let i=0;i<args.length;i++){
    if(!(head=head.next.get(args[i]))){return false}
  }
  return head.value!==unknown?head:false
}
function write(args,head,value){
  for(let i=0;i<args.length;i++){
    let nextPathValue=head.next.get(args[i])
    if(!nextPathValue){
      head.next.set( args[i],{value:unknown,next:new Map()} )
      head=head.next.get(args[i])
    }
    else{head=nextPathValue}
  }
  return head.value=value
}
function memo(func) {
  const list = {value:unknown,next:new Map()}
  return function () {
    let existing=read(arguments,list)
    if (!existing) {
      return write(arguments,list,func(...arguments))
    }
    return existing.value
  }
}
const fibonacci = (n) => {
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}
let memoFibonacci=memo(fibonacci)
console.log(memoFibonacci(5))

that memoization function will not work well when there are argument(s) that do not stringify in a unique way, or have hyphens in them

@trincott is right and a solution to that would be to have a Map based "linked list" of sorts which I demonstrate below

@VLAZ already covered the memoization and to emphasise, this answer is simply to hold the various types of arguments that may exist in a list of arguments

let unknown=Symbol(null) //a symbol for a value NOT EXISTING
/*example structure of list(the only known arguments are [], [5,9] and [5,2]):
OBJECT{
  value:'nothing',
  next:MAP{
    5:OBJECT{
      value:unknown, //[5] isn't a recorded argument
      next:MAP{
        9:OBJECT{
          value:59,
          next:MAP{}
        },
        2:OBJECT{
          value:52,
          next:MAP{}
        }
      }
    }
  }
}
yes, so the result for arguments [arg1,arg2,arg3] would be list->arg1->arg2->arg3
*/
function read(args,head){ 
  for(let i=0;i<args.length;i++){
    if(!(head=head.next.get(args[i]))){return false}
  }
  return head.value!==unknown?head:false
}
function write(args,head,value){
  for(let i=0;i<args.length;i++){
    let nextPathValue=head.next.get(args[i])
    if(!nextPathValue){
      head.next.set( args[i],{value:unknown,next:new Map()} )
      head=head.next.get(args[i])
    }
    else{head=nextPathValue}
  }
  return head.value=value
}
function memo(func) {
  const list = {value:unknown,next:new Map()}
  return function () {
    let existing=read(arguments,list)
    if (!existing) {
      return write(arguments,list,func(...arguments))
    }
    return existing.value
  }
}
const fibonacci = (n) => {
  if (n <= 1) return 1
  return fibonacci(n - 1) + fibonacci(n - 2)
}
let memoFibonacci=memo(fibonacci)
console.log(memoFibonacci(5))

回复 原文
~没有更多了~

关于作者

烟雨凡馨

暂无简介

文章
评论
26 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

微信用户

文章 0 评论 0

小情绪

文章 0 评论 0

追我者格杀勿论

文章 0 评论 0

ゞ记忆︶ㄣ

文章 0 评论 0

笨死的猪

文章 0 评论 0

彭明超

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文