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
