Pensamento Funcional: recursos funcionais no Groovy – Parte 03

Quanto mais detalhes de baixo nível a linguagem de programação puder manipular, menos espaços haverá para a inserção de erros e complexidade. Um exemplo clássico disso é a coleta de lixo e o gerenciamento de memória na JVM. Como já enfatizado nas partes anteriores, uma das características das linguagens funcionais — e das linguagens dinâmicas com recursos funcionais — é o fato de permitirem que se conceda seletivamente o controle dos detalhes mais corriqueiros para a linguagem e o tempo de execução. Em “Recursos funcionais no Groovy – Parte 01“, por exemplo, é mostrado como a recursão elimina a necessidade de que o desenvolvedor mantenha o estado. Nesta parte, faremos o mesmo com o armazenamento em cache no Groovy.

O armazenamento em cache é um requisito comum (e uma fonte de erros difíceis de localizar). Nas linguagens orientadas a objetos, o armazenamento em cache geralmente acontece no nível do objeto de dados e os desenvolvedores devem que gerenciá-lo. Muitas linguagens de programação funcionais fazem o armazenamento em cache no nível da função por meio de um mecanismo chamado memoização. Neste artigo, investigamos dois casos de uso do armazenamento em cache para as funções: chamadas intraclasse x externas. Também ilustramos duas alternativas para implementar o armazenamento em cache: estado manual e memoização.

Armazenamento em cache no nível do método

Se você já leu alguma parte desta série, está familiarizado com o problema da classificação numérica (explicado no primeiro artigo). O ponto de partida deste artigo é uma versão do Groovy (derivado no último artigo), mostrado na Listagem 1:

class Classifier {
  def static isFactor(number, potential) {
    number % potential == 0;
  }

  def static factorsOf(number) {
    (1..number).findAll { i -> isFactor(number, i) }
  }

  def static sumOfFactors(number) {
    factorsOf(number).inject(0, {i, j -> i + j})
  }

  def static isPerfect(number) {
    sumOfFactors(number) == 2 * number
  }

  def static isAbundant(number) {
    sumOfFactors(number) > 2 * number
  }

  def static isDeficient(number) {
    sumOfFactors(number) < 2 * number
  }
}

O algoritmo interno de factorsOf(), na Listagem 1, pode ser otimizado por meio dos truques mostrados em “Pensando funcionalmente – Parte 02“, mas neste exemplo estamos mais interessados no armazenamento em cache no nível da função.

Como a classe Classifier classifica números, um uso comum da mesma seria passar o mesmo número por vários métodos para classificá-lo. Por exemplo, veja o código da Listagem 2:

//...
if (Classifier.isPerfect(n)) print '!'
else if (Classifier.isAbundant(n)) print '+'
else if (Classifier.isDeficient(n)) print '-'
//...

Na implementação atual, é necessário recalcular a soma de fatores de todos os métodos de classificação chamados. Este é um exemplo de armazenamento em cache intraclasse : durante o uso normal, o método sumOfFactors() normalmente é chamado diversas vezes por número. Neste caso de uso comum, essa abordagem é ineficiente.

Soma do armazenamento em cache

Uma das formas de deixar o código mais eficiente é aproveitar o trabalho intenso que já foi realizado. Como a geração da soma de fatores é cara, faremos somente uma vez para cada número. Para isso, é criado um cache para armazenar os cálculos, como mostra a Listagem 3:

class ClassifierCachedSum {
  private sumCache

  ClassifierCachedSum() {
    sumCache = [:]
  }

  def sumOfFactors(number) {
    if (sumCache.containsKey(number))
      return sumCache[number]
    else {
      def sum = factorsOf(number).inject(0, {i, j -> i + j})
      sumCache.putAt(number, sum)
      return sum
    }
  }
  //... remainder of code unchanged
}

Na Listagem 3, é criado um hash chamado sumCache no construtor. No método sumOfFactors(), verificamos se a soma do parâmetro já está em cache e a retorno. Se não estiver, é feito o cálculo caro e a soma é colocada no cache antes de retorná-la.

