Acabar com os globais?

Question

Eu tenho um conjunto de objetos de árvore com profundidade em torno de 20 anos.Cada um dos nós desta árvore precisa de acesso à raiz de sua árvore.

Algumas soluções:

1. Cada nó pode armazenar uma referência diretamente à raiz (desperdiça memória)
   • Posso calcular a raiz em tempo de execução "subindo" (desperdiça ciclos)
   • Posso usar campos estáticos (mas isso equivale a globais)

Alguém pode fornecer um design que não use global (em qualquer variação), mas seja mais eficiente que o número 1 ou o número 2 na memória ou nos ciclos, respectivamente?

Editar: Como tenho um conjunto de árvores, não posso simplesmente armazená-lo de forma estática, pois seria difícil diferenciar as árvores.(obrigado maccullt)

Answer 1

Passe a raiz como parâmetro para qualquer função no nó que precise dela.

Editar:As opções são realmente as seguintes:

1. Armazene a referência raiz no nó
2. Não armazene a referência raiz
3. Armazene a referência raiz em um formato global
4. Armazene a referência raiz na pilha (minha sugestão, padrão de visitante ou recursiva)

Acho que são todas as possibilidades, não existe opção 5.

Answer 2

Por que você precisaria acabar com os globais?Eu entendo o estigma de que os globais são ruins e tudo mais, mas às vezes apenas ter uma estrutura de dados global com todos os elementos é a solução mais rápida.

Você faz uma troca:clareza de código e menos problemas futuros de desempenho.Esse é o significado de 'Não otimizar ainda'.Como você está no estágio de otimização, às vezes é necessário eliminar algumas práticas de legibilidade e boas práticas de programação em favor do desempenho.Quero dizer, hacks bit a bit não são legíveis, mas são rápidos.

Não tenho certeza de quantos objetos de árvore você tem, mas eu pessoalmente escolheria a opção um.A menos que você esteja lidando com mais de milhares de árvores, os ponteiros realmente não equivalerão a muito mais do que algumas strings.Se a memória for realmente um problema muito importante, tente os dois métodos (eles parecem bastante simples de implementar) e execute-o por meio de um criador de perfil.Ou use o excelente Explorador de processos.

Editar:Um dos aplicativos em que estou trabalhando tem uma árvore de nós contendo cerca de 55 mil nós.Construímos a estrutura em árvore, mas também mantemos um array para pesquisas O(1).Muito melhor que o O(m*n) que obtíamos ao usar um método recursivo FindNodeByID.

Answer 3

Passar a raiz como parâmetro geralmente é melhor.Se você estiver usando algum tipo de iterador para navegar na árvore, uma alternativa é armazenar uma referência para root nela.

Answer 4

O ponto nº 1 é uma otimização prematura da memória.O nº 2 é uma otimização de desempenho prematura.Você criou o perfil do seu aplicativo para determinar se gargalos de memória ou CPU estão causando problemas para você?Se não, por que sacrificar um design mais sustentável por uma “otimização” que não ajuda seus usuários?

Eu recomendo fortemente que você escolha o número 2.Sempre que você armazena algo que poderia calcular, o que você está fazendo é armazenar em cache.Há alguns momentos em que o cache é uma boa ideia, mas também é uma dor de cabeça de manutenção.(Por exemplo, e se você mover um nó de uma árvore para outra alterando seu pai, mas esquecer de atualizar também o campo raiz?) Não armazene em cache se não for necessário.

Answer 5

Você poderia derivar uma classe de TreeView e depois adicionar uma propriedade estática singleton.Dessa forma, você está efetivamente adicionando um campo global que faz referência à instância única da classe, mas tem a vantagem de ter o escopo do namespace para essa classe.

Answer 6

Ignorando a aversão às classes internas, eu poderia definir uma classe Árvore e definir os nós como classes internas.Cada um dos nós teria acesso ao estado de sua árvore, incluindo sua raiz.

Isso pode acabar sendo igual ao número 1, dependendo de como o Java relaciona os nós aos seus pais.(Não tenho certeza e terei que traçar um perfil)