Memoria X Processamento ( List.contains Ou Iteraçao de array )

Programação Java
#1

Galera eu estava programando uma rotina que precisa buscar um conteudo string num array de objetos.

Todo sistema ja está feito e o metodo me retorna um array de objetos de aproximadamente 15 posiçoes.

Eu fiz de duas formas e gostaria de saber na opniao de voces qual é a melhor. A primeira foi a primeira que me ocorreu, iterei o array usando o velho amigo FOR e fiz um if ( “chave”.equals(MeuArray.get(x) ) …
E outra forma que me veio na cabeça foi fazer um get do array todo passando-o para um list e utilizar o metodo List.Contains(“chave”).

Gostaria de saber qual o melhor método e porque, na opnião de vocês.

#2

Se você fosse usar List, seria melhor usar um Iterator ao invés do contains/containsKey.

Entretanto, se o seu array possuirá poucas posições (15, como você disse), não há motivos para alterar para List; mantenha como array.

#3

Tente utilizar pesquisa binária, pois reduz em muito o tempo da busca. Por exemplo, um array com um bilhão de elementos iria precisar de apenas 30 comparações para encontrar o elemento necessário.

Abraços,

Alexandre Oliveira

#4

Se em vez de 15 fossem 30 ou mais dados, aconselharia que a rotina lhe retornasse um Set<String>.
Pode ser um HashSet (se você só quer procurar o dado) ou um TreeSet (se você quer que os dados venham ordenados “como brinde”). A busca é quase instantânea.

#5

Como disse o aleck, tente usar Busca Binária

Collections.binarySearch(…) ou
Arrays.binarySeach()

Mas a lista deve estar ordenada ascendentemente…

#6

Na verdade não precisaria uma ordem específica, pois na busca binária, seria comparado o elemento do meio, caso este fosse maior que o elemento buscado, seria feita uma busca do meio para o início, do contrário, do meio para o final do array.

Abraços,

Alexandre Oliveira

#7

Tenho uma pergunta,

o método que retorna os 15 elementos, ele busca estes elementos em um banco de dados? Você não poderia passar o elementos desejado direto para que o método que gera o vetor retornar apenas os elementos que atendam a String?

Se a string for ser usada como chave para o objeto, pode ser mais interessando criar um HashMap<String,Objeto> em que a String a ser pesquisada é a chave para o mapa. Esta solução certamente é mais rápida que a pesquisa binária. Em tese O(1), contra o O(nlogn) da pesquisa binária.

fw

#8

[quote]Tenho uma pergunta,

o método que retorna os 15 elementos, ele busca estes elementos em um banco de dados? Você não poderia passar o elementos desejado direto para que o método que gera o vetor retornar apenas os elementos que atendam a String?

Se a string for ser usada como chave para o objeto, pode ser mais interessando criar um HashMap<String,Objeto> em que a String a ser pesquisada é a chave para o mapa. Esta solução certamente é mais rápida que a pesquisa binária. Em tese O(1), contra o O(nlogn) da pesquisa binária.

fw[/quote]
Então o método eu nao posso modificar pois ele já está sendo usado por outras estruturas e daria um trabalho imenso pra readaptar tudo.

Em um primeiro momento eu tentei a pesquisa binária mas nao tive muito sucesso, acho que por inexperiencie em utiliza-la, pois ela me retornava numeros negativos, e fiquei meio perdido em como faria a validação se existe ou nao o String que procuro no Array.

Então Yky por enquanto a aplicação está com um array mesmo, mas porque voce sugere o iterator e nao o contains ? ( se minha list fosse maior )

#9

a) Se o array não vier ordenado, não se pode usar busca binária.
b) Se o array for pequeno (15 posições) e você for procurar apenas uma vez, faça a busca linear mesmo (for).
c) Se a busca for feita várias vezes nesse mesmo array, vale a pena você transferir os dados para um HashSet ou TreeSet, e usar o “contains”. Exemplo:

String[] resultado = bla.ble(bli);  // seu método que retorna o array
Set&lt;String&gt; dados = new HashSet&lt;String&gt; (Arrays.asList (resultado));
System.out.println (dados.contains ("Joao")); // para ver se "Joao" está na lista. Retorna "true" ou "false".
#10

É thingol eu deixei a busca linear mesmo. Valeu pelas dicas. Realmente o array nao vem ordenado e vai ter apenas 15 posições nao tem necessidade de complicar ainda mais o código.

Galera obrigado pela atenção.

#11