Gostar de desenvolver algoritmos que desempenham bem é uma característica presente na maioria dos devs, quando vemos aquele algoritmo bem escrito que performa lindamente sentimos aquela felicidade na alma, mas sabemos que muitas das técnicas de melhoria de desempenho envolvem muitos tradeofs e implementações complexas. Hoje eu vou explicar uma técnica bem simples para melhorar o desempenho dos seus algoritmos, a memorização.

Table of contents

• O que é memorização
• Primeira implementação utilizando operador de atribuição ou
• Segunda implementação utilizando a palavra chave defined
• Quando utilizar uma implementação ou outra
• Terceira implementação utilizando método tap
• Conclusão

O que é memorização

Em termos gerais, memorização é uma técnica que envolve você memorizar, lembrar ou guardar, de alguma forma, uma resposta de um método caro para evitar ficar usando desnecessariamente.

O que seria um "método caro"? 

Um "método caro" seriam aqueles métodos que podem demandar muita memória, processamento, chamam diversos serviços terceiros ou que naturalmente têm uma complexidade inevitavelmente maior.

Com essa definição em mente, o Ruby oferece ferramentas interessantes que permitem técnicas interessantes de implementação de memorização. Separei três técnicas que achei interessante para apresentar e vou explicá-las na seguinte ordem.

Primeiramente, eu mostrarei as duas implementações principais de memorização, após isso, explicarei quando escolher uma ao invés da outra a depender do caso específico e por fim mostrarei uma terceira forma diferente de implementação a fim de conhecimento.

Primeira implementação utilizando operador de atribuição ou

A primeira forma de implementar memorização é utilizando apenas o “operador de atribuição ou” ||=, sendo muito importante para o funcionamento adequado da memorização.

Você pode estar se perguntando: “Certo, mas o que é esse abençoado 'operador de atribuição ou'?”

Este operador segue apenas uma condição, só atribui um novo valor à variável se o valor atual for false ou nil. Caso contrário, ele irá manter o valor atual da variável.

Vamos para um exemplo:

example_variable = false
example_variavel ||= 'Giovanny'
puts example_variable # 'Giovanny'

example_variavel ||= 'Fulano'
puts example_variable # 'Giovanny'

Perceba que na primeira atribuição do valor Giovanny utilizando o “operador de atribuição ou” a variável example_variable foi bem-sucedida, pois o valor atual da example_variable era false.

No entanto, na segunda atribuição, que tinha como valor Fulano utilizando o “operador de atribuição ou” para a variável example_variable, não foi bem-sucedida, pois o valor atual da variável example_variable era uma string “Giovanny” e não valores nil ou false.

Com isso em mente, podemos guardar o valor de retorno vindo de um método caro em uma variável utilizando o “operador de atribuição ou”. Uma vez que esse método for executado, a variável guardará esse valor e não será necessário executar o método novamente para o caso.

No exemplo a seguir, o método caro será o expensive_method e ele retornará como valor uma string. Para deixar ainda mais claro, fixarei uma string de retorno a fim de exemplificação, que nesse caso será a string MOLA.

Exemplo:

class EspecifiqClass
  def some_method
    @store ||= expensive_method
  end

  private

  def expensive_method
    puts 'Executando expensive_method'
    # many logic
    'MOLA'
  end
end

example = EspecifiqClass.new
puts example.some_method # Retorno do valor "Mola" executando o expensive_method
puts example.some_method # Retorno do valor "Mola" sem executar o expensive_method

Resultado:

algorith_test git:(main) ✗ ruby test.rb
Executando expensive_method
MOLA
MOLA

Nesse caso, percebe-se que estamos chamando duas vezes o método some_method, no entanto, o método some_method vai apenas chamar o método privado expensive_method apenas na primeira vez.

Isso faz sentido porque a variável example é uma instância da classe EspecifiqClass e, na primeira execução do método some_method a variável @store não tinha nenhum valor, logo, a condição do “operador de atribuição ou” vai ser atendida executando o método privado expensive_method e armazenando seu resultado na variável @store.

