Performace em métodos

Você pode tentar usar threads. Mas vai depender do que você tá querendo fazer.

Então, eu gostaria que ele executasse mais rápido.
Usando theads, me corrija se eu estiver errado, mas ele vai ficar mais rápido mesmo se eu estiver usando um processador dual core pra mais, não é??

DoomGuy:

Então, eu gostaria que ele executasse mais rápido.
Usando theads, me corrija se eu estiver errado, mas ele vai ficar mais rápido mesmo se eu estiver usando um processador dual core pra mais, não é??

Teoricamente sim.
Também pode ter o fator do OS que tá dando preferência para outras tarefas e não ao seu programa.

Ou tenta usar uma lógica diferente.

Explica o que você quer fazer.
Pelo o que eu vi no seu código, é para gerar senhas e tentar quebrar alguma senha por força bruta.

Vc tem 7 loops aninhados. Dependendo do tamanho de “possíveis.length” isso vai ficar lento mesmo. Esse tipo de código com mtos loops aninhados deve ser evitado pois pode deixar o seu prorgrama lento. Use só se não tiver jeito…

Usar mais de uma thread deixa o programa mais eficiente em “determinados” casos(aqueles que você precisar processar vários ítens simultâneamente). Esse não me parece o caso. O problema é a complexidade do algoritmo que é logarítmica. A curva de tempo em relação ao número de inputs que você usou é muito grande por ter vários laços aninhados. A melhor curva é a linear.

Dá uma lida nesse artigo sobre análise de algoritmos, (Tem vários pdfs). Tenho certeza que você consegue melhorar o desempenho desse.
http://www.ime.usp.br/~pf/analise_de_algoritmos/

Esse algoritmo é muito ineficiente.

É por aí mesmo.

Eu fiquei curioso pra ver como funcionava esse tipo de algoritmo. Por isso, tentei fazer um.

Você quer quebrar uma senha, sendo que ela tem 8 caracteres, e cada um tem 62 valores possíveis.

Existem 62 ^8 = 218.340.105.584.896 combinações possíveis.
Suponha que um núcleo possa testar 10 milhões de combinações por segundo.
O tempo médio para achar uma senha é de 218.340.105.584.896 / 2 / 10.000.000 = 10.917.005 segundos. Isso dá “apenas” 126 dias.
(O tempo máximo é 218.340.105.584.896 / 10.000.000 = 21.834.010 segundos = 253 dias)
Digamos agora que você possa repartir essa tarefa por 62 núcleos (estou usando esse valor quebrado, só para ficar mais fácil para você dividir o serviço). Por exemplo, você pode achar 16 computadores quadcore e repartir esse serviço entre eles. O tempo médio para achar a senha será de um pouco mais de 2 dias.

Do jeito que você fez, usando concatenação de strings, realmente vai levar um tempo absurdo - esse seu programa em Java não consegue varrer 10 milhões de combinações por segundo nem a pau.
Você pode usar uma outra linguagem (como C ou C++) e, usando OpenMP ou alguma tecnologia semelhante, repartir o processamento entre threads (e MPI para repartir o processamento entre computadores).

Uma forma que ajuda um pouco a tornar mais rápido esse processamento é ver se a senha pode estar em um dicionário.
Mesmo que a senha tenha 8 caracteres, se ela for algo como “AgoraTem” (talvez seja a senha daquele prefeito que usa a musiquinha do “antes não tinha agora tem”), você mata a senha na hora.

entanglement:

Você quer quebrar uma senha, sendo que ela tem 8 caracteres, e cada um tem 62 valores possíveis.

Existem 62 ^8 = 218.340.105.584.896 combinações possíveis.
Suponha que um núcleo possa testar 10 milhões de combinações por segundo.
O tempo médio para achar uma senha é de 218.340.105.584.896 / 2 / 10.000.000 = 10.917.005 segundos. Isso dá “apenas” 126 dias.
(O tempo máximo é 218.340.105.584.896 / 10.000.000 = 21.834.010 segundos = 253 dias)
Digamos agora que você possa repartir essa tarefa por 62 núcleos (estou usando esse valor quebrado, só para ficar mais fácil para você dividir o serviço). Por exemplo, você pode achar 16 computadores quadcore e repartir esse serviço entre eles. O tempo médio para achar a senha será de um pouco mais de 2 dias.

