I was solving project euler in freecodecamp. When solving problem no 14 i use recursion and tried to increase the performance using memorization. But without memoization it is taking less time to execute and with memoization it is taking more time. Is memoization implementation is correct? What is wrong with this code? Can any one explain?
//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}`);
CodePudding user response：
From my limited understanding of the collatz conjecture, when starting at a number n, with all of the operations that you do, you should never see the same number again until you reach 1 (otherwise you would end up in an infinite loop). So your memo object will always hold unique keys that will never match the current number n, so if (n in memo) will never be true.
It actually seems that you want to memoize your results for further calls recurseWrapper() within your loop, so that you can prevent computing results you've already seen. At the moment you are not doing that, as you are creating a new memo object each time you call recurseWrapper(), removing all of the memoized values. You can instead return your inner auxiliary recursive wrapper function that closes over the memo object so that you keep the one memo object for all calls of the recursive wrapper function.
But even then we will still face issues, because of how the count is being calculated. For example, if you call recurseWrapper(n) and it takes 10 iterations to call recurseCollatzSequence(k), the returned count of recurseCollatzSequence(k) is going to be 10 plus whatever number it takes to compute the Collatz sequence for k. If we memoize this number, we can face issues. If we again call recurseWrapper on another number m, recurseWrapper(m), and this time it takes 20 iterations to get to the same call of recurseCollatzSequence(k), we will use our memoized value for k. But this value holds an additional count for the 10 that it took to get from n to k, and not just the count that it took to get from k to 1. As a result, we need to change how you're computing count in your recursive function so that it is pure, so that calling a function with the same arguments always produces the same result.
As Vincent also points out in a comment, you should be memoizing the current number, ie: memo[n] and not the number you're about to compute the Collatz count for (that memoization is done when you recurse):
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");In comparison, the below shows times without memo:
//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");CodePudding user response：
After spending some time figuring out I found a working solution. The code below improved time complexity. Thanks all for helping me.
//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)