Optimizing speed using memory in JavaScript

There are situations when you can sacrifice RAM to increase speed.

Let's look at an example. The following code finds friendly numbers in a given range:

console.log(getFriendly(9000)); function getFriendly(range) { let res = []; for (let i = 1; i <= range; i++) { for (let j = 1; j < range; j++) { if (isFriendly(i, j)) { res.push([i, j]); } } } return res; } function isFriendly(num1, num2) { let sum1 = getSum(getOwnDivisors(num1)); let sum2 = getSum(getOwnDivisors(num2)); return sum1 == num2 && sum2 == num1; } function getOwnDivisors(num) { let res = []; for (let i = 1; i < num; i++) { if (num % i === 0) { res.push(i); } } return res; } function getSum(arr) { let sum = 0; for (let elem of arr) { sum += elem; } return sum; }

The above code is not optimal. It perform a large number of operations, and at the specified range up to 9000, the browser page will simply freeze.

The problem with this code is that for each number we calculate the sum of its divisors very many times, as many as many numbers we check. This means that in our case, for any number, the sum of its divisors will be found 9000 times. No wonder everything hangs.

Let's optimize. First, let's make a function that directly calculates the sum of divisors, without storing them in an array:

function getOwnDivisorsSum(num) { let sum = 0; for (let i = 1; i < num; i++) { if (num % i === 0) { sum += i; } } return sum; }

Now it's time to sacrifice RAM. Let's make a function that calculates the sum of the divisors of all numbers from a given range once in advance and saves them to an array.

As a result, our function will return an array in which the key will be a number (one less), and the value will be the sum of its divisors. Let's implement our function:

function getAllSum(range) { let arr = []; for (let i = 1; i <= range; i++) { arr.push(getOwnDivisorsSum(i)); } return arr; }

Now, to check the friendliness, we will not calculate the sum of the number divisors each time, but simply take the already calculated one from the array:

function getFriendly(range) { let sums = getAllSum(range); // [1, 2, 6...] let res = []; for (let i = 0; i < sums.length; i++) { for (let j = i; j < sums.length; j++) { let sum1 = sums[i]; let sum2 = sums[j]; let num1 = i + 1; let num2 = j + 1; if (num1 == sum2 && num2 == sum1) { res.push([num1, num2]); } } } return res; }

Putting it all together, we get obtain following code:

console.log(getFriendly(9000)); function getFriendly(range) { let sums = getAllSum(range); let res = []; for (let i = 0; i < sums.length; i++) { for (let j = i; j < sums.length; j++) { let sum1 = sums[i]; let sum2 = sums[j]; let num1 = i + 1; let num2 = j + 1; if (num1 == sum2 && num2 == sum1) { res.push([num1, num2]); } } } return res; } function getAllSum(range) { let arr = []; for (let i = 1; i <= range; i++) { arr.push(getOwnDivisorsSum(i)); } return arr; } function getOwnDivisorsSum(num) { let sum = 0; for (let i = 1; i < num; i++) { if (num % i === 0) { sum += i; } } return sum; }

The following code finds coprime numbers from a given range. Optimize it:

console.log(getRelativelyPrime(10000)); function getRelativelyPrime(range) { let res = []; for (let i = 2; i <= range; i++) { for (let j = 2; j < range; j++) { if (isRelativelyPrime(i, j)) { res.push([i, j]); } } } return res; } function isRelativelyPrime(num1, num2) { let arr1 = getDivisors(num1); let arr2 = getDivisors(num2); let int = getIntersect(arr1, arr2); if (int.length === 0) { return true; } else { return false; } } function getIntersect(arr1, arr2) { let result = []; for (let elem of arr1) { if (arr2.includes(elem)) { result.push(elem); } } return result; } function getDivisors(num) { let res = []; for (let i = 2; i <= num; i++) { if (num % i === 0) { res.push(i); } } return res; }
enru