Ҳушвории суръат тавассути хотира дар 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;
}