Bloguefícios: Refatoração de funções recursivas.

Refatoração é uma prática que tem o intuito de modificar a estrutura interna de uma função ou classe, sem alterar se comportamento.

Na semana passada, ao ler tópicos de uma lista sobre linguagem Java, me deparei com uma pergunta sobre stack overflow, causado pela execução de um algoritmo. Tratava-se de um algoritmo de preenchimento de regiões. Partindo-se de um ponto de partida, o algoritmo deveria visitar seus vizinhos, marcando aqueles que possuem cores semelhantes.

Para determinar a semelhança entre duas cores, toma-se a norma Euclidiana da diferença dos vetores de cores. Se esse valor fosse menor que uma dada tolerância, este era julgado semelhante. Os pontos vizinhos aos pontos já visitados também deveriam ser visitados. O Algoritmo para quando não há mais pontos semelhantes.

Segue o pseudo-código do algoritmo recursivo:


visita_ponto(imagem, linha, coluna, cor)
COMECE
        SE linha,coluna NÃO PERTENCE A imagem
        FAÇA
          RETORNO
        FIM
 ponto <- imagem[linha][coluna] 
 SE visitado(ponto) É FALSO ENTÃO
 FAÇA     
  SE     norma(cor(ponto) - cor) É MENOR QUE TOLERÂNCIA ENTÃO  # cor for próxima
  FAÇA
   visitado(ponto) <- VERDADEIRO
   visita_ponto(imagem, linha + 1, coluna)
   visita_ponto(imagem, linha -  1, coluna)
   visita_ponto(imagem, linha, coluna + 1)
   visita_ponto(imagem, linha, coluna -  1)
  FIM
 FIM    
FIM

Note que há 4 pontos de chamada da mesma função. O problema é que este algoritmo estourou a pilha do Java. No algoritmo original, certa de 40 bytes (no mínimo) eram alocados por chamada. Admita esse número é o consumo de byte de uma chamada do método em Java. Para uma imagem de 128x128 pontos (um ícone, por exemplo) poderia chegar a bagatela de 40x128x128 = 65Kbytes consumidos na pilha.. Para uma imagem de 680x480, 11,7 MB !

Claramente, o stack overflow ocorre pelo uso excessivo de memória. A pilha de uma thread em Java é configurada com 2MB de memória, no máximo. A primeira solução é substituir o algoritmo recursivo por um algoritmo iterativo. Com uma pilha explícita, alocada no heap, mais memória pode ser empregada, e sem precisar modificar os parâmetros de chamada da máquina virtual.

No http://www.refactoring.com/catalog/replaceRecursionWithIteration.html há uma descrição sobre esse padrão refatoração. Mas não é apresentado um método geral para obter uma conversão de uma rotina recursiva para outra, com mesma funcionalidade e iterativa.

Entretanto, um método pode ser obtido pela explicitação da pilha. Para tanto, devemos seguir alguns passos para o procedimento:

Criação de pilha explícita.
Criação de um laço ENQUANTO que monitora a condição de retorno da rotina, ou seja, do fim da iteração, ou do que antes era a condição de retorno da chamada mais profunda do algoritmo recursivo.
Criação de uma variável rótulo, que mantém informação do estado, ou do último ponto de onde foi feita uma "chamada". É equivalente a guardar o endereço de retorno da rotina.
Testes para executar o código do ponto onde havia parado a computação. Se a linguagem possuir algum tipo de GOTO, a implementação fica mais fácil.
Analise os parâmetros, para determinar quais são constantes, ou aqueles que modificam com um padrão previsível (como um contador, por exemplo). Eles podem ser retirados da pilha explícita.

Aplicando os princípios acima citados, vamos reescrever o pseudo-código:


