Visitando uma Collection em ordem inversa

As vezes troco algumas mensagens bem técnicas com alguns colegas pelo GTalk, e aí aparecem algumas charadas interessantes.

O Orseni Campos, um desenvolvedor que eu admiro muito, passou o seguinte problema: “Paulo, como percorrer uma coleção qualquer na ordem inversa de maneira elegante?“. Quando ele disse maneira elegante, pensei que ele queria evitar criar uma lista e acessá-la via lista.get(indice) de trás para frente. Respondi o trivial: que o Collections.reverse resolveria:

public void imprimeInvertidoClassico(Collection<? extends Object>
           colecao) {
  List<Object> invertida = new ArrayList<Object>(colecao);
  Collections.reverse(invertida);
  for (Object objeto : invertida) {
    System.out.println(objeto);
  }
}

Ele não gostou, queria uma maneira de percorrer a coleção invertida sem criar uma coleção temporária, nem mexer na ordem dos objetos da coleção dada.

Desisti. Ele respondeu: “basta visitar a coleção recursivamente, realizando a ação como pós processamento!“. Perfeito. Uma técnica das linguagens funcionais e adorada pelos professores de conceitos de linguagens. Aliás, universidades importantes como MIT utilizam linguagens funcionais no curso introdutório de computação, acreditam que é mais fácil do aluno assimilar os conceitos dos algoritmos (algumas dessas linguagens são dos mesmos criadores do Java).

Então traduzi a idéia para código:

public void imprimeInvertido(Collection<? extends Object> colecao) {
  imprimeInvertido(colecao.iterator());
}

private void imprimeInvertido(Iterator<? extends Object> iterator) {
  if (iterator.hasNext()) {
    Object object = iterator.next();
    imprimeInvertido(iterator);
    System.out.println(object);
  }
}

Aqui, o método imprimeInvertido rapidamente delega a responsabilidade para o que recebe um Iterator como argumento. Este faz uma invocação recursiva no caso de existir um próximo elemento a ser visitado. O importante aqui é que a referência trazida pelo iterator.next() só é processado depois que seus elementos vizinhos forem, realizando o processo na ordem contrária da determinada pelo Iterator. (repare que considerando que a ordem definida pelo Iterator define uma lista, e que toda lista é uma árvore, estamos percorrendo essa ávore de maneira pós-fixa).

Ok, funciona e não cria coleção temporária! Mas se você parar para analisar bem, cada invocação recursiva empilha mais um stackframe, e em cada um temos uma variável temporária (a Object object declarado dentro do if) para ser recuperada quando a invocação retornar. Pensando na última invocação (base da recursão, quando o iterator chegar ao final e não entrar no if (iterator.hasNext())) teremos uma pilha com colecao.size() stackframes, alocando uma memória proporcional ao tamanho da coleção, muito semelhante a ter alocado a coleção temporária para o Collections.reverse.

Você ainda corre o risco de um StackOverflowError por estar gastando memória da pilha em vez do heap! Outra desvantagem é a legibilidade: nós programadores java não estamos acostumados a utilizar recursão para resolver problemas que poderiam ser facilmente resolvidos de maneira iterativa.

O exercício vale para relembrar que é importante manter contato com outras linguagens, para não ficar viciado no mesmo paradigma, o que te limita na hora de encontrar soluções. Em alguns casos a solução recursiva pode ser muito mais trivial de encontrar, desde que você esteja com o paradigma afiado!

Alguma outra maneira interessante de percorrer uma coleção na ordem inversa?

11 Comentários

  1. Michael Nascimento Santos 30/08/2006 at 07:46 #

    Bem, já que você cria uma List no primeiro exemplo, outra opção seria usar ListIterator, que tem previous() e hasPrevious().

  2. Paulo Silveira 30/08/2006 at 08:26 #

    Pode ser, percorro até o fim do iterator, e aí começo a andar de trás pra frente!

  3. Fabio Kung 30/08/2006 at 08:43 #

    Não precisa, tem um método na interface List que te retorna um ListIterator na posição que você quiser:

    ListIterator it = list.listIterator(list.size());
    while(it.hasPrevious()) {
    Object obj = it.previous();
    ...
    }

    Mais elegante, não?

  4. Paulo Silveira 30/08/2006 at 10:12 #

    mais elegante, sem dúvida! mas ainda assim precisa criar a coleção temporária…

  5. Fabio Kung 30/08/2006 at 10:28 #

    mas ainda assim precisa criar a coleção temporária…

    Não tô enxergando onde!

  6. Orseni Ferreira Campos 30/08/2006 at 17:24 #

    Neste caso seria um método pra percorrer na ordem inversa qualquer Collection, e não somente List.
    Por isto o Paulo disse que ainda seria necessário a criação de uma coleção temporária.

    Excelente blog, parabéns a Caelum, nota 10…

  7. Rafael de F. Ferreira 30/08/2006 at 20:18 #

    Oi Paulo.

    Só para constar, numa linguagem funcional daria para transformar essa recursão para estilo CPS (continuation passing style), e o compilador se encarregaria de fazer uma tail-call optimization. Nesse caso a recursão vira um loop e não temos o custo de empilhar os stack frames.

  8. Rafael de F. Ferreira 30/08/2006 at 20:28 #

    Botei em código a idéia de passar para CPS. Em java, sem closures (por pouco tempo, espero), seria assim:

       interface Continuacao {
          public void faz();
       }
       
       class ContVazia implements Continuacao {
          public void faz() {}
       }
       
       public void imprimeInvertido(Collection colecao) {
          imprimeInvertido(colecao.iterator(), new ContVazia());
        }
    
        private void imprimeInvertido(Iterator iterator, final Continuacao cont) {
          if (!iterator.hasNext()) {
             cont.faz();
          }
          else {
            final Object object = iterator.next();
            imprimeInvertido(iterator, new Continuacao() {public void faz() {
               System.out.println(object);
               cont.faz();
            }});
          }
        }
    
    

    O javac não faz tail-call optimization, então nesse caso não faz nenhuma diferença (além do código ficar ininteligível para o pessoal que não fez MAC0316 ou similar…)

  9. Guilherme Silveira 02/09/2006 at 13:49 #

    muito doido! a continuacao de um chama a continuacao do outro… loucura. mas nao da pra ler mesmo.

  10. Fernando Boaglio 06/09/2006 at 17:44 #

    Interessante… fiz uns testes e com collection acima de aproximandamente 10000 itens dá StackOverflowError.

  11. Paulo Silveira 06/09/2006 at 18:07 #

    tem como voce aumentar o tamanho da stack passando -Xss pela linha de comando. se bem me lembro o default era 250k. 10 mil itens de 24 bytes (que é o que um Integer ocupa +-) da o limite

Deixe uma resposta