Qual Collection tem melhor performance para buscar Strings em um Array?

Só um adendo:

Como achei que ir removendo os boletos que já “verifiquei” da lista seria uma boa ideia, fiz o código abaixo que causou uma java.util.ConcurrentModificationException - Isso não era para NÃO acontecer com o Iterator?

public ArrayList<Boleto> getChavesIguais(String chave, ArrayList<Boleto> array){
        //cria o ArrayList
        ArrayList<Boleto> listaChaves = new ArrayList<>();
        //cria um Iterator para percorrer o Array com performance aprimorada
        Iterator<Boleto> it = array.iterator();
        //para cada Boleto dentro do array:
        while(it.hasNext()){
            //verifica se o boleto possue a chave que estamos procurando
            if(it.next().getChave().equals(chave)){
                //acrescenta ao ArrayList de Boleto
                listaChaves.add(it.next());
            }
            it.remove();
        }
        //retorna o ArrayList com somente os boletos iguais à chave passada.
        return listaChaves;
    }

b2000:

GUJ, tô desesperado e acho que só vocês podem me ajudar! hehehe

Possuo uma tabela no banco de dados com 400.000 linhas.
Cada linha corresponde a um objeto do tipo “Boleto”, armazenados em um ArrayList.
Para cada boleto (as tais 400.000 linhas), preciso verificar se seu código é encontrado em outro boleto, e quais são esses boletos(incluindo ele mesmo), por isso, fiz a função abaixo que retorna os boletos em questão:

public ArrayList<Boleto> getChavesIguais(String chave, ArrayList<Boleto> array){
        //cria um ArrayList que será usado para retornar apenas os boletos com chave/código igual
        ArrayList<Boleto> listaChaves = new ArrayList<>();
        //para cada Boleto dentro do array:
        for(Boleto b : array){
            //verifica se o boleto possue a chave que estamos procurando
            if(b.getChave().equals(chave)){
                //acrescenta ao ArrayList de Boleto
                listaChaves.add(b);
            }
        }
        //retorna o ArrayList com somente os boletos iguais à chave passada.
        return listaChaves;
    }

O fato é: preciso verificar se uma String existe em um Array (não precisa ser do tipo ArrayList).

O que fazer? Meu problema está em utilizar ArrayList? O código acima está lento demais!

Por favor, me ajudem! Abraços

confesso que as vezes fico na duvida.
mas se quer ter certeza, o que eu faria era um teste antes.
vc precisa ficar esperto pois algumas destas classe que trabalham co colections podem ou não ter elemenentos nulos ou únicos. Outras permitem sincronização e outras não.

http://mrbool.com/overview-of-java-arraylist-hashtable-hashmap-hashetlinkedlist/30383

Luiz Augusto Prado:

confesso que as vezes fico na duvida.
mas se quer ter certeza, o que eu faria era um teste antes.

Obrigado pela resposta Luiz Augusto Prado, olhei os dois links passados e são muito úteis quanto ao conhecimento geral dessas Collections, porém, nesse caso específico acho que só alguma collection que permita remover elementos pode me ajudar…

Já fiz vários testes, usando LinkedHashMap e ArrayList a performance é quase igual.
Acho que para o meu caso, a performance passa por poder remover os elementos já verificados (por isso planejo utilizar Iterator, porém ao fazer o código está dando erro - veja meu segundo post no tópico)… Estou fazendo algo errado?

b2000:

Luiz Augusto Prado:

confesso que as vezes fico na duvida.
mas se quer ter certeza, o que eu faria era um teste antes.

Obrigado pela resposta Luiz Augusto Prado, olhei os dois links passados e são muito úteis quanto ao conhecimento geral dessas Collections, porém, nesse caso específico acho que só alguma collection que permita remover elementos pode me ajudar…

Já fiz vários testes, usando LinkedHashMap e ArrayList a performance é quase igual.
Acho que para o meu caso, a performance passa por poder remover os elementos já verificados (por isso planejo utilizar Iterator, porém ao fazer o código está dando erro - veja meu segundo post no tópico)… Estou fazendo algo errado?

se eu fosse vc escolheria então uma classe que permita encontrar pra vc. Se vc utilizar interator, vai demorar. algumas destas classes ja possui isso implementado de forma otmizada (comparador). depois que vc encontrar… é só remover.
De cabeça eu não vou lembrar qual é a melhor solução.

http://www.javapractices.com/topic/TopicAction.do?Id=65

Por que você não faz um SELECT logo de uma vez ?

Luiz Augusto Prado:

se eu fosse vc escolheria então uma classe que permita encontrar pra vc. Se vc utilizar interator, vai demorar. algumas destas classes ja possui isso implementado de forma otmizada (comparador). depois que vc encontrar… é só remover.
De cabeça eu não vou lembrar qual é a melhor solução. http://www.javapractices.com/topic/TopicAction.do?Id=65

Poisé… usando iterator demorou uns 30 segundos a mais do que ArrayList:

[1]:::: Tempo total para executar o FOR com ArrayList: 13,87 minutos
[2]:::: Tempo total para executar o FOR com Iterator: 14,49 minutos

Já tinha visto essas listas e tinha optado pelo LinkedHashMap. É a melhor performance entre as listas ordenadas que encontrei, como a performance ficou quase inalterada em comparação ao ArrayList (1 segundo em um tempo total que varia entre 13 e 14 minutos), optei pelo ArrayList.

Então… a situação acima é na verdade uma “transformação para forma simples do meu problema”.
O select já está otimizado ao máximo, preciso mesmo dessas 400.000 linhas ou perco informação…
Por isso a dúvida é focada em: qual a melhor forma (em termos de performance) de validar se uma String encontra-se em um Array…

Pergunto, se Iterator permite remover elementos durante a iteração, por quê o código abaixo lança a exceção java.util.ConcurrentModificationException ?

public ArrayList<Boleto> getChavesIguais(String chave, ArrayList<Boleto> array){
        //cria o ArrayList
        ArrayList<Boleto> listaChaves = new ArrayList<>();
        //cria um Iterator para percorrer o Array com performance aprimorada
        Iterator<Boleto> it = array.iterator();
        //para cada Boleto dentro do array:
        while(it.hasNext()){
            //verifica se o boleto possue a chave que estamos procurando
            if(it.next().getChave().equals(chave)){
                //acrescenta ao ArrayList de Boleto
                listaChaves.add(it.next());
            }
            it.remove();
        }
        //retorna o ArrayList com somente os boletos iguais à chave passada.
        return listaChaves;
    }

Vi que o Vini (moderador) tinha falado em um post que o Iterator era bonzão por isso, mas não consegui repetir o feito… o que fiz de errado?

b2000:

Luiz Augusto Prado:

se eu fosse vc escolheria então uma classe que permita encontrar pra vc. Se vc utilizar interator, vai demorar. algumas destas classes ja possui isso implementado de forma otmizada (comparador). depois que vc encontrar… é só remover.
De cabeça eu não vou lembrar qual é a melhor solução. http://www.javapractices.com/topic/TopicAction.do?Id=65

Poisé… usando iterator demorou uns 30 segundos a mais do que ArrayList:

[1]:::: Tempo total para executar o FOR com ArrayList: 13,87 minutos
[2]:::: Tempo total para executar o FOR com Iterator: 14,49 minutos

Já tinha visto essas listas e tinha optado pelo LinkedHashMap. É a melhor performance entre as listas ordenadas que encontrei, como a performance ficou quase inalterada em comparação ao ArrayList (1 segundo em um tempo total que varia entre 13 e 14 minutos), optei pelo ArrayList.

Então… a situação acima é na verdade uma “transformação para forma simples do meu problema”.
O select já está otimizado ao máximo, preciso mesmo dessas 400.000 linhas ou perco informação…
Por isso a dúvida é focada em: qual a melhor forma (em termos de performance) de validar se uma String encontra-se em um Array…

Basicamente, existem 3 tipos de busca:

• busca linear (n)
• busca binária (log n)
• acesso aleatório (1)

ou seja, a melhor estrutura de dados é aquela que oferecer suporte ao melhor algoritmo de busca. Qualquer lista que você escolher será inútil, pois ela executará
busca linear. Portanto, resta escolher uma estrutura que ofereça suporte ou à busca binária ou à busca aleatória. Se o problema for realmente saber se uma String está ou não em uma coleção, então o HashSet é mais do que suficiente, pois ele faz essa verificação por acesso aleatório.

rmendes08:

Basicamente, existem 3 tipos de busca:

• busca linear (n)
• busca binária (log n)
• acesso aleatório (1)

ou seja, a melhor estrutura de dados é aquela que oferecer suporte ao melhor algoritmo de busca. Qualquer lista que você escolher será inútil, pois ela executará
busca linear. Portanto, resta escolher uma estrutura que ofereça suporte ou à busca binária ou à busca aleatória. Se o problema for realmente saber se uma String está ou não em uma coleção, então o HashSet é mais do que suficiente, pois ele faz essa verificação por acesso aleatório.

rmendes08, obrigado pela resposta!

Bom, na verdade a busca em si não precisa ter uma ordem mesmo, mas preciso que após encontrar as chaves que procuro, consiga ter um novo array na ordem que estava antes. Exemplo:

nome / valor / posicao
Água / 1.50 / 0
Água / 1.50 / 1
Água / 0.50 / 2
Suco / 1.00 / 3
Suco / 0.50 / 4

não pode depois virar

Água
Suco
Água

Porém no momento de consultar tanto faz a ordem…

Eu preciso manter a ordem no Array que retorna para quem chama a função getChaves(“Água”,arrayQualquer) pois com esse retorno farei cálculos baseado no que é relacionado à Água, e eles precisam estar ordenados pelo valor da água. (lembrando, essa situação é hipotética)

Se eu entendi corretamente o problema, implementar essa busca utilizando busca binária deve resolver o seu problema, a performance ficaria muito melhor como o rmendes08 comentou