visita_ponto2(imagem, linha, coluna, cor)
COMECE
 pilha_linha  := vetor(0..(linha*coluna)-1)
 pilha_coluna := vetor(0..(linha*coluna)-1)
 pilha_imagem := vetor(0..(linha*coluna)-1)
 pilha_rotulo  := vetor(0..(linha*coluna)-1) # ponto de parada
 pos_pilha  := inteiro
 
        

 pilha_linha[0] <- linha
 pilha_coluna[0] <- coluna
 pilha_imagem[0] <- imagem
 pilha_rotulo[0] <- 0
 pos_pilha <- 1

 ENQUANTO pos_pilha FOR MAIOR QUE 0 
 FAÇA
  linha <- pilha_linha[0] 
  coluna <- pilha_coluna[0].
  imagem <- pilha_imagem[0]
  # início do antigo algoritmo.
                SE linha,coluna NÃO PERTENCE A imagem
                FAÇA
                  pos_pilha <- pos_pilha - 1
                  CONTINUE
                FIM
  ponto <- imagem[linha][coluna] 
  SE visitado(ponto) É FALSO ENTÃO
  FAÇA     
   SE     norma(cor(ponto) - cor) É MENOR QUE TOLERÂNCIA ENTÃO  # cor for próxima
   FAÇA
    visitado(ponto) <- VERDADEIRO
    SE pilha_rotulo[0] É 0 ENTÃO
    FAÇA
     pilha_rotulo[pos_pilha] <- 1 # ponto de retorno
     pos_pilha <- pos_pilha + 1
     pilha_linha[pos_pilha] <- linha + 1
     pilha_coluna[pos_pilha] <- coluna
     pilha_imagem[pos_pilha] <- imagem
     pilha_rotulo[pos_pilha] <- 0
     CONTINUE
    FIM
    SE pilha_rotulo[0] É 1 ENTÃO
    FAÇA
     pilha_rotulo[pos_pilha] <- 2 # ponto de retorno
     pos_pilha <- pos_pilha - 1
     pilha_linha[pos_pilha] <- linha - 1
     pilha_coluna[pos_pilha] <- coluna
     pilha_imagem[pos_pilha] <- imagem
     pilha_rotulo[pos_pilha] <- 0
     CONTINUE
    FIM
    SE pilha_rotulo[0] É 2 ENTÃO
    FAÇA
     pilha_rotulo[pos_pilha] <- 3 # ponto de retorno
     pos_pilha <- pos_pilha
     pilha_linha[pos_pilha] <- linha
     pilha_coluna[pos_pilha] <- coluna + 1
     pilha_imagem[pos_pilha] <- imagem
     pilha_rotulo[pos_pilha] <- 0
     CONTINUE
    FIM
    SE pilha_rotulo[0] É 3 ENTÃO
    FAÇA
     pilha_rotulo[pos_pilha] <- 4 # ponto de retorno
     pos_pilha <- pos_pilha + 1
     pilha_linha[pos_pilha] <- linha
     pilha_coluna[pos_pilha] <- coluna - 1
     pilha_imagem[pos_pilha] <- imagem
     pilha_rotulo[pos_pilha] <- 0
     CONTINUE
    FIM
   FIM
  FIM 
  pos_pilha <- pos_pilha - 1 # Se estamos aqui, temos 4 nós visitados.
 FIM
FIM

Note que o código ficou muito maior. A pilha agora é uma variável, que pode ser declarada no heap, na pilha, ou mesmo estaticamente. Analisando ainda mais o pseudo-código resultante, nota-se:

É possível monitorar a posição da pilha e reportar um possível stack overflow.
O argumento imagem é sempre constante. Pode então ser retirado do algoritmo.

No algoritmo original, em Java, haviam cerca de 10 argumentos, sendo que apenas 2 (linha e coluna) precisavam ser armazenados. Admitindo-se que a linha,coluna e o rótulo são variáveis inteiras, de 32 bits, temos um consumo de 12 bytes por iteração.


