static String min = "abcdefghijklmnopqrstuvwxyz";
static String max = min.toUpperCase();
static String num = "0123456789";
static String[] possiveis = min.concat(max).concat(num).split("|");
//Algum código aqui que não tem necessidade de ser exibido
for (int i = 0; i < possiveis.length; i++) {
for (int j = 0; j < possiveis.length; j++) {
for (int l = 0; l < possiveis.length; l++) {
for (int m = 0; m < possiveis.length; m++) {
for (int n = 0; n < possiveis.length; n++) {
for (int o = 0; o < possiveis.length; o++) {
for (int p = 0; p < possiveis.length; p++) {
for (int q = 0; q < possiveis.length; q++) {
teste = possiveis[i] + possiveis[j]
+ possiveis[l] + possiveis[m]
+ possiveis[n] + possiveis[o]
+ possiveis[p] + possiveis[q];
System.out.println("Teste: " + teste);
if(teste.equals(senha)){
System.out.println("\n\n\nTeste: " + teste);
break outerloop;
}
}
}
}
}
}
}
}
}
após algumas milhares de saida, percebe-se que o programa fica lento. Tenho 2 perguntas: Pq fica lento??? Tem como melhorar pra ser mais rápida a execução??
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 é??
[quote=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 é??[/quote]
Teoricamente sim.
Também pode ter o fator do OS que tá dando preferência para outras tarefas e não ao seu programa.
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.
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.
[quote=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).
[/quote]
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.
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…
[quote=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. [/quote]
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 =));
[quote=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.[/quote]
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;
}
}
}
}
}
}
}
}
}
}
}
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.