この大きな階乗関数を高階関数に変換するにはどうすればよいですか?

debugcn 投稿 Dev

素晴らしき世界

次のコードはcache、factorial関数の外部でオブジェクトを使用しています。factorial関数自体は階乗とキャッシュを見つけるあまりにも多くの関心を持っている大規模です。

このコードを高階関数に変換し、呼び出したときに同じ結果を生成するにはどうすればよいですか

console.log(factorial(5));
console.log(factorial(7));

cache = { }

function factorial(n) {
  
  if (n === 0) {
    return 1;
  }
  
  if (cache[n])
  {
    return cache[n];
  }
  
  console.log("Stack Up: " + n);
  
  var value = n * factorial(n - 1);
  
  console.log("Stack Down: " + value);
  
  cache[n] = value;
  
  return value;
}

console.log(factorial(5));
console.log(factorial(7));

ありがとうございました

再帰関数を記憶するための他の答えはすでにありますが、その答えをjavascriptの階乗に適応させて、より簡単に機能する方法を確認できるようにします

memoized 再帰関数を書く秘訣は、継続渡しスタイルです。非末尾再帰関数をスタックセーフにする場合にも、同様の手法が機能します。

console.logこの最初の例にいくつかのステートメントを残して、実際に計算を行っているときと、メモ検索を行っているときを確認できるようにします。

const memoise = f => {
  const memo = new Map()
  const compute = (x, k) =>
    (console.log('compute', x),
    memo.get(x, memo.set(x, f(x,k))))
  const lookup = x =>
    (console.log('lookup', x),
    memo.has(x) ? memo.get(x) : compute(x, lookup))
  return lookup
}

const factk = (x, k) => {
  if (x === 0)
    return 1
  else
    return x * k(x - 1)
}

const memfact = memoise(factk)

console.log(memfact(5)) // 120
console.log(memfact(7)) // 5040

ここでは、console.log内部の呼び出しを削除し、memoise代わりにメモ化されたフィボナッチ関数とメモ化されていないフィボナッチ関数を示しています。劇的な時間差の比較の間memoise(fibk)とbadfib

const memoise = f => {
  const memo = new Map()
  const compute = (x, k) =>
    memo.get(x, memo.set(x, f(x,k)))
  const lookup = x =>
    memo.has(x) ? memo.get(x) : compute(x, lookup)
  return lookup
}

const fibk = (x, k) => {
  if (x < 2)
    return x
  else
    return k(x - 1) + k(x - 2)
}

const badfib = x => {
  if (x < 2)
    return x
  else
    return badfib(x - 1) + badfib(x - 2)
}

console.time('memoised')
console.log(memoise (fibk) (35)) // 9227465 1.46ms
console.timeEnd('memoised')

console.time('unmemoised')
console.log(badfib(35))          // 9227465 135.85ms
console.timeEnd('unmemoised')

この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。

侵害の場合は、連絡してください[email protected]