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