List ou HashMap? That's the question

Bem, não sei se é o local certo, mas vamos lá. Se não for, me desculpem.

Tenho duas classes: Node e Atributo. Node possui uma coleção de atributos. Atributo contém nome e valor como atributos. Segue abaixo a estrutura:

Classe Node:

public class Node {
	private int nivel;
	private String nome;
	private List<Atributo> atributos;
	
	private boolean grupo;
}

Classe Atributo:

public class Atributo {
	private String nome;
	private String valor;
}

Preciso acessar um atributo da coleção, utilizando o nome.

A minha dúvida é quanto ao tipo da coleção. As duas abordagens que pensei são as seguintes:

[list]Posso usar uma lista de objetos como está no exemplo e criar um método para interar na lista e procurar o atributo ou[/list]
[list]Fazer com que atributos seja um HashMap<String, String> e simplesmente dar um get na key que necessito.[/list]

Acontece que acabei de sair de uma parte do livro de Projeto de Software do Braude que fala exatamente sobre eficiência, elegância, robustez, flexibilidade, etc.

O que acho do assunto:

[list]Me parece que a primeira abordagem é mais elegante e clara, facilitando a manutenção e a flexibilidade, mas menos eficiente, pois posso ter laços aninhados, já que também trabalho com uma coleção de nodes.[/list]
[list]A segunda é bem menos elegante e clara, mas me parece mais eficiente. A não ser que o algoritmo para dar um get também faça uso de um laço.[/list]

E aí? Qual a opnião de vocês. Não tem pressa, pois já estou com as duas formas implementadas e backupeadas, não estando o projeto parado por conta disso. Seria uma questão de “plugar” uma solução ou outra.

Obrigado.

Se os resultados forem ser acessados por uma chave, me parece que a melhor solução é o HashMap.

Algo como:

public class Node {
	private int nivel;
	private String nome;
	private HashMap<String, String> atributos;
	private boolean grupo;
}

A idéia é essa. Conversei com o pessoal aqui e chegamos a conclusão de que se não tem a previsão de entrada de mais “atributos” em atributo =) que deveria usar esta abordagem mesmo.

Mas a opnião do GUJ sempre é bem-vinda. Quem quiser, pode continuar mandando os seus pontos de vista.

Respondendo ao [dc.rec1]

Sim, será acessada por chave. Um ex.

