Optimasi Kecepatan dengan Memori dalam JavaScript

Ada situasi di mana kita dapat mengorbankan memori RAM untuk meningkatkan kinerja.

Mari kita lihat sebuah contoh. Kode berikut menemukan bilangan bersahabat dalam rentang yang ditentukan:

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

Kode di atas tidak optimal. Ia melakukan banyak sekali operasi dan dengan rentang hingga 9000 halaman browser akan hang.

Masalah dari kode ini adalah kita untuk setiap bilangan menghitung jumlah pembaginya sangat banyak kali, sebanyak jumlah bilangan yang diperiksa. Ini berarti, dalam kasus kita untuk bilangan apa pun, jumlah pembaginya akan dicari sebanyak 9000 kali. Tidak mengherankan jika semuanya menjadi hang.

Mari kita optimalkan. Pertama-tama buatlah fungsi yang langsung menghitung jumlah pembagi, tanpa menyimpannya ke dalam array:

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

Sekarang saatnya mengorbankan memori RAM. Mari buat fungsi, yang sebelumnya sekali menghitung jumlah pembagi semua bilangan dari rentang yang ditentukan dan menyimpannya ke dalam array.

Hasil dari fungsi kami akan menghasilkan array, di mana kuncinya adalah bilangan (kurang satu), dan nilainya adalah jumlah pembaginya. Mari kita implementasikan fungsi kami:

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

Sekarang untuk memeriksa sifat bersahabat kita tidak perlu setiap kali menghitung jumlah pembagi bilangan, melainkan cukup mengambil yang sudah dihitung dari array:

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

Mari kumpulkan semuanya dan dapatkan kode berikut:

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

Kode berikut menemukan bilangan yang saling prima dari rentang yang ditentukan. Optimalkan kode tersebut:

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