是否有通用技术通过使用promise来避免堆栈溢出？

2024-04-29 • 问答

我发现，做到这一点的一种方法是不时地“稍后再做”：

function knowNFactorial(n) {
  return new Promise(function(resolve,reject) {
    n = BigInt(n);

    if (n === 1n) {
      resolve(1n);
    } else {
      if (n % 1000n !== 0n) {
        knowNFactorial(n - 1n).then(v => resolve(n * v));
      } else {
        // just "do it later" once in a while
        setTimeout(() => {
          knowNFactorial(n - 1n).then(v => resolve(n * v));
        },0)
      }
    }
  });
}

knowNFactorial(20000).then(v => console.log("I know its binary representation length is",v.toString(2).length));

// Only do the following inside of Node or Google Chrome developer console:
// knowNFactorial(20000).then(v => console.log("I know it is",v));

但是关于此还有其他通用技术或研究吗？当然，我们不必使用递归来解决factorial(n)，但是如果存在需要递归的问题，并且如果可能发生堆栈溢出，则似乎存在一种技术：在任何可能的堆栈溢出之前，只需再创造一个承诺（并退出递归）。

仅在Node或Google Chrome内部打印出整个结果。如果在代码段内完成操作，则效果可能会不太理想。（可能body包含大数字而没有自动换行的方式太宽了，并且占用了大量内存）：

knowNFactorial(20000).then(v => console.log("I know it is",v));

否则，一种方法就是将其转换为二进制并打印结果的数字长度，如代码段所示。

如果它是factorial(n)的常规递归，则通常在n超过12,000或{{1}以上时，它会在我的Node或Google Chrome上堆栈溢出}}。我刚刚尝试使用上面的代码，将20,000设为n，但这不是问题。

要递归计算阶乘，但要避免最大调用堆栈大小，我们可以使用：

一些微任务

process.nextTick( _ => f(...)) / Promise.then(_ => f(...))或Promise.finally(_ => f(...)) / queueTask(_ => f(...))

（其中process.nextTick用于节点，queueTask用于浏览器）

一些延迟的宏任务

setImmediate或setTimeout甚至setInterval

（节点为setImmediate）

相同的执行上下文

通过踩铃（不会递归堆叠）

明智的选择，从快到慢

如果可能的话，使其非递归
踩脚
然后执行微任务
然后执行宏任务（可能是因为您每次都使事件循环）

function nextTick (n,s,cbk) {
  if (n === 1n) {
    return cbk(s)
  }
  return process.nextTick(() => nextTick(n - 1n,s * n,cbk))
}

function pthen (n,s = 1n) {
  if (n === 1n) {
    return s
  }
  return Promise.resolve().then(() => pthen(n - 1n,s * n))
}

function pfinally (n,cbk) {
  if (n === 1n) {
    return cbk(s)
  }
  // Promise.finally does not return the value and you don't want to use
  // .then (since already covered),so return value by callback
  return Promise.resolve().finally(() => pfinally(n - 1n,cbk))
}

function microtask (n,cbk) {
  if (n === 1n) {
    return cbk(s)
  }
  return queueMicrotask(() => microtask(n - 1n,cbk))
}

function immediate (n,cbk) {
  if (n === 1n) {
    return cbk(s)
  }
  return setImmediate(() => immediate(n - 1n,cbk))
}

function timeout (n,cbk) {
  if (n === 1n) {
    return cbk(s)
  }
  return setTimeout(() => timeout(n - 1n,cbk),0)
}

function interval (n,cbk) {
  // feels like trampolining but letting the engine call us back instead of doing it explicitely
  arg1 = n
  arg2 = s
  const id = setInterval( function () {
    if (arg1 === 1n) {
      clearInterval(id)
      return cbk(arg2)
    }
    arg2 = arg1 * arg2
    arg1 = arg1 - 1n
  },0.01)
}
function tco(n,s = 1n) {
  if (n === 1n) {
    return s
  }
  return tco(n - 1n,s * n)
}
function trampoMain (n) {
  function trampo (n,v = 1n) {
    if (n === 1n) {
      return v
    }
    return _ => trampo(n - 1n,n * v)
  }
  let f = trampo(n)
  while (typeof f === 'function') {
    f = f()
  }
  return f
}

function cbkToProm (f) {
  return n => new Promise((resolve,reject) => f(n,1n,resolve))
}

;(async _ => {
  const methods = {
    pthen,pfinally: cbkToProm(pfinally),trampolining: trampoMain
  }
  if (typeof process === 'object') {
    methods.nextTick = cbkToProm(nextTick)
  }
  if (typeof setImmediate === 'function') {
    methods.setImmediate = cbkToProm(immediate)
  }
  if (typeof queueMicrotask === 'function') {
    methods.queueMicrotask = cbkToProm(microtask)
  }
  // horribly slow
  methods.setTimout = cbkToProm(timeout)
  methods.setInterval = cbkToProm(interval)

  // does not work
  methods.tco = tco

  const N = BigInt(1e9)+7n
  for (const [name,f] of Object.entries(methods)) {
    console.time(name)
    console.log('res',parseInt((await f(2000n)) % N))
    console.timeEnd(name)
  }
})()

关于tco（用于尾部呼叫优化）的一个副节点，我想知道我们是否会神奇地避免最大调用堆栈大小，但似乎不会很快出现（ptc syntax at draft 0）

是否有通用技术通过使用promise来避免堆栈溢出？

dido17 回答：是否有通用技术通过使用promise来避免堆栈溢出？

大家都在问