我在 freecodecamp 中解決專案 euler。在解決問題 14 時，我使用遞回并嘗試使用記憶來提高性能。但是，如果沒有 memoization，它會花費更少的時間來執行，而有了 memoization，它會花費更多時間。記憶化實作是否正確？這段代碼有什么問題？誰能解釋一下？
//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}`);
uj5u.com熱心網友回復：
根據我對 collat??z 猜想的有限理解，當從一個數字開始時n，通過你所做的所有操作，在你達到 1 之前你不應該再次看到相同的數字（否則你會陷入無限回圈）。因此，您的memo物件將始終擁有永遠不會匹配當前 number 的唯一鍵n，因此if (n in memo)永遠不會是真的。
實際上，您似乎想記住您的結果recurseWrapper()，以便在回圈中進一步呼叫，這樣您就可以防止計算您已經看到的結果。目前您沒有這樣做，因為您memo每次呼叫時都會創建一個新物件recurseWrapper()，從而洗掉所有記憶值。您可以改為回傳關閉memo物件的內部輔助遞回包裝函式，以便為遞回包裝函式的所有呼叫保留一個備忘錄物件。
但即便如此，我們仍將面臨問題，因為它是如何count計算的。例如，如果您呼叫recurseWrapper(n)并且呼叫 需要 10 次迭代recurseCollatzSequence(k)，則回傳的計數recurseCollatzSequence(k)將10加上計算 Collat??z 序列所需的任何數字k。如果我們記住這個數字，我們可能會遇到問題。如果我們再次呼叫 recurseWrapper另一個數字m, recurseWrapper(m)，這一次需要 20 次迭代才能達到相同的呼叫recurseCollatzSequence(k)，我們將使用我們記憶的值k。但是這個值包含一個額外的計數，用于10從 to 獲取n，k而不僅僅是從kto獲取的計數1。因此，我們需要改變您的計算方式count在您的遞回函式中，使其為pure，以便呼叫具有相同引數的函式始終產生相同的結果。
正如文森特在評論中指出的那樣，您應該記住當前的數字，即：memo[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");uj5u.com熱心網友回復：
在花了一些時間弄清楚后，我找到了一個可行的解決方案。下面的代碼提高了時間復雜度。謝謝大家幫助我。
//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)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/487929.html
標籤：javascript 算法 递归 优化 记忆
上一篇：CSS/Javascript：用角上的小矩形標記單擊的形狀
下一篇：通用物件屬性