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

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

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

javascriptconsole.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 раз. Не удивительно, что все зависает.

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

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

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

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

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

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

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

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

javascriptconsole.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;
}

javascriptconsole.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;
}