O código é mais complicado, mas os resultados falam por si. Todos os exemplos são submetidos a uma série de testes de unidade que seguem o padrão mostrado na Listagem 4:

class ClassifierTest {
  def final TEST_NUMBER_MAX = 1000
  def classifier = new ClassifierCachedSum()

  @Test
  void classifier_many_checks_without_caching() {
    print "Nonoptimized:              "
    def start = System.currentTimeMillis()
    (1..TEST_NUMBER_MAX).each {n ->
      if (Classifier.isPerfect(n)) print '!'
      else if (Classifier.isAbundant(n)) print '+'
      else if (Classifier.isDeficient(n)) print '-'
    }
    println "\n\t ${System.currentTimeMillis() - start} ms"
    print "Nonoptimized (2nd):        "
    start = System.currentTimeMillis()
    (1..TEST_NUMBER_MAX).each {n ->
      if (Classifier.isPerfect(n)) print '!'
      else if (Classifier.isAbundant(n)) print '+'
      else if (Classifier.isDeficient(n)) print '-'
    }
    println "\n\t ${System.currentTimeMillis() - start} ms"
  }

Ao realizar os testes da Listagem 4, os resultados indicam que o armazenamento em cache ajuda, como mostra a Listagem 5:

Test for range 1-1000
Nonoptimized:             
	 577 ms
Nonoptimized (2nd):       
	 280 ms
Cached sum:                
	 600 ms
Cached sum (2nd run):      
	 50 ms

A Listagem 5 ilustra que a versão não otimizada (da Listagem 1) executa em 577 ms na primeira vez, em comparação com a versão em cache, que leva 600 ms para a primeira execução. Nesses dois casos, a diferença é insignificante. No entanto, a segunda execução da versão não otimizada obtém 280 ms. A diferença entre a primeira e a segunda pode ser atribuída a fatores ambientais, como a coleta de lixo. A segunda execução da versão em cache apresenta um aumento drástico na velocidade, obtendo 50 ms. Quando a segunda execução acontece, todos os valores são armazenados em cache. Agora, estamos medindo a velocidade de leitura a partir de um hash. A diferença entre a primeira execução não otimizada e a primeira versão em cache é desprezível, mas é drástica na segunda execução. Este é um exemplo de armazenamento em cache externo: os resultados gerais são usados por qualquer um que chame o código, portanto, a segunda execução é muito rápida.

O armazenamento das somas em cache faz uma diferença enorme, mas tem suas desvantagens. ClassifierCachedSum não pode mais conter métodos estáticos puros. O cache interno representa o estado, portanto, é necessário que todos os métodos que interagem com ele sejam não estáticos, o que tem um efeito propagador. Seria possível criar uma solução singleton (consulte Recursos), mas isso também aumenta a complexidade. Como a variável do cache está controlada, é necessário assegurar que esteja correta (usando testes, por exemplo). Embora o armazenamento em cache melhore o desempenho, ele não é gratuito: acrescenta a complexidade acidental e uma carga de manutenção ao meu código (consulte Recursos).

Armazenando tudo em cache

Se o armazenamento das somas em cache acelera tanto o código, porque não armazenar também o resultado intermediário que provavelmente se repetirá? Este é o objetivo da Listagem 6:

class ClassifierCached {
  private sumCache, factorCache

  ClassifierCached() {
    sumCache = [:]
    factorCache = [:]
  }

  def sumOfFactors(number) {
    sumCache.containsKey(number) ?
      sumCache[number] :
      sumCache.putAt(number, factorsOf(number).inject(0, {i, j -> i + j}))
  }

  def isFactor(number, potential) {
  number % potential == 0;
}

def factorsOf(number) {
    factorCache.containsKey(number) ?
      factorCache[number] :
      factorCache.putAt(number, (1..number).findAll { i -> isFactor(number, i) })
  }

  def isPerfect(number) {
    sumOfFactors(number) == 2 * number
  }

  def isAbundant(number) {
    sumOfFactors(number) > 2 * number
  }