atributos.put("name","Celso");
if (node.getAtributos().get("name").equals("Celso"){
  //Faz alguma coisa
}

Minha dúvida é sobre elegancia, flexibilidade, etc. etc.

Abraços.
Celso Martins

Pelo que já trabalhei, caso você não vá ter muitos atributos acessados opte pela abordagem de List, pois economiza em memória e estrutura. Mas se você tiver uma quantidade bem razoável de atributos das quais os índices são altamente acessados, o HashMap (ou HashTable) é bem mais indicado. A estrutura de chave->valor usando hashs é bem estável e segura em performance mesmo com várias chaves/valores.

Até!

[quote=maquiavelbona]Pelo que já trabalhei, caso você não vá ter muitos atributos acessados opte pela abordagem de List, pois economiza em memória e estrutura. Mas se você tiver uma quantidade bem razoável de atributos das quais os índices são altamente acessados, o HashMap (ou HashTable) é bem mais indicado. A estrutura de chave->valor usando hashs é bem estável e segura em performance mesmo com várias chaves/valores.

Até![/quote]

Entendi, mas o algoritmo de busca de Key da HashMap não seria mais eficiente do que um simples laço for feito por mim num método da classe Node?

E com certeza o num de atributos é bem pequeno. Não sei se terá caso que passará de 10.

Vlw!

[quote=celso.martins]…

Entendi, mas o algoritmo de busca de Key da HashMap não seria mais eficiente do que um simples laço for feito por mim num método da classe Node?[/quote]
Sim, ele é mais eficiente. Mas com um Map você leva junto toda a estrutura rígida de chave->valor e o espalhamento de objetos. Talvez você não goste também, mas o Map aceita como chave null.

[quote=celso.martins]…
E com certeza o num de atributos é bem pequeno. Não sei se terá caso que passará de 10.

Vlw![/quote]
Se for ter poucos objetos, acho que utilizar um List ou implementar um List para que tenha um método mais adequado pode ser mais econômico.

Até!

[quote=maquiavelbona][quote=celso.martins]…

Entendi, mas o algoritmo de busca de Key da HashMap não seria mais eficiente do que um simples laço for feito por mim num método da classe Node?[/quote]
Sim, ele é mais eficiente. Mas com um Map você leva junto toda a estrutura rígida de chave->valor e o espalhamento de objetos. Talvez você não goste também, mas o Map aceita como chave null.

[quote=celso.martins]…
E com certeza o num de atributos é bem pequeno. Não sei se terá caso que passará de 10.

Vlw![/quote]
Se for ter poucos objetos, acho que utilizar um List ou implementar um List para que tenha um método mais adequado pode ser mais econômico.[/quote]

Cara, tuas considerações foram muito importantes. Eu não tinha pensado por esse lado. Vou analisa-las com carinho.

Muito obrigado!

De início acho que vc deve pensar qual forma é a mais clara para uma pessoa entender o código (ou vc mesmo no futuro :slight_smile: ). Eu tenderia a usar List porque só pelo tipo vc já identifica e também na classe Atributo é fácil saber que tem um nome e valor. No HashMap<String, String> você fica sabendo que são atributos pelo nome da variável, mas depois tem que interpretar o código pra saber que coisa é a String key e que coisa é a String value do HashMap.

Em questão de funcionalidade haveria diferença se os nomes dos Atributos pudessem se repetir, daí não daria para usar o HashMap.

E não existe necessidade de ficar pensando qual é o mais rápido se não houver problema de performance, pense em primeiro lugar na clareza da idéia que você quer passar.

[quote=Renato K. Araujo]De início acho que vc deve pensar qual forma é a mais clara para uma pessoa entender o código (ou vc mesmo no futuro :slight_smile: ). Eu tenderia a usar List porque só pelo tipo vc já identifica e também na classe Atributo é fácil saber que tem um nome e valor. No HashMap<String, String> você fica sabendo que são atributos pelo nome da variável, mas depois tem que interpretar o código pra saber que coisa é a String key e que coisa é a String value do HashMap.

Em questão de funcionalidade haveria diferença se os nomes dos Atributos pudessem se repetir, daí não daria para usar o HashMap.

E não existe necessidade de ficar pensando qual é o mais rápido se não houver problema de performance, pense em primeiro lugar na clareza da idéia que você quer passar.[/quote]

A questão da clareza me preocupou bastante. As 5hs da manhã da quinta-feira ultima sobre a minha cama, com a minha esposa no 15º sono, pensei nessa solução do HashMap devido ao aninhamento dos laços. Mas pensei muito na clareza que a abordagem com a classe Atributo me trazia. Por isso a dúvida. A sua análise junto com a análise do [maquiavelbona] mostraram que a minha preocupação fazia sentido. Como você também mencionou a questão da clareza, estou bem inclinado a adotar esta abordagem da lista de Atributos.

Obrigado!

para dar uma satisfação, mostrar como ficou a brincadeira e tirar uma última dúvida boba.

			// Adiciona os atributos format, min, max, nullSupression, nullValue e 
			// altera o atributo type para o formato de XmlNode
			Hashtable<String, String> hashFormatXmlNode = new Hashtable<String, String>();
			hashFormatXmlNode.put("A", "string");
			hashFormatXmlNode.put("N", "number");
			
			Hashtable<String, String> hashTypeXmlNode = new Hashtable<String, String>();
			hashTypeXmlNode.put("A", "xsd:string");
			hashTypeXmlNode.put("N", "xsd:decimal");
			
			if (listaDeNodes.get(i).getValorAtributo("type").equalsIgnoreCase("G")){
				listaDeNodes.get(i).removeAtributo("type");
			}else{
				// Cria o atributo format
				Atributo format = new Atributo();
				format.setNome("format");
				format.setValor(
						hashFormatXmlNode.get(listaDeNodes.get(i).getValorAtributo("type")));
				listaDeNodes.get(i).getAtributos().add(format);
				format = null;

				// Acerta o type para o formato correto
				listaDeNodes.get(i).updateValorAtributo("type", 
						hashTypeXmlNode.get(listaDeNodes.get(i).getValorAtributo("type")));
			}

A linha 20 é necessária? Como podem perceber estou dentro de um laço. Há uns 2 anos atrás me contaram que isso deixa o GC mais eficiente e garante o não acumulo de objetos, quando estamos dentro de um laço.

Abraços

Humm… na verdade usar Map é a solução mais eficiente e clara. (ambas) utilizar a primeira opção é POG.
Repare que vc não precisa do list já que vc não utiliza get(i). O list é apenas para agrupar.
Como o nodo só pode ter um atributo com o mesmo nome tb não precisa de repetidos, logo Set seria suficiente.
No fim vc quer uma pesquisa por nome o que significa ter um Map

public class Node {
	private int nivel;
	private String nome;
	private Map<Atributo> atributos;
	
	private boolean grupo;

         public Atributo getAtributo(String nome ){
           return atributos.get(nome);
         }

        public void addAtributo(Atributo a){
           atributos.put(a.nome,a);
         }

         public Iterator<Atributo> getAtributos(){
return            atributos.getValues().iterator();
         }
}

Agora, qual implementação de Map usar ?
Se precisar de manter a ordem de iteração igual à de insersão use LinkedHashMap.
Se não use TreeMap. Como a chave são strings, TreeMap é mais eficiente que HashMap.

[quote=sergiotaborda][quote=celso.martins]
O que acho do assunto:

[list]Me parece que a primeira abordagem é mais elegante e clara, facilitando a manutenção e a flexibilidade, mas menos eficiente, pois posso ter laços aninhados, já que também trabalho com uma coleção de nodes.[/list]
[list]A segunda é bem menos elegante e clara, mas me parece mais eficiente. A não ser que o algoritmo para dar um get também faça uso de um laço.[/list]
[/quote]

Humm… na verdade usar Map é a solução mais eficiente e clara. (ambas) utilizar a primeira opção é POG.
Repare que vc não precisa do list já que vc não utiliza get(i). O list é apenas para agrupar.
Como o nodo só pode ter um atributo com o mesmo nome tb não precisa de repetidos, logo Set seria suficiente.
No fim vc quer uma pesquisa por nome o que significa ter um Map

public class Node {
	private int nivel;
	private String nome;
	private Map<Atributo> atributos;
	
	private boolean grupo;

         public Atributo getAtributo(String nome ){
           return atributos.get(nome);
         }

        public void addAtributo(Atributo a){
           atributos.put(a.nome,a);
         }

         public Iterator<Atributo> getAtributos(){
return            atributos.getValues().iterator();
         }
}

Agora, qual implementação de Map usar ?
Se precisar de manter a ordem de iteração igual à de insersão use LinkedHashMap.
Se não use TreeMap. Como a chave são strings, TreeMap é mais eficiente que HashMap.[/quote]

Cara, Você está usando uma combinação das duas soluções? Foi o que entendi com a implementação e com o “(ambas)” =).
Não sabia que era possível algo do tipo.

A idéia seria usar essa LinkedHashMap mesmo.

Vou implementar neste momento esta nova versão.

[Editado - Agora acho que entendi] - o atributo seria

private LinkedHashMap<String, Atributo> atributos 

só agora vi o addAtributo.
Mas cara, assim eu não teria o nome repetido na Key e no atributo nome da classe atributo?

Obrigado Sérgio.

Abraços

Não estou usando uma combinação das soluções. Estou-lhe apresentado a mais clara e eficiente ( que é que vc pediu :wink: )
Vc disse que usar list era mais clara e menos eficiente e que map era ao contrario.
O que estou dizendo é que map é simultaneamente a mais clara e mais eficiente e que List é pog.

Não. É Map mesmo.

private final Map<String, Atributo> atributos = new LinkedHashMap<String, Atributo> ();

Vc estava preocupado com eficiencia e clareza … usar o tipo mais polimorfico possivel é o mais eficiente e claro
( isso é conhecido pela máxima “Programe para interfaces”)
Vc quer maximizar o polimorfismo das suas variáveis. Isso é bom OO.

hum… O objeto que está dentro do atributo é o mesmo que é a chave dentro do Map. Não ha repetição alguma.
Além disso faz sentido se pensar que os atributos são classificados pelo seu nome. É isso que significa :

atributos.put(atributo.nome, atributo);

Creio que entendi onde você quis chegar. Seria “quase” uma junção das duas soluções já que manteve a classe Atributo e ainda usou um Hash (nesse caso o LinkedHashMap). =)

Entendi a questão da Key também e fez bastante sentido.

E o que eu queria era isso mesmo. (Aliás como sempre perturbo aqui no GUJ). A solução mais elegante. Nunca imaginaria que a solução com List seria POG. Creio que as razões que você apresentou são suficientes.

Gostei da sua explicação. Gosto sempre de refinar as soluções, mas nem sempre sei como.

Obrigado!

Abraços!

[quote=celso.martins]Creio que entendi onde você quis chegar. Seria “quase” uma junção das duas soluções já que manteve a classe Atributo e ainda usou um Hash (nesse caso o LinkedHashMap). =)

Entendi a questão da Key também e fez bastante sentido.

E o que eu queria era isso mesmo. (Aliás como sempre perturbo aqui no GUJ). A solução mais elegante. Nunca imaginaria que a solução com List seria POG. Creio que as razões que você apresentou são suficientes.

Gostei da sua explicação. Gosto sempre de refinar as soluções, mas nem sempre sei como.

Obrigado!

Abraços![/quote]
Mas não é POG. Map tem um uso bem específico: quando o acesso direto ao valor necessite diretamente da chave. Num caso onde você queira espalhar atributos com mesmos nomes, List garante que você possa ter mais de um até igual(Exemplo: Qualquer uso de XML. Já pensou o que seria do HTMl se fosse transformado em Set?), caso queira percorrer objetos Atributos que você tenha necessidade deles serem agrupados, Map se torna POG. Agora, quando você vai ter X elementos, na maior parte diferentes e/ou únicos, na qual a consistência não seja direta mas uma simples referência, o Map começa a fazer sentido(Exemplo: estrutura de mensagens de algum serviço).

Falar que algo é POG sem entender realmente o que vai fazer com isso é perda de tempo.

E quanto a setar null numa variável para deixá-la elegível ao gc pode ser um tiro no pé. Um objeto é automaticamente limpo após o seu uso ( a não ser que você tenha alguma referência forte a ele ) e alguns posts no guj mostram que isso pode fazer com o objeto espere mais uma vez o gc rodar para ser coletado ( pois o gc roda duas vezes antes de coletar algo ).

Até!

[quote=maquiavelbona]
Mas não é POG. Map tem um uso bem específico: quando o acesso direto ao valor necessite diretamente da chave. Num caso onde você queira espalhar atributos com mesmos nomes, List garante que você possa ter mais de um até igual(Exemplo: Qualquer uso de XML. Já pensou o que seria do HTMl se fosse transformado em Set?), caso queira percorrer objetos Atributos que você tenha necessidade deles serem agrupados, Map se torna POG. Agora, quando você vai ter X elementos, na maior parte diferentes e/ou únicos, na qual a consistência não seja direta mas uma simples referência, o Map começa a fazer sentido(Exemplo: estrutura de mensagens de algum serviço).

Falar que algo é POG sem entender realmente o que vai fazer com isso é perda de tempo.

E quanto a setar null numa variável para deixá-la elegível ao gc pode ser um tiro no pé. Um objeto é automaticamente limpo após o seu uso ( a não ser que você tenha alguma referência forte a ele ) e alguns posts no guj mostram que isso pode fazer com o objeto espere mais uma vez o gc rodar para ser coletado ( pois o gc roda duas vezes antes de coletar algo ).

Até![/quote]

Opa… dessa do GC eu não sabia. Vou retirar essa bala do meu pé. E quanto aos atributos, não terei atributos repetidos. Eles serão únicos.

Algumas pessoas mais curiosas podem estar se perguntando: “O que esse caboclo está fazendo”. Bem eu ia colocar essa dúvida aqui há cerca de 1 mês atrás. Vou postar agora em outra thread.

Abraços e obrigado.
Celso

Quando disse que List era POG não foi para ofender ninguém, mas para chocar o nosso amigo a entender
que o problema se resolve de outra forma. ( shock to enlightment)

Nas condições que ele tinha em que os atributos são unicos ( uma tag tem atributos unicos) Map é mais simples de usar (claresa).
Uma iteração de for poderia também funcionar. Aliás poderia até usar list.contains modificando o equals do atributo para
comparar os nomes. O contains inclui o for. Assim o código continuaria legível, mas menos claro porque usa o truque do equals.
Mesmo assim a procura com o list e o for é O(n) enquanto que o map - TreeMap - é O(log n ) , log n < n. Então a eficiencia tb é melhor usando Map. A unica coisa que poderíamos estar interessados, e que a lista oferece, é a ordem de inserção. Mas isso é facil com LinkedHashMap. (tudo bem, tb não entendo porque precisa disso, mas isso é uma escolha de implementação)

Ou seja, o que realmente se quer é : clareza e eficiência. E para ter isso usar Map é sem duvida melhor que List.
Mesmo que a eficiência fosse igual, ainda assim Map seria escolhido porque é mais claro.

List só deve ser usando quando : ha repetidos , ou , tem que ser utilizado leitura por índice.
Mas leitura por índice é muiiiiiittttooooo raro ser necessário. Quase sempre é possível converter para Map ou Queue.