Qual Collection voce usaria?

Assuntos Gerais
#1

Boa dia a todos !
Estou precisando de uma coleção que não contenha chaves duplicatas e que seja ordenada pelos valores.
Com um exemplo fica mais facil de entender.
Eu possuo uma grande lista de palavras, que contem palavras repetidas.
Ao percorrer esta lista, eu quero colocar as palavras em uma collection onde a chave sera a palavra e o valor sera o numero de vezes que esta palavra apareceu.
Ao final eu espero iterar esta colecao e obter as palavras com a maior frequencia em primeiro.

Colecao minhaColecao = new Colecao(); ArrayList<String> listaDePalavras = carregarPalavras(); for(int i=0 ; i<listaDePalavras.size() ; i++){ String palavraAtual = listaDePalavras.get(i); //se a palvra esta presente na colecao incrementar sua frequencia if(minhaColecao.contains(palavraAtual)){ //incrementar frequencia int frequencia = minhaColecao.getValue(palavraAtual) + 1; minhaColecao.replace(palavraAtual,frequencia); }//senao inserir a palarva na colecao com frequencia 1 else{ minhaColecao.add(palavraAtual,1); } } //ordenar a colecao se ela ja nao for ordenada automaticamente minhaColecao.sort();

P.S. Desempenho é crucial, portanto preciso de uma implementacao eficiente e com bom tempo de execucao.
O que sera melhor: usar um ArrayList de objetos PalavraComFrequencia e usar um sort() no final, ou usar um set ou map ?
Eai o que voces acham ?

#2

Se a ordem das chaves é importante, use um LinkedHashMap.
Como você vai usar Strings como chaves, o seu mapa vai estar sempre ordenado.

[]´s

#3

Certo, neste caso eu necessitaria que a LinkedHashMap estivesse ordenado por Valor(int) e nao por Chave(String).
Exemplo:

Palavra 1 - 12
Palavra 3 - 10
Palavra 2 - 8
Palavra 4 - 5
Palavra 5 - 1

#4

Hummm então, o valor vai mudar a cada iteração, então você pode perder o que já tinha em um determinado local e terminar com uma coleção cheia de valores irrelevantes caso alguma palavra tenha chegado no valor 10 por exemplo, mas passou pelo 9 e ninguém mais a sobrescreveu.
E você vai cair em outro problema. Palavras com valor de chave duplicado.

Lendo melhor sua dúvida (desculpa, tinha lido por cima), acho que a sua alternativa de usar uma lista de objetos PalavrasComFrequencia e depois ordená-la com base na frequencia é muito mais adequada.

[]´s

#5

Ah, é claro, você pode usar um mapa (HashMap) para ajudar no processo de contagem. :wink:

[]´s

#6

david eu acabei fazendo isso mesmo.
Criei uma classe KeyWordFrequency que implementa Comparable para que eu possa usar o Metodo Collections.sort(instanciaDeKeyWordFrequency)
e sorbeescrevi o metodo equals para que eu pudesse comprar dois objetos pelo atributo keyWord. Funcionou certinho, só não sei se é a alternativa mais rápida, pois, para fazer a ordenação eu creio que eles usam um algoritmo O(n²).

[code]public class KeyWordFrequency implements Comparable {

private String keyWord;
private int frequency;

public boolean equals(Object o) {
    KeyWordFrequency oIn = (KeyWordFrequency) o;
    if (keyWord.equals(oIn.getKeyWord())) {
        return true;
    } else {
        return false;
    }
}

public KeyWordFrequency(String key) {
    this.keyWord = key;
    frequency = 1;
}

public int getFrequency() {
    return frequency;
}

public String getKeyWord() {
    return keyWord;
}

public int compareTo(Object o) {
    KeyWordFrequency kwfIn = (KeyWordFrequency) o;
    if (this.frequency > kwfIn.getFrequency()) {
        return -1;
    } else if (this.frequency == kwfIn.getFrequency()) {
        return 0;
    } else {
        return 1;
    }
}

void setFrequency(int increasedFrequency) {
    this.frequency = increasedFrequency;
}

}[/code]

#7

Oi kirill
Pq vc está preocupado com performance?
Tenho quase certeza que no algoritmo de ordenação implementado no sort é o quick sort.

[]´s

#8

Estou preocupado pois irei trabalhar com uma grande quantidade de texto que devera ser processado.
Esta parte do codigo sera a mais rodada, como dizem 80% de execucao encontra-se em 20% do codigo e os outros 20% de execucao estao nos 80% de codigo, entao estou querendo otimizar =)
Eu estou implementando um projeto de iniciacao cientifica no qual meu objetivo é desenvolver um aplicativo WEB que se comunica com um outro aplicativo que possui um banco de dados extremamente extenso, e baseado numa query do usuario neste BD serao retornados diversos artigos. Cada artigo possui um texto de resumo, neste texto eu devo identificar palavras-chave relevantes (busca local) e numa proxima etapa eu irei identificar palavras-chave que se repetem nos diversos resumos para assim poder chegar a palavras-chave que resumam no geral os assuntos abordados por estes resumos (busca global). É mais ou menos isso.

#9