  def isDeficient(number) {
    sumOfFactors(number) < 2 * number
  }

}

Em ClassifierCached , na Listagem 6, são incluídos os caches para a soma de fatores e para os fatores de um número. Em vez de usar a sintaxe detalhada mostrada na Listagem 3, o operador terciário é usado, o que é surpreendentemente expressivo neste caso. Por exemplo, no método sumOfFactors() , a parte de condição do operador terciário é usada para verificar o cache em relação ao número. No Groovy, a última linha de um método é o valor de retorno dele, assim, o valor em cache é retornado se for obtido um acerto do cache. Do contrário, o número é calculado, colocado no cache, e o valor é retornado. O método putAt() do Groovy retorna o valor adicionado ao hash. A Listagem 7 mostra os resultados:

Test for range 1-1000
Nonoptimized:             
	 577 ms
Nonoptimized (2nd):       
	 280 ms
Cached sum:                
	 600 ms
Cached sum (2nd run):      
	 50 ms
Cached:                    
	 411 ms
Cached (2nd run):          
	 38 ms

A versão totalmente em cache (que é uma variável de instância e uma classe inteiramente nova nessas execuções de teste) obtém 411 ms na primeira execução e excelentes 38 ms na segunda execução, uma vez que o cache tenha sido “carregado”. Embora esses resultados sejam bons, essa abordagem não se escala tão bem. Na Listagem 8, que mostra os resultados do teste de 5.000 números, a versão em cache leva muito mais tempo para carregar, mas, mesmo assim, tem tempos de leitura muito rápidos nas leituras subsequentes:

Test for range 1-5000
Nonoptimized:         
	 6199 ms
Nonoptimized (2nd):   
	 5064 ms
Cached sum:            
	 5962 ms
Cached sum (2nd run):  
	 93 ms
Cached:                
	 6494 ms
Cached (2nd run):      
	 41 ms

O resultado para 10.000 números é bem pior, como mostra a Listagem 9:

Test for range 1-10000
Nonoptimized:
	 43937 ms
Nonoptimized (2nd):
	 39479 ms
Cached sum:         
	 44109 ms
Cached sum (2nd run):
	 289 ms
Cached:              
java.lang.OutOfMemoryError: Java heap space

Como mostra a Listagem 9 , o desenvolvedor responsável pelo código do armazenamento em cache deve se preocupar com a sua correção e condições de execução. Este é um exemplo perfeito de partes móveis: o estado no código em que o desenvolvedor deve manter e dissecar as implicações.

Memoização

A programação funcional se esforça para minimizar as partes móveis integrando mecanismos reutilizáveis ao tempo de execução. A memoização é um recurso integrado a uma linguagem de programação que permite o armazenamento automático em cache de valores de retorno de função recorrentes. Em outras palavras, esse recurso fornece automaticamente o código escrito na Listagem 3 e na Listagem 6. Muitas linguagens funcionais suportam a memoização. Recentemente, o Groovy também incluiu esse suporte (consulte Recursos).

Para memoizar uma função no Groovy, defina como um bloco de códigos e, em seguida, execute o método memoize() para retornar uma função cujos resultados serão armazenados em cache.

Memoizando a soma

Para implementar o armazenamento em cache para sumOfFactors() como na A Listagem 3, o método sumOfFactors() é memoizado, como mostra a Listagem 10:

class ClassifierMemoizedSum {
def static isFactor(number, potential) {
number % potential == 0;
}

def static factorsOf(number) {
(1..number).findAll { i -> isFactor(number, i) }
}

def static sumFactors = { number ->
factorsOf(number).inject(0, {i, j -> i + j})
}
def static sumOfFactors = sumFactors.memoize()

// remainder of code unchanged
}

Na Listagem 10, o método sumFactors() é criado como um bloco de códigos (observe o = e a colocação dos parâmetros). Este método é bem genérico e poderia ser obtido em uma biblioteca qualquer. Para memoizá-lo, o nome sumOfFactors é atribuído como a chamada de método memoize() na referência da função.

A execução da versão memoizada apresenta os resultados mostrados na Listagem 11:

Test for range 1-1000
Nonoptimized:             
	 577 ms
Nonoptimized (2nd):       
	 280 ms
Cached sum:                
	 600 ms
Cached sum (2nd run):      
	 50 ms
Cached:                    
	 411 ms
Cached (2nd run):          
	 38 ms
Partially Memoized:        
	 228 ms
Partially Memoized (2nd):  
	 60 ms

A primeira execução parcialmente memoizada obtém aproximadamente a mesma pontuação que a segunda execução não otimizada. Nos dois casos, a memória e outras questões ambientais foram resolvidas. Assim, as pontuações semelhantes fazem sentido. Contudo, a segunda execução parcialmente memoizada apresenta o mesmo aumento drástico de velocidade que a versão da soma em cache escrita à mão — com a alteração de apenas duas linhas do código original (alterar sumFactors() para um bloco de códigos e fazer com que sumOfFactors() aponte para uma instância memoizada do bloco de códigos).

Memoizando tudo

Da mesma forma que tudo foi armazenado em cache anteriormente, por que não memoizar tudo o que tenha resultados possivelmente reutilizáveis? Essa versão do classificador aparece na Listagem 12:

class ClassifierMemoized {
  def static dividesBy = { number, potential ->
    number % potential == 0
  }
  def static isFactor = dividesBy.memoize()
//  def static isFactor = dividesBy.memoizeAtMost(100)

