Tối ưu tốc độ bằng cách sử dụng bộ nhớ trong JavaScript

Có những tình huống có thể hy sinh bộ nhớ RAM để tăng hiệu suất.

Hãy xem xét một ví dụ. Đoạn code sau tìm các số thân thiện trong một khoảng đã cho:

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

Code ở trên không tối ưu. Nó thực hiện một số lượng lớn các phép toán và với khoảng đến 9000 trang trình duyệt sẽ đơn giản là bị treo.

Vấn đề của code này là chúng ta với mỗi số đều tính tổng các ước số của nó rất nhiều lần, bằng đúng số lượng số chúng ta kiểm tra. Điều này có nghĩa là trong trường hợp của chúng ta với bất kỳ số nào, tổng các ước số của nó sẽ được tìm thấy 9000 lần. Không có gì ngạc nhiên khi mọi thứ bị treo.

Hãy tối ưu hóa. Đầu tiên hãy tạo một hàm, tính trực tiếp tổng các ước số, mà không lưu chúng vào mảng:

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

Bây giờ đã đến lúc hy sinh bộ nhớ RAM. Hãy tạo một hàm, mà tính trước một lần tổng các ước số của tất cả các số trong khoảng đã cho và lưu chúng vào một mảng.

Kết quả của hàm chúng ta sẽ là một mảng, trong đó khóa sẽ là số (trừ đi một), và giá trị là tổng các ước số của nó. Hãy triển khai hàm của chúng ta:

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

Bây giờ để kiểm tra tính thân thiện chúng ta sẽ không mỗi lần tính lại tổng các ước số của các số, mà sẽ đơn giản lấy giá trị đã tính từ mảng:

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

Hãy tổng hợp tất cả lại và nhận được code sau:

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

Code sau tìm các số nguyên tố cùng nhau từ một khoảng đã cho. Hãy tối ưu hóa nó:

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