JavaScript-ում արագության օպտիմիզացիա հիշողության միջոցով

Լինում են իրավիճակներ, երբ կարելի է զոհաբերել օպերատիվ հիշողությունը՝ արագագործությունը բարձրացնելու համար։

Դիտարկենք օրինակով։ Հետևյալ կոդը գտնում է բարեկամական թվերը տվյալ միջակայքում.

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