  def static factorsOf(number) {

    (1..number).findAll { i -> isFactor.call(number, i) }
  }

  def static sumFactors = { number ->
    factorsOf(number).inject(0, {i, j -> i + j})
  }
  def static sumOfFactors = sumFactors.memoize()

  def static isPerfect(number) {
    sumOfFactors(number) == 2 * number
  }

  def static isAbundant(number) {
    sumOfFactors(number) > 2 * number
  }

  def static isDeficient(number) {
    sumOfFactors(number) < 2 * number
  }

Da mesma forma que tudo foi armazenado em cache na Listagem 6, memoizar tudo tem os seus prós e contras. A Listagem 13 mostra os resultados para 1.000 números:

Test for range 1-1000
Nonoptimized:
	 577 ms
Nonoptimized (2nd):
	 280 ms
Cached sum:
	 600 ms
Cached sum (2nd run):
	 50 ms
Cached:
	 411 ms
Cached (2nd run):
	 38 ms
Partially Memoized:
	 228 ms
Partially Memoized (2nd):
	 60 ms
Memoized:
	 956 ms
Memoized(2nd)
19 ms

A memoização de tudo deixa a primeira execução mais lenta, mas a execução subsequente é a mais rápida de todos os casos — , porém somente para conjuntos pequenos de números. Assim como na solução imperativa de armazenamento em cache testada na Listagem 8, conjuntos grandes de números prejudicam drasticamente o desempenho. Na verdade, a versão memoizada fica sem memória com 5.000 números. Entretanto, para que a abordagem imperativa seja robusta, é necessário ter proteções e conhecer bem o contexto de execução — outro exemplo de partes móveis. Com a memoização, a otimização ocorre no nível da função. Observe os resultados da memoização na Listagem 14:

Test for range 1-10000
Nonoptimized:          
	 41909 ms
Nonoptimized (2nd):    
	 22398 ms
Memoized:               
	 55685 ms
Memoized(2nd)           
	 98 ms

Os resultados mostrados na Listagem 14 são produzidos chamando o método memoizeAtMost(1000) em vez de memoize(). Como outras linguagens que suportam a memoização, o Groovy possui vários métodos para ajudar a otimizar os resultados, como mostra a Tabela 1:

Método	Descrição
`memoize()`	Cria uma variante de armazenamento em cache do encerramento
`memoizeAtMost()`	Cria uma variante de armazenamento em cache do encerramento com um limite superior do tamanho do cache
`memoizeAtLeast()`	Cria uma variante de armazenamento em cache do encerramento com um ajuste automático do tamanho do cache e um limite inferior no tamanho do cache
`memoizeBetween()`	Cria uma variante do armazenamento em cache do encerramento com um ajuste automático e os limites superiores e inferiores do tamanho do cache

Na versão imperativa, o desenvolvedor tem a propriedade do código (e é responsável por ele). As linguagens funcionais criam um maquinário genérico, — às vezes, com botões giratórios para customização (na forma de funções alternativas) — , a qual é possível aplicar a construções padrão. As funções são um elemento fundamental da linguagem, por isso, a otimização desse nível oferece uma funcionalidade avançada gratuitamente. As versões de memoização que possuem conjuntos numéricos pequenos deste artigo apresentam um desempenho melhor que o do código de armazenamento em cache escrito à mão.

Conclusão

Esta parte ilustra um tema comum a toda esta série: a programação funcional facilita as coisas ao minimizar as partes móveis. Duas soluções diferentes de armazenamento em cache foram sobrepostas para um caso de uso comum de classificação numérica: testar o mesmo número em relação a várias categorias. A criação manual de um cache é objetiva, mas acrescenta informações de estado e aumenta a complexidade do código. Usando recursos de linguagem funcional, como a memoização, é possível incluir o armazenamento em cache no nível da função, obtendo resultados melhores (sem praticamente nenhuma alteração no código) que os da versão imperativa. A programação funcional elimina as partes móveis, permitindo que a concentração da sua energia na resolução de problemas reais.

***

O IBM Worklight Developer Edition 5.0 simplifica o desenvolvimento de aplicativos da web nativos, híbridos e móveis em diversas plataformas de dispositivo móvel, incluindo iOS, Android, BlackBerry e Windows Phone. Ele fornece recursos de desenvolvimento visual baseados no Eclipse e melhorias de código fonte para ajudar os desenvolvedores a acelerar o desenvolvimento, teste e entrega de aplicativos de dispositivo móvel usando tecnologias abertas como HTML5, Apache Cordova, JavaScript e as populares estruturas do JavaScript, como Dojo, jQuery, e Sencha Touch. Faça agora o download!

Recursos

Aprender

The Productive Programmer (Neal Ford, O’Reilly Media, 2008): O livro mais recente de Neal Ford trata de ferramentas e práticas que ajudam a melhorar sua eficiência em codificação.
Memoização do encerramento: confira as notas sobre o release do recurso de memoização incluído no Groovy 1.8.
O padrão Singleton: o Singleton é um padrão de design bem conhecido da Gangue dos Quatro para manipular o estado global em uma linguagem orientada a objetos.
“Evolutionary architecture and emergent design: Investigating architecture and design“: leia sobre a complexidade essencial x acidental em software.
Navegue na livraria de tecnologia para ver livros sobre este e outros tópicos técnicos.
Zona tecnologia Java do developerWorks: Encontre centenas de artigos sobre quase todos os aspectos da programação Java.

Obter produtos e tecnologias

Groovy: o Groovy é uma linguagem dinâmica na JVM que oferece muitos recursos funcionais.
Avalie produtos IBM da maneira que for melhor para você: faça download da versão de teste de um produto, avalie um produto on-line, use-o em um ambiente de nuvem ou passe algumas horas na SOA Sandbox aprendendo a implementar Arquitetura Orientada a Serviços de modo eficiente.

Discutir

Participe da comunidade do developerWorks. Entre em contato com outros usuários do developerWorks e explore os blogs, fóruns, grupos e wikis voltados para desenvolvedores.

***

Sobre o autor: Neal Ford é arquiteto de software e Meme Wrangler na ThoughtWorks, uma consultoria global de TI. Ele também projeta e desenvolve aplicativos, materiais de instrução, artigos para revistas, treinamentos e apresentações em vídeo/DVD e é autor ou editor de livros que abordam várias tecnologias, incluindo o mais recente The Productive Programmer. Sua especialidade é o projeto e a criação de aplicativos corporativos de grande porte. Também é orador internacionalmente aclamado nas conferências de desenvolvedores ao redor do mundo. Conheça seu website website.

***

Artigo original disponível em: http://www.ibm.com/developerworks/br/library/j-ft9/index.html

De 0 a 10, o quanto você recomendaria este artigo para um amigo?

Powered by: