# Оптимизация скорости за счет памяти в JavaScript

Бывают ситуации, когда можно пожертвовать оперативной памятью для повышения быстродействия.

Давайте посмотрим на примере. Следующий код находит дружественные числа в заданном промежутке:

`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; }`

Приведенный выше код не оптимальный. Он делает большое количество операций и при указанном промежутке до `9000` страница браузера просто зависнет.

Проблема этого кода в том, что мы для каждого числа считаем сумму его делителей очень много раз, столько, сколько всего чисел проверяем. Это значит, что в нашем случае для любого числа сумма его делителей будет найдена `9000` раз. Не удивительно, что все зависает.

Давайте оптимизировать. Для начала сделаем функцию, напрямую подсчитывающую сумму делителей, без сохранения их в массив:

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

Теперь пришло время пожертвовать оперативной памятью. Сделаем функцию, которая заранее один раз рассчитает сумму делителей всех чисел из заданного промежутка и сохранит их в массив.

Своим результатом наша функция будет отдавать массив, в котором ключом будет число (на один меньше), а значением - сумма его делителей. Реализуем нашу функцию:

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

Теперь для проверки дружественности мы не будем каждый раз рассчитывать сумму делителей чисел, а просто будем брать уже посчитанную из массива:

`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; }`

Соберем все вместе и получим следующий код:

`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; }`

Следующий код находит взаимно-простые числа из заданного промежутка. Оптимизируйте его:

`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; }`
← →
↑
en ru