Otimização de código

acho que uma primeira otimização seria tirar esses replaceAll em sequencia e usar apenas um, passando um regex tipo "[,;.]"pra substituir por “”.

Troque seu ArrayList por um TreeSet ou HashSet().
Seu código ficaria mais ou menos assim:

Set<String> lista = new TreeSet<String>(); // ou new HashSet<String>()
for (int m=0; m < list.size(); m++ ){  
    String[] tokens = list.get (m).split ("\\s+");
    for (String token: tokens) {
        lista.add (token.replaceAll ("[;,.]+", ""));
    }
}

1. Evita o uso de StringTokenizer (cujo uso deve ser evitado em código que rode em Java 1.4 ou posterior)
2. Evita a inserção em uma lista simples tendo de procurar o elemento antes (que, como você desconfiou, tem complexidade O(N)).

a diferença foi bem pouca, teste em milisegundos:

antes
153875

depois
141126

e se vc trocar isso:

for (int m=0; m < list.size(); m++ ){  
  
            StringTokenizer parser = new StringTokenizer(list.get(m));  
            while (parser.hasMoreTokens()) {  
                String aux = parser.nextToken();  
                aux = aux.replaceAll(",", "")  
                         .replaceAll(";", "")  
                         .replaceAll("\\.", "");  
                if (!lista.contains(aux )){  
                lista.add(aux);  
                }  
            }  
        }

por isso:

for (int m=0; m < list.size(); m++ ){  
            lista.addAll(Arrays.asList(list.get(m).replaceAll("[,;.]", "").split("\\s+"))); // com o regex \\s+ fica melhor pois pode ter mais de um espaço entre palavras
        }

entanglement:

Troque seu ArrayList por um TreeSet ou HashSet().
Seu código ficaria mais ou menos assim:

Set<String> lista = new TreeSet<String>(); // ou new HashSet<String>()
for (int m=0; m < list.size(); m++ ){  
    String[] tokens = list.get (m).split ("\\s+");
    for (String token: tokens) {
        lista.add (token.replaceAll ("[;,.]+", ""));
    }
}

1. Evita o uso de StringTokenizer (cujo uso deve ser evitado em código que rode em Java 1.4 ou posterior)
2. Evita a inserção em uma lista simples tendo de procurar o elemento antes (que, como você desconfiou, tem complexidade O(N)).

Nossa show de bola entanglement

antes
153875

depois
3666

DaniloAndrade:

e se vc trocar isso:

for (int m=0; m < list.size(); m++ ){  
  
            StringTokenizer parser = new StringTokenizer(list.get(m));  
            while (parser.hasMoreTokens()) {  
                String aux = parser.nextToken();  
                aux = aux.replaceAll(",", "")  
                         .replaceAll(";", "")  
                         .replaceAll("\\.", "");  
                if (!lista.contains(aux )){  
                lista.add(aux);  
                }  
            }  
        }

por isso:

for (int m=0; m < list.size(); m++ ){  
            lista.addAll(Arrays.asList(list.get(m).replaceAll("[,;.]", "").split("\\s+"))); // com o regex \\s+ fica melhor pois pode ter mais de um espaço entre palavras
        }

ficou muito mais rápido danilo:

antes
153875
depois
1597

mas o problema é que ele adiciona repetidos

Parece que acabamos de fazer um mini DOJO

srsrsr

Algebra:

DaniloAndrade:

e se vc trocar isso:

for (int m=0; m < list.size(); m++ ){  
  
            StringTokenizer parser = new StringTokenizer(list.get(m));  
            while (parser.hasMoreTokens()) {  
                String aux = parser.nextToken();  
                aux = aux.replaceAll(",", "")  
                         .replaceAll(";", "")  
                         .replaceAll("\\.", "");  
                if (!lista.contains(aux )){  
                lista.add(aux);  
                }  
            }  
        }

por isso:

for (int m=0; m < list.size(); m++ ){  
            lista.addAll(Arrays.asList(list.get(m).replaceAll("[,;.]", "").split("\\s+"))); // com o regex \\s+ fica melhor pois pode ter mais de um espaço entre palavras
        }

ficou muito mais rápido danilo:

