JavaScript atminties greičio optimizavimas

Būna situacijų, kai galima paaukoti operatyviąją atmintį, kad padidintumėte veikimo greitį.

Pažiūrėkime pavyzdžiu. Šis kodas nurodytame intervale randa draugiškus skaičius:

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

Aukščiau pateiktas kodas nėra optimalus. Jis atlieka didelį operacijų skaičių ir esant nurodytam intervalui iki 9000 naršyklės puslapis tiesiog užstrigs.

Šio kodo problema ta, kad mes kiekvienam skaičiui apskaičiuojame jo dalinų sumą labai daug kartų, tiek, kiek iš viso yra tikrinamų skaičių. Tai reiškia, kad mūsų atveju bet kurio skaičiaus jo daliklių suma bus rasta 9000 kartų. Nieko keisto, kad viskas stringa.

Optimizuokime. Pirmiausia sukurkime funkciją, kuri tiesiogiai apskaičiuoja dalinų sumą, neįrašant jų į masyvą:

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

Dabar atėjo laikas paaukoti operatyviąją atmintį. Sukurkime funkciją, kuri iš anksto vieną kartą apskaičiuos visų skaičių iš nurodyto intervalo daliklių sumas ir išsaugos jas masyve.

Mūsų funkcijos rezultatas bus masyvas, kuriame raktas bus skaičius (vienu mažiau), o reikšmė - jo daliklių suma. Įgyvendinkime mūsų funkciją:

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

Dabar, norėdami patikrinti draugiškumą, mes nebekiekvieną kartą skaičiuosime skaičių daliklių sumą, o tiesiog imsime jau apskaičiuotą iš masyvo:

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

Sujunkime viską kartu ir gausime tokį kodą:

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

Šis kodas nurodytame intervale randa tarpusavyje pirminius skaičius. Optimizuokite jį:

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