Caching
El Caching es básicamente una forma de almacenar datos en memoria para que no se vuelvan a calcular. Con esto podemos ahorrar tiempo (time complexity) pero tendremos más space complexity.
Optimizando un algoritmo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
// Ejemplo obtenido de https://slides.com/bgando/intro-to-algorithms/#/2/1
const isUnique = (arr) => {
let result = true;
for (let i = 0; i < arr.length; i++) {
console.log(`~~~~ OUTER LOOP ~~~~ i === ${i}`);
for (let j = 0; j < arr.length; j++) {
console.log(`~~~~ INNER LOOP ~~~~ j === ${j}`);
if (i !== j && arr[i] === arr[j]) {
result = false;
}
}
}
return result;
};
|
Si ejecutamos este código Quadratic (n^2), las veces que entramos en un loop serán 12:
1
2
3
4
5
6
7
8
9
10
11
12
|
~~~~ OUTER LOOP ~~~~ i === 0
~~~~ INNER LOOP ~~~~ j === 0
~~~~ INNER LOOP ~~~~ j === 1
~~~~ INNER LOOP ~~~~ j === 2
~~~~ OUTER LOOP ~~~~ i === 1
~~~~ INNER LOOP ~~~~ j === 0
~~~~ INNER LOOP ~~~~ j === 1
~~~~ INNER LOOP ~~~~ j === 2
~~~~ OUTER LOOP ~~~~ i === 2
~~~~ INNER LOOP ~~~~ j === 0
~~~~ INNER LOOP ~~~~ j === 1
~~~~ INNER LOOP ~~~~ j === 2
|
Para optimizar este algoritmo, podemos hacer Caching:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
// Ejemplo obtenido de https://slides.com/bgando/intro-to-algorithms/#/2/2
isUnique = (arr) => {
const cache = {};
let result = true;
for (let i = 0; i < arr.length; i++) {
console.log(`~~~~ LOOP ~~~~ i === ${i}`);
if (cache[arr[i]]) {
result = false;
} else {
cache[arr[i]] = true;
}
}
return result;
};
|
Si ejecutamos este código Linear (n), las veces que entramos en un loop serán 3, por lo tomara menos tiempo su ejecución:
1
2
3
|
~~~~ LOOP ~~~~ i === 0
~~~~ LOOP ~~~~ i === 1
~~~~ LOOP ~~~~ i === 2
|
Otro ejemplo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
// Ejemplo obtenido de https://slides.com/bgando/intro-to-algorithms/#/2/4
// It should not return any duplicate values in the sorted array.
const uniqSort = function(arr) {
const cache = {};
const result = [arr[0]];
for (let i = 0; i < arr.length; i++) {
if (!cache[arr[i]]) {
result.push(arr[i]);
cache[arr[i]] = true;
}
}
return result.sort((a, b) => a - b);
};
uniqSort([4,2,2,3,2,2,2]); // => [2,3,4]
|
Memoization
Memoization es una forma específica de almacenamiento en caché que implica el almacenamiento en caché del valor de retorno de una función basado en sus parámetros.
El almacenamiento en caché es un término más general; por ejemplo, el almacenamiento en caché HTTP es almacenamiento en caché pero no memoization.
En javascript, usamos objetos como hash tables para almacenar datos.
Ejemplo
Obtener el factorial de un número implica haces muchos cálculos una y otra vez. En lugar de re calcular el resultado de la función, podemos simplemente memoize/memorizarlo.
Por ejemplo, si hacemos:
factorial(5) = 5 * 4 * 3 * 2 * 1
tenemos que pasar por factorial(4) = 4 * 3 * 2 * 1.
En lugar de hacer eso, simplemente guardaríamos el resultado de factorial(4) y la usaríamos para hacer nuestro factorial(5) = 5 * memo["4"] * memo["3"] * memo["2"] * memo["1"].
Ejemplo con javascript
// times10 takes an argument, n, and multiples n times 10
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
// Ejemplo obtenido de https://slides.com/bgando/intro-to-algorithms/#/2/10
const times10 = (n) => (n * 10);
const cache = {};
const memoTimes10 = (n) => {
if (n in cache) {
console.log('Fetching from cache:', n);
return cache[n];
} else {
console.log('Calculating result');
let result = times10(n); //90
cache[n] = result;
return result;
}
};
console.log('calculated value:', memoTimes10(9)); // calculated
console.log('cached value:', memoTimes10(9)); // cached
|
En este caso tenemos nuestro cache en el scope global, lo cual no es una buena practica pero para este ejemplo nos funciona, ya que si lo pusiéramos dentro el scope de memoTimes10, siempre borraríamos el cache de la función anterior.
Ejemplo con callback
Un ejemplo con el cache en el scope de la función (lo cual es buena practica):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
// Ejemplo obtenido de https://slides.com/bgando/intro-to-algorithms/#/2/10
const times10 = (n) => (n * 10);
const memoizedClosure = () => {
let cache = {};
return (n) => {
if (n in cache) {
console.log('Fetching from cache:', n);
return cache[n];
} else {
console.log('Calculating result');
let result = times10(n);
cache[n] = result;
return result;
}
};
};
|
Ok, pero, ¿cómo lo ejecutamos?
1
2
3
4
5
|
// returned function from memoizedAdd
const memoClosureTimes10 = memoizedClosure();
console.log('calculated value:', memoClosureTimes10(9)); // calculated
console.log('cached value:', memoClosureTimes10(10)); // cached
|
Función para hacer memoization automáticamente
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
const memoize = (cb) => {
let cache = {};
return (n, ...args) => { //[9]
if (n in cache) {
console.log('Fetching from cache:', n);
return cache[n];
} else {
console.log('Calculating result');
let result = cb(n, ...args); // cb(9)
cache[n] = result;
return result;
}
};
};
|
Para utilizarla:
1
2
3
4
5
6
7
|
const times10 = (n) => (n * 10);
// returned function from memoizedAdd
const memoizedTimes10 = memoize(times10);
console.log('calculated value:', memoizedTimes10(9)); // calculated
console.log('cached value:', memoizedTimes10(9)); // cached
|
Lo que estamos haciendo aquí, es pasarle la función del algoritmo que queremos usar, en este caso times10, pero perfectamente podemos pasar cualquier otra función y nuestro memoize funcionara igual.
Ejemplo con recusión
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
// Ejemplo obtenido de https://slides.com/bgando/intro-to-algorithms/#/3/19
const memoize = (fn) => {
let cache = {};
return (...args) => {
let n = args[0];
if (n in cache) {
console.log('Fetching from cache', n);
return cache[n];
}
else {
console.log('Calculating result', n);
let result = fn(n);
cache[n] = result;
return result;
}
}
}
const factorial = memoize(
(x) => {
if (x === 0) {
return 1;
}
else {
return x * factorial(x - 1);
}
}
);
console.log(factorial(5)); // calculated
console.log(factorial(5)); // calculated for 6 and cached for 5
|
Ejemplos obtenidos de Bianca Gandolfo