Do jeito que você fez, usando concatenação de strings, realmente vai levar um tempo absurdo - esse seu programa em Java não consegue varrer 10 milhões de combinações por segundo nem a pau.
Você pode usar uma outra linguagem (como C ou C++) e, usando OpenMP ou alguma tecnologia semelhante, repartir o processamento entre threads (e MPI para repartir o processamento entre computadores).

A qt concurrent é muito boa api também. Dá para paralelizar com uma gpu se for o caso.
Eu acredito que separar o problema em um número de threads maior que o número de núcleos da plataforma alvo não vai garantir maior desempenho não. Pelo menos comigo o ganho sempre foi o número justo de núcleos.

http://qt-project.org/doc/qt-4.8/qtconcurrent.html

Acredito que esteja ficando lento pela quantidade de strings criadas… deve estar lotando o heap e demorando para limpar… algo assim… mas eu rodei o programa aqui e não achei lento… achei que a velocidade continua igual (depois de quanto tempo começa a lentidão)???

óbvio que como já foi falado por ai… esse algoritmo é ineficiente e precisaria ser melhorado, porém deixando isso de lado… tem algum motivo de lentidão!!! Vou deixar rodando aqui e ver o que acontece…

entanglement:

Uma forma que ajuda um pouco a tornar mais rápido esse processamento é ver se a senha pode estar em um dicionário.
Mesmo que a senha tenha 8 caracteres, se ela for algo como “AgoraTem” (talvez seja a senha daquele prefeito que usa a musiquinha do “antes não tinha agora tem”), você mata a senha na hora.

o aircracker usa essa idéia. Normalmente as senhas da maioria das pessoas são criadas baseadas em alguma palavra e sequencia de números, então o dicionário acaba sendo um grande avanço.

Aqui começou a lentidão depois de uns 40 minutos. Então, se meu objetivo fosse realmente quebrar uma senha, eu usaria direto alguma word list, ou os programas do backtrack mesmo. Mas eu gostaria de ver como um algoritmo desse tipo funciona de verdade. Da melhor maneria possível. Ai resolvi pedir ajuda pro pessoal que manja mais do que eu(vcs =));

A lentidão começou depois de uns 40 minutos.

DoomGuy:

Aqui começou a lentidão depois de uns 40 minutos. Então, se meu objetivo fosse realmente quebrar uma senha, eu usaria direto alguma word list, ou os programas do backtrack mesmo. Mas eu gostaria de ver como um algoritmo desse tipo funciona de verdade. Da melhor maneria possível. Ai resolvi pedir ajuda pro pessoal que manja mais do que eu(vcs =));

A lentidão começou depois de uns 40 minutos.

Então, pega aquele artigo sobre análise de algoritmos e tenta diminuir a complexidade deste seu. Depois que você melhorá-lo ainda pode repartir o processamento dele como o entanglement citou no post acima.

Este é o seu algoritmo de força bruta, mas sem usar String. Eu vi que ele faz cerca de 50 milhões de comparações por segundo, em uma máquina Core 2 Duo T5500 3.0 GHz. Estou usando apenas uma thread.

Para eu não ficar esperando a eternidade e mais um pouco, peguei uma senha que precisa apenas de 345.342.908 iterações. para ser encontrada.

package guj;

import java.util.Arrays;

public class ForcaBruta {

