Βελτιστοποίηση Ταχύτητας μέσω Μνήμης στο JavaScript

Υπάρχουν καταστάσεις όπου μπορούμε να θυσιάσουμε μνήμη RAM για να αυξήσουμε την ταχύτητα απόδοσης.

Ας δούμε ένα παράδειγμα. Ο ακόλουθος κώδικας βρίσκει φιλικά νούμερα σε ένα δεδομένο διάστημα:

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

Τώρα ήρθε η ώρα να θυσιάσουμε μνήμη RAM. Ας φτιάξουμε μια συνάρτηση, που θα υπολογίσει εκ των προτέρων μία φορά το άθροισμα των διαιρετών όλων των αριθμών από το δεδομένο διάστημα και θα τα αποθηκεύσει σε έναν πίνακα.

Ως αποτέλεσμα η συνάρτησή μας θα επιστρέφει έναν πίνακα, στον οποίο το κλειδί θα είναι ο αριθμός (μειωμένο κατά ένα), και η τιμή - το άθροισμα των διαιρετών του. Ας υλοποιήσουμε τη συνάρτησή μας:

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