记忆提供更少的表现，花费更多的时间

Question

我正在FreecodeCamp解决Euler项目。解决问题14时，我会使用递归，并尝试使用记忆来提高性能。但是，如果没有记忆，则需要更少的时间来执行，并且通过记忆需要更多的时间。备忘录实施是正确的吗？此代码有什么问题？有人可以解释吗？

//Memoized version of the longestCollatzSequence project euler
let t1 = Date.now();

// function recurseWrapper(n) {
//     let count = 0;
//     let memo = {}

//     function recurseCollatzSequence(n) {
//         if (n in memo) {
//             return memo[n];
//         } else {
//             if (n === 1) {
//                 return;
//             } else if (n % 2 === 0) {
//                 count++;
//                 memo[n / 2] = recurseCollatzSequence((n / 2))
//             } else {
//                 count++;
//                 memo[(3 * n) + 1] = recurseCollatzSequence(((3 * n) + 1))
//             }
//             return count
//         }

//     }
//     return recurseCollatzSequence(n);
// }

//Without memoization (better performance)

function recurseWrapper(n) {
    let count = 0;

    function recurseCollatzSequence(n) {

        if (n === 1) {
            return;
        } else if (n % 2 === 0) {
            count++;
            recurseCollatzSequence((n / 2))
        } else {
            count++;
            recurseCollatzSequence(((3 * n) + 1))
        }
        return count

    }
    return recurseCollatzSequence(n);
}


function longestCollatzSequence(n) {
    let max = 0;
    let startNum = 0;
    for (let i = n; i > 1; i--) {
        let changeMax = recurseWrapper(i)
        if (changeMax > max) {
            max = changeMax;
            startNum = i;
        }
    }
    return startNum;
}

console.log(longestCollatzSequence(54512))
let t2 = Date.now() - t1;
console.log(`time taken by first instruction ${t2}`);
console.log(longestCollatzSequence(900000));
let t3 = Date.now() - t1 - t2
console.log(`time taken by second instruction ${t3}`);
let t4 = Date.now() - t1 - t2 - t3
console.log(longestCollatzSequence(1000000))
console.log(`time taken by third instruction ${t4}`);

Answer 1

从我对Collat​​z猜想的有限理解，从数字 n 开始时，使用您执行的所有操作，您再也不会看到相同的数字直到达到1（否则您最终会出现在无限循环中）。因此，您的备忘录对象将始终容纳永远不会匹配当前号码 n 的唯一键，因此如果（n中的n中的n中）永远不会是正确的。

实际上，您似乎想在循环中记忆结果 recursewrapper（），以便可以防止已经看到的计​​算结果。目前，您尚未这样做，因为您每次调用 recurseWrapper（）时，要创建一个新的 Memo 对象，以删除所有记忆的值。取而代之的是，您可以返回通过备忘录对象关闭的内部辅助递归包装器功能，以便将一个备忘对象保留在递归包装器功能的所有调用中。

但是，即使如此，我们仍然会面临问题，因为如何计算。例如，如果您调用 recurseWrapper（n），并且需要10个迭代才能调用 recurseCollat​​zSequence（k），则返回的 recurseCollat​​zSequence（k）将为 10 加上计算 k 的Collat​​z序列所需的任何数字。如果我们记住这个数字，我们可能会面临问题。如果我们再次调用 recurseWrapper 在另一个号码 m ， recurseWrapper（m），这次需要20个迭代才能到达相同的呼叫 recurseCollat​​zSequence（k），我们将使用 k 的记忆价值。但是，此值对从 n 到 k 进行的 10 还有一个额外的计数，而不仅仅是所花费的计数从 k 到 1 。结果，我们需要更改您的递归函数中计算 count 的方式，以便它是 pure 相同的结果。

正如文森特（Vincent）也在a ，您应该记住当前号码，即：备忘录[n] ，而不是您将要计算Collat​​z计数的数字（重新浏览时进行了记忆）：

function createCollatzCounter() {
  const memo = {};
  return function recurseCollatzSequence(n) {
    if (n in memo) {
      return memo[n];
    } else {
      if (n === 1) {
        memo[n] = 0;
      } else if (n % 2 === 0) {
        memo[n] = 1 + recurseCollatzSequence(n / 2);
      } else {
        memo[n] = 1 + recurseCollatzSequence((3 * n) + 1);
      }
      return memo[n];
    }
  }
}

