JavaScript ātruma optimizācija, izmantojot atmiņu

Ir situācijas, kad var upurēt operatīvo atmiņu, lai uzlabotu veiktspēju.

Apskatīsim piemēru. Šāds kods atrod draudzīgus skaitļus noteiktā intervālā:

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

Iepriekš minētais kods nav optimāls. Tas veic lielu skaitu operāciju un ar norādīto intervālu līdz 9000 pārlūkprogrammas lapa vienkārši iesala.

Šī koda problēma ir tā, ka mēs katram skaitlim aprēķinām tā dalītāju summu ļoti daudz reizes, tik, cik kopā skaitļu tiek pārbaudīts. Tas nozīmē, ka mūsu gadījumā jebkuram skaitlim tā dalītāju summa tiks atrasta 9000 reizes. Nav brīnums, ka viss iesalst.

Optimizēsim. Sākumā izveidosim funkciju, kas tieši aprēķina dalītāju summu, nesaglabājot tos masīvā:

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

Tagad ir pienācis laiks upurēt operatīvo atmiņu. Izveidosim funkciju, kas iepriekš vienreiz aprēķinās visu skaitļu dalītāju summas no noteiktā intervāla un saglabās tās masīvā.

Mūsu funkcijas rezultāts būs masīvs, kurā atslēga būs skaitlis (par vienu mazāks), un vērtība - tā dalītāju summa. Realizēsim mūsu funkciju:

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

Tagad, lai pārbaudītu draudzīgumu, mēs katru reizi nerēķināsim skaitļu dalītāju summas, bet vienkārši paņemsim jau aprēķināto no masīva:

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

Apvienosim visu kopā un iegūsim šādu kodu:

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

Šāds kods atrod savstarpēji pirmskaitļus no noteiktā intervāla. Optimizējiet to:

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