visita_ponto3(imagem, linha, coluna, cor)
COMECE
 pilha_linha  := vetor(0..(linha*coluna)-1)
 pilha_coluna := vetor(0..(linha*coluna)-1)
 pilha_rotulo  := vetor(0..(linha*coluna)-1) # ponto de parada
 pos_pilha  := inteiro
 
 pilha_linha[0] <- linha
 pilha_coluna[0] <- coluna
 pilha_rotulo[0] <- 0
 pos_pilha <- 1

 ENQUANTO pos_pilha FOR MAIOR QUE 0 
 FAÇA
  SE pos_pilha FOR IGUAL A linha*coluna ENTÃO
  FAÇA
   SINALIZAR ESTOURO DE PILHA
  FIM

  linha <- pilha_linha[0] 
  coluna <- pilha_coluna[0].
  imagem <- pilha_imagem[0]
  # início do antigo algoritmo.
  SE linha,coluna NÃO PERTENCE A imagem
  FAÇA
    pos_pilha <- pos_pilha - 1
    CONTINUE
  FIM
  ponto <- imagem[linha][coluna] 
  SE visitado(ponto) É FALSO ENTÃO
  FAÇA     
   SE     norma(cor(ponto) - cor) É MENOR QUE TOLERÂNCIA ENTÃO  # cor for próxima
   FAÇA
    SE pilha_rotulo[0] É 0 ENTÃO
    FAÇA
     visitado(ponto) <- VERDADEIRO
     pilha_rotulo[pos_pilha] <- 1 # ponto de retorno
     pos_pilha <- pos_pilha + 1
     pilha_linha[pos_pilha] <- linha + 1
     pilha_coluna[pos_pilha] <- coluna
     pilha_rotulo[pos_pilha] <- 0
     CONTINUE
    FIM
    SE pilha_rotulo[0] É 1 ENTÃO
    FAÇA
     pilha_rotulo[pos_pilha] <- 2 # ponto de retorno
     pos_pilha <- pos_pilha - 1
     pilha_linha[pos_pilha] <- linha - 1
     pilha_coluna[pos_pilha] <- coluna
     pilha_rotulo[pos_pilha] <- 0
     CONTINUE
    FIM
    SE pilha_rotulo[0] É 2 ENTÃO
    FAÇA
     pilha_rotulo[pos_pilha] <- 3 # ponto de retorno
     pos_pilha <- pos_pilha
     pilha_linha[pos_pilha] <- linha
     pilha_coluna[pos_pilha] <- coluna + 1
     pilha_rotulo[pos_pilha] <- 0
     CONTINUE
    FIM
    SE pilha_rotulo[0] É 3 ENTÃO
    FAÇA
     pilha_rotulo[pos_pilha] <- 4 # ponto de retorno
     pos_pilha <- pos_pilha + 1
     pilha_linha[pos_pilha] <- linha
     pilha_coluna[pos_pilha] <- coluna - 1
     pilha_rotulo[pos_pilha] <- 0
     CONTINUE
    FIM
   FIM
  FIM 
  pos_pilha <- pos_pilha - 1 # Se estamos aqui, temos 4 nós visitados.
 FIM
FIM

Evidentemente, a segunda e terceira versão do código é muito maior, devido a repetição. Quanto a isso, podemos modificar o código de iteração, usando uma tabela para calcular as coordenadas do vizinhos a serem visitados.


#tabela auxiliar.
tab := [ +1  0;
  -1  0;
   0 -1;
   0 +1]

visita_ponto4(imagem, linha, coluna, cor)
COMECE
 pilha_linha  := vetor(0..(linha*coluna)-1)
 pilha_coluna := vetor(0..(linha*coluna)-1)
 pilha_rotulo  := vetor(0..(linha*coluna)-1) # ponto de parada
 pos_pilha  := inteiro
 
 pilha_linha[0] <- linha
 pilha_coluna[0] <- coluna
 pilha_rotulo[0] <- 0
 pos_pilha <- 1

 ENQUANTO pos_pilha FOR MAIOR QUE 0 
 FAÇA
  SE pos_pilha FOR IGUAL A linha*coluna ENTÃO
  FAÇA
   SINALIZAR ESTOURO DE PILHA
  FIM

  linha <- pilha_linha[0] 
  coluna <- pilha_coluna[0].
  imagem <- pilha_imagem[0]
  # início do antigo algoritmo.
                SE linha,coluna NÃO PERTENCE A imagem
                FAÇA
                  pos_pilha <- pos_pilha - 1
                  CONTINUE
                FIM
  ponto <- imagem[linha][coluna] 
  SE visitado(ponto) É FALSO ENTÃO
  FAÇA     
   SE     norma(cor(ponto) - cor) É MENOR QUE TOLERÂNCIA ENTÃO  # cor for próxima
   FAÇA
    visitado(ponto) <- VERDADEIRO
    SE pilha_rotulo[0] É MENOR QUE 4 ENTÃO
    FAÇA
     pilha_rotulo[pos_pilha] <- pilha_rotulo[pos_pilha] + 1 # ponto de retorno
     pilha_linha[pos_pilha + 1] <- linha + tab[rotulo][0]
     pilha_coluna[pos_pilha + 1] <- coluna + tab[rotulo][1]
     pilha_rotulo[pos_pilha + 1] <- 0
     pos_pilha <- pos_pilha + 1
     CONTINUE
    FIM
   FIM
  FIM 
  pos_pilha <- pos_pilha - 1 # Se estamos aqui, temos 4 nós visitados.
 FIM
