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