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