FIM

Interpretação Geométrica

Vejamos uma imagem, de 5 x 5 posições. Começando-se pelo ponto central, vamos escrever a ordem de descobrimento do algoritmo:

00	09	10	19	20
01	08	11	18	21
02	07	12	17	22
03	06	13	16	23
04	05	14	15	24

Veja que existem uma profundiade de chamadas: 0 -> 24. Ou seja, tivemos uma pilha com profundidade máxima de 25 chamadas. Em um caso mais geral, o número de chamadas será de linhas x colunas (pior caso).

Esse algoritmo se expande como se fosse uma curva. Seria mais conveniente, entretanto, que ele se espalha-se de acordo com uma fronteira.

Nesse caso, se faz necessário o emprego de uma outra estrutura de dados, diferente da pilha, pois os termos já visitados precisariam ser descartados. Essa estrutura de dados é uma fila.

O tamanho da memória empregada aqui é muito menor. O número máximo de elementos é da ordem do perímetro da tabela, que é 4 x linhas x colunas. no caso de uma tabela quadrada.

Fazendo a conversão final do algoritmo, para que este empregue a fila, temos:


#tabela auxiliar. relativa
tab_rel := [ -1  0;
      +2  0;
      -1 -1;
       0 +2]

visita_ponto5(imagem, linha, coluna, cor)
COMECE
 dqueue := nova dqueue[2*(linha + coluna)]
 
 dqueue.inserirFrente(linha, coluna)
 
 ENQUANTO dqueue.vazia() FOR FALSO 
 FAÇA
  tamanho_da_borda <- dqueue.comprimento()
  PARA TODA linha, coluna EM dqueue 
  FAÇA
                        SE linha,coluna NÃO PERTENCE A imagem
                        FAÇA
                            CONTINUE
                        FIM
   ponto <- imagem[linha][coluna]
   SE norma(cor(ponto) - cor) ENTÃO
   FAÇA
    visitado(ponto) <- VERDADEIRO
   FIM
  FIM
  
  ENQUANTO tamanho_da_borda > 0
  FAÇA 
   tamanho_da_borda <- tamanho_da_borda - 1
   linha, coluna <- dqueue.retireTras()
   ponto <- imagem[linha][coluna]
   SE visitado(ponto) É VERDADEIRO ENTÃO
   FAÇA
    PARA I := 0..3 
    FAÇA
     linha <- linha + tab[I][0]
     coluna <- coluna + tab[I][0]
     ponto <- imagem[linha][coluna]
     SE visitado(ponto) É FALSO
      dqueue.inserirFrente(linha, coluna)
     FIM
    FIM
   FIM
  FIM
 FIM
FIM

Por fim, vamos fazer um comparação com uma tabela de algoritmos x imagem:

Algoritimo/Dimensões	300x200	640x480	1024x768
recursivo(pilha)	2.29MB	11.72MB	30.00MB
iterativo(pilha)	703.12kB	3.52MB	9.00MB
iterativo(fila)	7.81kB	17.50kB	28.00kB

Conclusões

Um algoritmo recursivo pode ser convertido para um equivalente iterativo, com o emprego de uma pilha explícita.

Com um pouco mais de análise pode-se chegar a uma simplificação da pilha e do código. Nesse exemplo, a complexidade do algoritmo com pilhas era de O(MN) (M=linhas, N=colunas) foi baixado para O(M+N). O método não deve ser empregado como única possibilidade de refatoração do algoritmo.

O resultado é uma melhoria de qualidade o código, sem dúvida. Entretanto, outras análises podem trazer algoritmo ainda mais eficientes.

Marcadores: computation

Bloguefícios

quarta-feira, novembro 01, 2006

Refatoração de funções recursivas.

Interpretação Geométrica

Conclusões

0 Comentários:

Quem sou eu

Postagens anteriores