    /**
     * @param args
     */
    public static void main(String[] args) {
        String senha = "AAAXXBc3";
        char[] chrSenha = senha.toCharArray();
        String possiveis = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
        char[] chrPossiveis = possiveis.toCharArray();
        char[] teste = new char[8];
        long t = System.nanoTime();
        long iteracoes = 0;
    loop:
        for (int i0 = 0; i0 < 62; i0++) {
            teste[0] = chrPossiveis [i0];
            for (int i1 = 0; i1 < 62; i1++) {
                teste[1] = chrPossiveis [i1];
                for (int i2 = 0; i2 < 62; i2++) {
                    teste[2] = chrPossiveis [i2];
                    for (int i3 = 0; i3 < 62; i3++) {
                        teste[3] = chrPossiveis [i3];
                        for (int i4 = 0; i4 < 62; i4++) {
                            teste[4] = chrPossiveis [i4];
                            for (int i5 = 0; i5 < 62; i5++) {
                                teste[5] = chrPossiveis [i5];
                                for (int i6 = 0; i6 < 62; i6++) {
                                    teste[6] = chrPossiveis [i6];
                                    for (int i7 = 0; i7 < 62; i7++) {
                                        teste[7] = chrPossiveis [i7];
                                        iteracoes++;
                                        if (Arrays.equals (teste, chrSenha)) {
                                            System.out.println ("Achou: [" + new String (teste) 
                                            + "] após " + (System.nanoTime() - t)*1E-9 + " seg e " +
                                            iteracoes + " iteracoes");
                                            break loop;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

Esquecendo a idéia do algortimo… ( overhead )

O problema já foi mencionado… A heap está sendo dimensionada de uma maneira big(o) n^n.

Mesmo você tendo bons recursos de HW, você precisa dizer a sua JVM que ela pode usar mais memória.

-Xmn100M -Xms500M -Xmx500M

Uma solução simples é bufferizar essas concatenações, e claro, melhorar o algoritmo!

new StringBuffer().append("");

Concatenar 2 strings (mesmo sendo da forma que foi escrita originalmente, com uma sequencia de concatenações como

teste = possiveis[i] + possiveis[j]  
                                                + possiveis[l] + possiveis[m]  
                                                + possiveis[n] + possiveis[o]  
                                                + possiveis[p] + possiveis[q];

que o compilador compilou para :

teste = new StringBuilder (possiveis[i])
     .append (possiveis[j])
     .append (possiveis[l])
     .append (possiveis[m])
     .append (possiveis[n])
     .append (possiveis[o])
     .append (possiveis[p])
     .append (possiveis[q]).toString();

é sempre lento. Nesse caso em particular, nem adianta usar o StringBuilder + append porque o resultado é o mesmo que o compilador (nesse caso específico) fez.

Suponha que você queira insistir na idéia de comparar 2 strings, em vez de comparar 2 arrays de char como fiz. Uma forma de fazer isso seria com a seguinte modificação:

package guj;


public class ForcaBruta {

    /**
     * @param args
     */
    public static void main(String[] args) {
        String senha = "AAAXXBc3";
        String possiveis = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
        char[] chrPossiveis = possiveis.toCharArray();
        char[] teste = new char[8];
        long t = System.nanoTime();
        long iteracoes = 0;
    loop:
        for (int i0 = 0; i0 < 62; i0++) {
            teste[0] = chrPossiveis [i0];
            for (int i1 = 0; i1 < 62; i1++) {
                teste[1] = chrPossiveis [i1];
                for (int i2 = 0; i2 < 62; i2++) {
                    teste[2] = chrPossiveis [i2];
                    for (int i3 = 0; i3 < 62; i3++) {
                        teste[3] = chrPossiveis [i3];
                        for (int i4 = 0; i4 < 62; i4++) {
                            teste[4] = chrPossiveis [i4];
                            for (int i5 = 0; i5 < 62; i5++) {
                                teste[5] = chrPossiveis [i5];
                                for (int i6 = 0; i6 < 62; i6++) {
                                    teste[6] = chrPossiveis [i6];
                                    for (int i7 = 0; i7 < 62; i7++) {
                                        teste[7] = chrPossiveis [i7];
                                        iteracoes++;
                                        if (senha.equals(new String(teste))) {
                                            System.out.println ("Achou: [" + new String (teste) 
                                            + "] após " + (System.nanoTime() - t)*1E-9 + " s e " +
                                            iteracoes + " iteracoes");
                                            break loop;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

O código acima estava rodando cerca de 20 milhões de comparações por segundo.

entanglement,

Você está correto!

O ganho de perfomace está em você não alocar tantos objetos na heap e exigir que o GC trabalhe limpando essas &refs.

Certo?

Obrigado!

nickdofeliperibeiro:

entanglement,

Você está correto!

O ganho de perfomace está em você não alocar tantos objetos na heap e exigir que o GC trabalhe limpando essas &refs.

Certo?

Obrigado!

Neste caso em particular talvez.

Eu ainda fico pasmado de ver que é possível criar 20 milhões de objetos por segundo (que é o caso desse loop com strings em vez de comparar 2 arrays “estáticos” de char - eu chamo de “estáticos” porque estou reusando sempre os mesmos) e o Garbage Collector ainda conseguir limpá-los eficaz e corretamente.

É que nesse programa em particular até dá para evitar a criação de objetos. Mas em geral, em Java, não fique tentando reaproveitar objetos, que não vale a pena.

Pois é… A velocidade de processamento realmente é absurda!

Na verdade minha preocupação não foi em reuso, e sim o uso da memória.

Hoje em dia não é hábito se preocupar com isto por termos, por exemplo, bastante memória para usar.

Mas imagine, um dia você ter que programar em um CI (circuito integrado) que tenha pouca memória para esse tipo de alocação?!

O meu argumento realmente é muiito específico. Mas foi só um destaque para nos atentarmos a isso!

Obrigado pelo conhecimento camarada!

Se a forma do entanglement ainda não for o suficiente, talvez o próximo passo da otimização seja tornar programa mais específico.

Se você sabe que a senha foi gerada por pessoas, ao invés de simplesmente tentar todos os valores possíveis, você pode tentar implementar o algorítmo do dicionário. Assim, você primeiro testa palavras da lingua de origem da pessoa, depois combinações dessas palavras para só então partir para força bruta simples.

Fica melhor ainda se você conhecer o alvo, e colocar também datas de aniversário, casamento, nascimento dos filhos, dos pais, da esposa, nome do cachorro…

Só a título de curiosidade. Eu implementei em C++ o algorítmo de Bresenham. O algorítmo estava desenhando sobre uma superfície de software da SDL.
Rodando ele num QuadCore i7 de 3.07Ghz, sem usar multiplas threads, consegui desenhar 600.000 linhas coloridas por segundo.

As linhas tinham em torno de 500 pixels de comprimento (são aproximadamente 300 milhões de pixels pintados por segundo).

As máquinas hoje em dia são mesmo muito rápidas.

Sua preocupação é bastante válida. Se isso fosse linguagem C++ e ele estivesse dando new e delete.

No Java, mesmo com o new daqueles, o garbage collector reusa memória. Tem um artigo bem interessante sobre isso do Goetz:

O interessante é que um programa que faça muito new e delete é o que eu geralmente uso de exemplo naqueles tópicos de flame quando os fãs de C++ dizem que o Java é mais lento que o C++. :mrgreen:

Um programinha assim:

int i = 0; int soma = 0; for (int i = 0; i < 10000; i++) Classe c = new Classe(i); soma += c.getValor(); //Retorna i delete c; } std::cout << soma << std::endl;

Roda milhares de vezes mais lento em C++ do que em Java, justamente por essa capacidade mágica do GC de reaproveitar a memória de objetos de vida curta.
Já o C++, perde muito tempo criando e apagando o objeto do heap (claro, um programador C++ mais “cabelos no peito” poderia escrever seu próprio alocador e deixar o java comendo poeira).

PS: O cálculo da soma só está ali para evitar que o compilador elimine o código por considera-lo “morto”.

Sua preocupação é bastante válida. Se isso fosse linguagem C++ e ele estivesse dando new e delete.

No Java, mesmo com o new daqueles, o garbage collector reusa memória. Tem um artigo bem interessante sobre isso do Goetz:

O interessante é que um programa que faça muito new e delete é o que eu geralmente uso de exemplo naqueles tópicos de flame quando os fãs de C++ dizem que o Java é mais lento que o C++. :mrgreen:

Um programinha assim:

int i = 0; int soma = 0; for (int i = 0; i < 10000; i++) Classe c = new Classe(i); soma += c.getValor(); //Retorna i delete c; } std::cout << soma << std::endl;

Roda milhares de vezes mais lento em C++ do que em Java, justamente por essa capacidade mágica do GC de reaproveitar a memória de objetos de vida curta.
Já o C++, perde muito tempo criando e apagando o objeto do heap (claro, um programador C++ mais “cabelos no peito” poderia escrever seu próprio alocador e deixar o java comendo poeira).

PS: O cálculo da soma só está ali para evitar que o compilador elimine o código por considera-lo “morto”.

Mas a pessoa que sabe escrever em c++ iria usar a stack na maioria dos casos do que partir para alocação dinâmica e guardar essas classes na heap.

int i = 0; int soma = 0; for (int i = 0; i < 10000; i++) Classe c (i); soma += c.getValor(); //Retorna i delete c; } std::cout << soma << std::endl;

Como você disse alocar dinamicamente em c++ não é tão eficiente quanto em java. Então o trabalho de otimizar o código acaba sendo nosso mesmo. Acho que desse jeito fica tão rápido quanto o java.