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

Энди оператив хотоса хисобини курбон қилиш вақти келди. Берилган оралиқдан олинган барча сонларнинг бўлувчилари йиғиндисини олдиндан бир марта ҳисоблайдиган ва уларни массивга сақлайдиган функсия ясаймиз.

Бизнинг функсиямизнинг натижаси сифатида калити (бирга камрок) сон бўладиган ва қиймати - унинг бўлувчилари йиғиндиси бўладиган массивни берadi. Келгила, функсиямизни амалга оширамиз:

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