function longestCollatzSequence(n) {
  let max = 0;
  let startNum = 0;
  const recurseWrapper = createCollatzCounter();
  for (let i = n; i > 1; i--) {
    let changeMax = recurseWrapper(i)
    if (changeMax > max) {
      max = changeMax;
      startNum = i;
    }
  }
  return startNum;
}

console.time("First");
console.log(longestCollatzSequence(54512));
console.timeEnd("First");
console.time("Second");
console.log(longestCollatzSequence(900000));
console.timeEnd("Second");
console.time("Third");
console.log(longestCollatzSequence(1000000));
console.timeEnd("Third");

相比之下，以下显示没有备忘录的时间：

//Without memoization (better performance)

function recurseWrapper(n) {
    let count = 0;

    function recurseCollatzSequence(n) {

        if (n === 1) {
            return;
        } else if (n % 2 === 0) {
            count++;
            recurseCollatzSequence((n / 2))
        } else {
            count++;
            recurseCollatzSequence(((3 * n) + 1))
        }
        return count

    }
    return recurseCollatzSequence(n);
}


function longestCollatzSequence(n) {
    let max = 0;
    let startNum = 0;
    for (let i = n; i > 1; i--) {
        let changeMax = recurseWrapper(i)
        if (changeMax > max) {
            max = changeMax;
            startNum = i;
        }
    }
    return startNum;
}

console.time("First");
console.log(longestCollatzSequence(54512))
console.timeEnd("First");
console.time("Second");
console.log(longestCollatzSequence(900000));
console.timeEnd("Second");
console.time("Third");
console.log(longestCollatzSequence(1000000));
console.timeEnd("Third");

Answer 2

这是该解决方案的简化版本，在纪念和递归周围具有最小的噪声。

let memo = {};
function collatzSequence(n) {
    if (! (n in memo)) {
        if (n == 1) {
            memo[n] = 1;
        }
        else if ((n % 2) === 0) {
            memo[n] = 1 + collatzSequence(n/2);
        } else {
            memo[n] = 1 + collatzSequence(3*n + 1);
        }
    }
    return memo[n];
}

function longestCollatzSequence(n) {
    let max = 0;
    let startNum = 0;
    for (let i = n; i > 1; i--) {
        let changeMax = collatzSequence(i)
        if (changeMax > max) {
            max = changeMax;
            startNum = i;
        }
    }
    return startNum;
}

console.log(longestCollatzSequence(14))

而且，如果您愿意接受一些高尔夫球，这仍然是第一个功能的较短版本。

let memo = {1: 1};
function collatzSequence(n) {
    if (!(n in memo)) {
        memo[n] = 1 + collatzSequence(0 === n%2 ? n/2 : 3*n+1);
    }
    return memo[n];
}

之所以重要的原因与我们的想法有关。只要代码自然而然地读取，写作和思考它需要多长时间才与它的时间直接相关。 （在许多地方都发现这在多种语言中都是真实的。我知道当然有。）因此，学会对代码进行更有效的思考将使您更快地编写。

这就是为什么在不谈论所使用的技术的情况下学习如何使用技术会使您在这种技术方面更好的原因。

Answer 3

花了一些时间弄清楚，我找到了一个工作解决方案。
以下代码提高了时间复杂性。谢谢大家帮助我。

//Memoized version of the longestCollatzSequence project euler
let memo = {}

function recurseWrapper(n) {
    let count = 0;
    if (n in memo) {
        return memo[n];
    } else {
        function recurseCollatzSequence(n) {
            if (n === 1) {
                return;
            } else if (n % 2 === 0) {
                count++;
                recurseCollatzSequence((n / 2))
            } else {
                count++;
                recurseCollatzSequence(((3 * n) + 1))
            }

            return count

        }
        let c = recurseCollatzSequence(n);
        memo[n] = c;
        return c;
    }

}

function longestCollatzSequence(n) {
    let max = 0;
    let startNum = 0;
    for (let i = n; i > 1; i--) {
        let changeMax = recurseWrapper(i)
        if (changeMax > max) {
            max = changeMax;
            startNum = i;
        }
    }
    return startNum;
}
longestCollatzSequence(14)