Оптимизация скорости за счет памяти в 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;
}