antes
153875
depois
1597

mas o problema é que ele adiciona repetidos

facil de resolver troca o List lista = new ArrayList();
pelo Set lista = new HashSet()

Use o HashSet (como o entanglement disse).

caramba, to gostando da brincadeira, rsrsr

Cara show de bola.

de 153875 para 1597 milissegundos.

bota otimização nisso!

Valew galera alto nível.

Abraços

agora tem que pagar o cafezinho, rsrs

depois de uma otimização destas merece até um churrasco \o/

é, mas isso foi resultado da junção das ideias de todos que postaram

Outro ponto:

em vez de

for (int m=0; m < list.size(); m++ ){

use

for (String string : list) {

assim evita o list.size() e o list.get(), que podem reduzir o desempenho (dependendo da implementação da lista).

Ataxexe:

Outro ponto:

em vez de

for (int m=0; m < list.size(); m++ ){

use

for (String string : list) {

assim evita o list.size() e o list.get(), que podem reduzir o desempenho (dependendo da implementação da lista).

Ponto positivo pra vc Ataxexe. consegui melhorar ainda mais a média.
de 1597 para 1180 ms.
A principio a diferença parece pequena, mas para um grande volume de informações isso faz muita diferença!

Algebra:

Ataxexe:

Outro ponto:

em vez de

for (int m=0; m < list.size(); m++ ){

use

for (String string : list) {

assim evita o list.size() e o list.get(), que podem reduzir o desempenho (dependendo da implementação da lista).

Ponto positivo pra vc Ataxexe. consegui melhorar ainda mais a média.
de 1597 para 1180 ms.
A principio a diferença parece pequena, mas para um grande volume de informações isso faz muita diferença!

Vc consegue ir mais longe tirando esse for. De onde vêm essa lista ? Porque vc não recebe o texto em um único String e recebe “frases” ?

sergiotaborda:

Algebra:

Ataxexe:

Outro ponto:

em vez de

for (int m=0; m < list.size(); m++ ){

use

for (String string : list) {

assim evita o list.size() e o list.get(), que podem reduzir o desempenho (dependendo da implementação da lista).

Ponto positivo pra vc Ataxexe. consegui melhorar ainda mais a média.
de 1597 para 1180 ms.
A principio a diferença parece pequena, mas para um grande volume de informações isso faz muita diferença!

Vc consegue ir mais longe tirando esse for. De onde vêm essa lista ? Porque vc não recebe o texto em um único String e recebe “frases” ?

Essa lista vem do meu controller no grails

def lista = Documento.getAll().texto

Eu pego um campo chamado texto da minha classe documento.

Não consigo ver otimização neste ponto, dá pra fazer??

Muito interessante esse tópico.
Ajuda a pensar em soluções mais eficazes para um determinado problemas.
Seria uma idéia ter mais tópicos como esses.

lele_vader:

Muito interessante esse tópico.
Ajuda a pensar em soluções mais eficazes para um determinado problemas.
Seria uma idéia ter mais tópicos como esses.

concordo em gênero numero e grau.

por mim pode ter vários e sempre que possível irei participar

Essa sua solução foi muito boa realmente. Algoritmos com laços aninhados são ineficientes por causa da complexidade n log^n. Da maneira que fez deixou ele linear que é como toda solução deve ficar. Muito bem.

parabéns pelo nosso trabalho em equipe.

que venham outros desafios como esse, eu particularmente gostei muito da brincadeira

rsrsr

Pensei aqui em uma coisa que teoricamente daria mais uma melhorada, que é deixar os regex pré-compilados ao invés de criá-los a cada chamada de split() e replaceAll().

// Antes do loop maior, pode até cachear em um static final na classe porque não muda nunca.
Pattern splitPattern = Pattern.compile("\\s+");
Pattern removeSpecialCharsPattern = Pattern.compile("[,;.]");

// Substituir
frase.replaceAll("[,;.]", "").split("\\s+"))
// por
splitPattern.split(removeSpecialCharsPattern.matcher(frase).replaceAll("")))

Mas em um teste que fiz aqui não diminuiu muito

Qualquer milissegundo com milhões de registros significaria uma melhoria significativa imagino eu.