Uboreshaji wa Kasi kwa kutumia Kumbukumbu katika JavaScript

Kuna hali ambazo unaweza kutoa kumbukumbu ya RAM ili kuongeza uchangamfu.

Hebu tuangalie kwa mfano. Msimbo unaofuata hupata nambari za kirafiki katika kiwango kilichopewwa:

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

Msimbo ulio hapo juu sio bora. Unafanya idadi kubwa ya shughuli na kwa kiwango kilichoonyeshwa hadi 9000 ukurasa wa kivinjari utakwama tu.

Shida ya msimbo huu ni kwamba sisi kwa kila nambari huhesabu jumla ya wagawanyiko wake mara nyingi sana, kadiri idadi ya jumla ya nambari tunazochunguza. Hii inamaanisha kuwa kwa upande wetu kwa nambari yoyote jumla ya wagawanyiko wake itapatikana 9000 mara. Haishangazi kwamba kila kitu kinakwama.

Hebu tuongeze ufanisi. Kwanza tufanye kitendo, kwa moja kukokotoa jumla ya wagawanyiko, bila kuhifadhi kwenye safu:

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

Sasa imefika wakati wa kutoa kumbukumbu ya RAM. Tufanye kitendo, ambacho mapema mara moja kitakokotoa jumla ya wagawanyiko wa nambari zote kutoka kwa kiwango kilichopewwa na kuhifadhi katika safu.

Matokeo yetu kitendo kitatoa safu, ambapo ufunguo utakuwa nambari (moja chini), na thamani - jumla ya wagawanyiko wake. Tutekeleze kitendo chetu:

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

Sasa kwa ukaguzi wa urafiki hatutahesabu kila wakati jumla ya wagawanyiko wa nambari, bali tuta kuchukua tayari iliyokokotolewa kutoka kwa safu:

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

Hebu tukusanye pamoja na tupate msimbo ufuatao:

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

Msimbo unaofuata hupata nambari zenye usawa kutoka kwa kiwango kilichopewwa. Ongeza ufanisi wake:

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