Já na segunda chamada do método some_method a variável @store agora tem um valor MOLA, fazendo a condição do “operador de atribuição ou” não seja atendida e fazendo o método some_method retorne o valor MOLA.

Com isso, na segunda chamada, você acaba de ter o resultado esperado, mas sem demandar executar novamente o método caro. Podemos comprovar isso pela mensagem no console "Executando expensive_method" ser executada apenas uma vez.

E se...

E se em vez o valor do retorno do método expensive_method se uma string estivéssemos recebendo um valor booleano (true e false), o que aconteceria?

Aconteceria que teríamos o caso em que o valor false seria efetivamente um valor a ser guardado na variável, mas como estamos utilizando diretamente o "operador de atribuição ou" (||=) ele não iria guardar esse valor, pois, a condição do operador vai ser sempre positiva nesse caso, pois o valor vai ser efetivamente false.

Vamos mudar o método expensive_method para que ele retorne um booleane vamos avaliar o seu funcionamento. Para facilitar a explicação, vamos fixar o valor false como retorno.

class EspecifiqClass
  def some_method
    @store ||= expensive_method
  end

  private

  def expensive_method
    puts 'Executando expensive_method'
    # many logic
    false
  end
end

example = EspecifiqClass.new
puts example.some_method
puts example.some_method

Resultado:

algorith_test git:(main) ✗ ruby test.rb
Executando expensive_method
false
Executando expensive_method
false

Podemos perceber que o expensive_method está executando duas vezes mesmo quando efetivamente estamos devolvendo um valor false que deveria ser guardado. Pelo motivo antes explicado da condição do "operador de atribuição ou" está sendo positiva ele não está guardando o valor false e executando novamente o método expensive_method.

Nesse caso, temos valores falsos legítimos e precisamos consertar esse problema guardando o valor. Para suprir essa lacuna, a segunda implementação de memorização será bem útil.

Segunda implementação utilizando a palavra chave defined

Para resolver o problema de “valores falsos legítimos” no caso do nosso método caro retornar valores falsos, precisamos verificar se existe um valor anterior na variável efetivamente.

Caso exista algum valor, a gente retorna esse valor, caso contrário, a gente executa o método caro.

Para verificar se a variável tem um valor ou não, podemos usar a palavra-chave defined?. Essa palavra-chave verificará se a variável está definida ou não, caso esteja, ela retornará o tipo da declaração dela, caso não esteja, ela retornará nil.

Segue o exemplo desse conceito, na prática, utilizando o REPL do Ruby:

irb(main):001> defined? example
=> nil
irb(main):002> example = 'test'
=> "test"
irb(main):003> defined? example
=> "local-variable"

Como podemos ver, quando verificamos se uma variável que não foi definida previamente está definida na primeira linha, ele retornará o valor nil. Nesse caso, estamos verificando se a variável example foi definida na primeira linha.

Mas quando realmente definimos a variável na segunda linha e depois verificamos se ela foi definida na terceira linha o Ruby retorna o tipo de declaração dela.

Agora, com esse entendimento da palavra-chave defined? podemos realmente guardar valores false legítimos da seguinte forma:

class EspecifiqClass
  def some_method
    return @store if defined? @store
    @store = expensive_method
  end

  def expensive_method
    # many logic, return the boolean value
    false
  end
end

example = EspecifiqClass.new
puts example.some_method # false (Executando o expensive_method)
puts example.some_method # false (Não executando o expensive_method)

Na primeira linha do método some_method ele verificará se a variável @store foi definida, em caso positivo, ele retornará diretamente à variável com seu valor. Caso contrário, ele chamará o método expensive_method que armazenará o valor retornado na variável @store e retornará à variável.

Quando utilizar uma implementação ou outra

Após mostrar as duas implementações, acredito que você já tenha uma boa noção de quando usar ambas, no entanto, eu vou apenas recapturar.

