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