การปรับปรุงความเร็วโดยใช้หน่วยความจำใน JavaScript

มีสถานการณ์ที่เราสามารถแลกเปลี่ยนการใช้หน่วยความจำ RAM เพื่อเพิ่มประสิทธิภาพความเร็วได้

ลองดูตัวอย่าง โค้ดต่อไปนี้ค้นหาจำนวนที่เป็นเพื่อนกันในช่วงที่กำหนด:

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