Corra Function, Corra!!

#Kotlin

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