Corra Function, Corra!!

Referencia: livro "Programming Kotlin" de Stephen Samuel e Stefan Bocutiu.

Photos by Andrea Piacquadio and Pixabay from Pexels

Olá pessoal,

Neste artigo vou compartilhar alguns recursos que aprendi para melhorar a performance do código:

1) Lazy: tem a finalidade de só invocar uma função apenas quando ela for ser usada pela primeira vez.

2) Memoization: em funções recorrentes se for necessário armazenar o resultado de cada chamada da função.

3) A keyword "tailrec": em funções recorrentes se não for necessário armazenar o resultado de cada chamada da função.

Vamos lá!

1) Lazy tem a finalidade de só invocar uma função apenas quando ela for ser usada pela primeira vez. Se você tiver uma função muito pesada, Lazy vai deixar para executá-la somente quando de fato você precisar do seu retorno em seu código. Veja o código ilustrativo abaixo:

/* Atribuindo a função "readStringFromDatabase" a uma variável. */
fun readStringFromDatabase(): String = ... // expensive operation
val lazyString = lazy { readStringFromDatabase() }

/* Usando o retorno da função pela primeira vez. */
val string = lazyString.value 

2) Ao usarmos funções recorrentes (funções que invocam a si próprias) podemos usar a técnica de "MEMOIZATION", memorização para acelerar a execução ao fazer o caching e reutilizar o resultado de chamadas anteriores. Assim ela roda mais rápido e evita a falha de Stack Overflow.

Vamos ver a comparação entre a chamada da função de exemplo com e sem aplicação da técnica:

1ª Execução: fib(10) = 89

Tempo de execução NÃO usando Memoization com mutableMapOf(): 9 ms.

2ª Execução: memfib(100) = 1298777728820984005

Tempo de execução USANDO Memoization com mutableMapOf(): 2 ms.

fun  main ( args :  Array < String >) {
    var k = 10
    var timeIni = System.currentTimeMillis()
    //A Função fib retorna o elemento a posição k da sequência de Fibonacci: 1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; 144;...
    //Por exemplo, fib(0) = 1, fib(1) = 1, fib(2), fib(3)
    fun fib(k: Int): Long = when (k) {
        0 -> 1
        1 -> 1
        else -> fib(k - 1) + fib(k - 2)
    }

    println("1ª Execução: fib($k) = ${fib(k)}")
    println("Tempo de execução NÃO usando Memoization com mutableMapOf() ${System.currentTimeMillis() - timeIni} ms.")

    // A Função memfib retorna o elemento a posição k da sequência de Fibonacci aplicando o conceito de 'MEMOIZATION' por meio de uma MutableMap.
    timeIni = System.currentTimeMillis()
    k = 100
    val map = mutableMapOf<Int, Long>()
    fun memfib(k: Int): Long {
        return map.getOrPut(k) {
            when (k) {
                0 -> 1
                1 -> 1
                else -> memfib(k - 1) + memfib(k - 2)
            }
        }
    }
    println("2ª Execução: memfib($k) = ${memfib(k)}")
    println("Tempo de execução USANDO Memoization com mutableMapOf() ${System.currentTimeMillis() - timeIni} ms.")
}

Uau!!!

3) Ao usarmos funções recorrentes (funções que invocam a si próprias) podemos fazer a declararação da função recorrente usando a keyword "tailrec"; assim ela não guarda os resultados da última execução. Assim ela roda mais rápido e evita a falha de Stack Overflow.

Olha a comparação do tempo de execução nesse exemplo de duas funções que calculam o fatorial de um número inteiro:

1ª Execução:

Fatorial de 5 = 120

A função fact executou em 16 ms

2ª Execução:

Fatorial de 5 = 120

A função factFaster executou em 0 ms

O código está abaixo:

fun main(args: Array<String>) {
    var time = System.currentTimeMillis()
    var num: Int = 5

    println("Fatorial de $num = ${fact(num)}")
    println("A função fact executou em ${System.currentTimeMillis() - time} ms\n")

    time = System.currentTimeMillis()
    println("Fatorial de $num = ${factFaster(num)}")
    println("A função factFaster executou em ${System.currentTimeMillis() - time} ms")

}

fun fact(k: Int): Int {
    fun factTail(m: Int, n: Int): Int {
        if (m == 0) return n
        else return factTail(m - 1, m * n)
    }
    return factTail(k, 1)
}

fun factFaster(k: Int): Int {
    tailrec fun factTail(m: Int, n: Int): Int {
        if (m == 0) return n
        else return factTail(m - 1, m * n)
    }
    return factTail(k, 1)
}