JavaScriptda xotira hisobiga tezlikni optimallashtirish

Ba'zi hollarda tezlikni oshirish uchun operativ xotirani foydalanish mumkin.

Keling, bir misolni ko'rib chiqaylik. Quyidagi kod berilgan oraliqda do'st sonlarni topadi:

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

Yuqoridagi kod optimal emas. U juda ko'p operatsiyalarni bajardi va 9000 oralig'ida brauzer sahifasi shunchaki to'xtab qoladi.

Ushbu kodning muammosi shundaki, biz har bir son uchun uning bo'luvchilari yig'indisini juda ko'p marta hisoblaymiz, tekshiradigan sonlarimiz sonicha. Bu demakki, bizning holatda har qanday son uchun uning bo'luvchilari yig'indisi 9000 marta topiladi. Hammasi to'xtab qolishi ajablanarli emas.

Keling, optimallashtiraylik. Boshlash uchun ularni massivga saqlamasdan, to'g'ridan-to'g'ri bo'luvchilar yig'indisini hisoblaydigan funktsiyani yaratamiz:

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

Endi operativ xotirani foydalanish vaqti keldi. Keling, funktsiya yarataylik, bu funktsiya oldindan berilgan oraliqdagi barcha sonlarning bo'luvchilari yig'indisini bir marta hisoblab chiqadi va ularni massivda saqlaydi.

Bizning funktsiyamizning natijasi bu massiv bo'ladi, unda kalit son (bir kamroq), qiymat esa uning bo'luvchilari yig'indisi bo'ladi. Keling, funktsiyamizni amalga oshiramiz:

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

Endi do'stlikni tekshirish uchun har safar sonlar bo'luvchilari yig'indisini hisoblamaymiz, balki oldingi hisoblangan massivdan olamiz:

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

Keling hammasini birlashtiramiz va quyidagi kodni olamiz:

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

Quyidagi kod berilgan oraliqdan o'zaro tub sonlarni topadi. Uni optimallashtiring:

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