Utilize a segunda implementação que usa a palavra-chave defined? quando o método caro poder retornar um valor falso legitimo, com isso, você armazenará efetivamente o valor false na variável normalmente.

Caso o retorno da função cara seja de outros tipos como stringsou objects, por exemplo, você pode seguir a primeira implementação que utiliza apenas o “operador de atribuição ou” (||=) normalmente, você estará tranquilo com essa implementação.

Terceira implementação utilizando método tap

Existe uma terceira forma de fazer uma implementação de memorização onde o retorno do “método caro” é um hash no Ruby, que o engenheiro de software “Alex MacArthur” apresentou no seu artigo "Elegant Memoization with Ruby’s .tap Method".

Inclusive, teve uma discussão interessante nesse artigo onde algumas pessoas alegam não enxergar efetivamente um “beneficio” na forma de implementação que o Sr. MacArthur trouxe. Caso tenha curiosidade sobre essa discussão (como eu tive), leia os comentários e os pontos que as pessoas trouxeram no artigo, não vou me atentar a detalhes aqui.

De toda forma, achei interessante ver outra forma de implementação sobre o tema e por isso decidi mencionar aqui.

Antes de ir para a implementação, é necessário entender o que é esse método .tap.

De acordo com a documentação do ruby em uma tradução direta, o método .tap:

Entrega-se ao bloco e depois devolve-se. O objetivo principal deste método é “entrar” numa cadeia de métodos, de modo a realizar operações em resultados intermédios dentro da cadeia.

A documentação menciona a "cadeia" porque esse método brilha especialmente no debbug de cadeia de métodos, no entanto, vamos nos ater ao nosso tema.

O que importa para nós é que ele apenas entra na cadeia e depois devolve normalmente, o que significa que podemos entrar em um hash e depois devolver resultados a ele

Parece confuso, eu sei, mas vamos para um exemplo da implementação de memorização utilizando o método .tap.

Nesse exemplo, temos uma classe chamada ExampleClasse onde o método people_detail vai memorizar detalhes das informações da pessoa, como nome e idade, mantendo o padrão do artigo, todos os dados também serão fixados no código.

Segue o exemplo:

class ExampleClass
  def name
    people_detail['name']
  end

  def age
    people_detail['age']
  end

  private

  def people_detail
    @people_detail ||= {}.tap do |people_store|
      puts 'Memorização people_detail'
      people_store['name'] = 'Giovany'
      people_store['age'] = 21
    end
  end
end

instance_one = ExampleClass.new
puts instance_one.name
puts instance_one.age

O resultado no console:

Memorização people_detail
Giovany
20

Nota-se que essa implementação é bem concisa em apenas um método, onde o próprio método verifica se a variável @people_detail é false ou nil com o “operador de atribuição ou” e em caso positivo, ele dispara o método .tapque aplica a lógica que está sendo passada a ele que por sua vez armazena as informações no hash. Achei superinteressante essa outra forma de implementação.

O resultado no console prova que a memorização dos dados foi feita de forma bem sucedida, pois a lógica passada para o método .tap foi apenas executada uma vez, pelo que mostra a mensagem Memorização people_detail no console.

Conclusão

Existem mais formas de tornar mais complexo o tema, como, por exemplo, colocando mais parâmetros para memorizar, mas está fora do escopo desse artigo introdutor, talvez no futuro eu faça uma parte dois sobre esse tema. Espero que esse artigo tenha te ajudado a aprender sobre memorização!

E claro, não poderia deixar de agradecer à Cherry, Cliton e ao Williams por darem feedback nesse artigo antes dele ser postado, foi por conta deles que eu consegui deixar esse artigo melhor, meus sinceros muito obrigado ❤️.

Referências

• Understanding Ruby - Memoization
• Memoization in Ruby
• Elegant Memoization with Ruby’s .tap Method
• O poder da memoização
• A Guide to Memoization in Ruby