Em ciência da computação, memoize ou memoization é uma técnica de otimização que faz um cache do resultado de uma função com base nos parâmetros passados para ela.
Essa técnica faz com que a execução real da função só aconteça a primeira vez que o parâmetro ou conjunto de parâmetros é passado, pois como fará um cache do resultado, ao receber os mesmos parâmetros, retornará o valor que está armazenado no cache.
Antes de utilizar a técnica, vamos criar duas funções. A Primeira para calcular o fatorial de um número.
func fatorial(n int) int {
total := 1
for i := 2; i <= n; i++ {
total *= i
}
return total
}
E a segunda para encontrar o número na posição X da sequência de Fibonacci.
func fibonacci(n int) int {
if n <= 1 {
return n
}
return fibonacci(n-1) + fibonacci(n-2)
}
Se você reparar, embora o que acontece dentro de cada função seja diferente, a assinatura das duas é praticamente a mesma func(int) int.
Com essa informação em mãos, vamos criar um tipo de dado que represente essa assinatura.
type FII func(int) int
Agora vamos criar nossa função de memoization para funções do tipo FII.
func memoized(fn FII) FII {
cache := make(map[int]int)
return func(n int) int {
if val, ok := cache[n]; ok {
fmt.Printf("hit: ")
return val
}
result := fn(n)
cache[n] = result
return result
}
}
Como podemos ver, a função é bem simples e aceita somente um parâmetro, que é uma outra função do tipo FII, cria uma variável para o cache e retorna uma função do tipo FII.
Dentro dessa função que é retornada, os passos são bem simples também.
- Valida se o input existe no cache;
- Se existir ela já retorna o valor;
- Caso não encontre o valor no cache, chama a função original para calcular o resultado;
- Armazena o resultado no cache;
- Retorna o resultado.
Agora vamos utilizar essa função memoized para “criar” uma função de memoization para nossa função fatorial.
fatMem := memoized(fatorial)
fmt.Printf("%d \n", fatMem(10)) // output - 3628800
fmt.Printf("%d \n", fatMem(10)) // output - hit: 3628800
fmt.Printf("%d \n", fatMem(10)) // output - hit: 3628800
Agora vamos fazer o mesmo processo para a função fibonacci.
fibMem := memoized(fibonacci)
fmt.Printf("%d \n", fibMem(14)) // output - 377
fmt.Printf("%d \n", fibMem(14)) // output - hit: 377
fmt.Printf("%d \n", fibMem(14)) // output - hit: 377
Poderiamos ter implementado a técnica de memoization dentro das próprias funções fatorial e fibonacci, porém isso levaria a duplicação de código, além de “prender” a sua forma de utilização.
Da forma como implementamos, podemos utilizar as funções com ou sem a técnica, além de conseguir reutilizar a função de memoization em qualquer função que tenha uma assinatura do tipo FII.
Deixem suas dúvidas nos comentários.
Até a próxima!