Otimização de código em recursividade para gerar palavras.

HelloWorld Membro desde: 21/10/2008 08:26:53 Mensagens: 12 Offline

Olá pessoal, eu tenho um código que eu fiz que gera palavras, e até frases porém como ele trabalha por análise combinatória existe o problema de ser extremamente sequencial, e conforme o tamanho da palvra vai aumentando, ou a quantidade de letras presente no alfabeto que ele irá trabalhar também aumenta eu tenho um problema de desempenho... Se alguém tiver alguma idéia de como eu posso fazer para melhorar esse código deixar ele mais rápido, ou paralelizar ele com threads para pelo menos melhorar o desempenho em processadores mais modernos, seria de grande ajuda.

o meu código é:

String[] alfabeto = ("a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","x","z","w","y"," "); 
/** 
 * Função montaPalavra, recebendo como parametro a palavra inicial, o nivel 
 * atual de recursividade e o tamanho maximo da palavra, como o algoritmo é recursivo é 
 * necessário esse parâmetro para controlar os níveis de recursividade do mesmo. 
 * 
 * saida esperada para uma palavra de 3 letras e alfabeto ABC: 
 *  A | AA | AAA | AAB | AAC | AB | ABA | ABB | ABC | AC | ACA | ACB | ACC | 
 *  B | BA | BAA | BAB | BAC | BB | BBA | BBB | BBC | BC | BCA | BCB | BCC | 
 *  C | CA | CAA | CAB | CAC | CB | CBA | CBB | CBC | CC | CCA | CCB | CCC | 
 *  
 * Esse algoritmo não previne palavras iguais, caso durante o funcionamento ele gere mais de uma 
 * vez palavras como "BANANA" essa palavra será listada mais de uma vez.      
 *    
 * @param Palavra - a palavra que deverá ser passada para formar as proxiams combinações. O valor 
 * inicial dessa variavel deverá ser sempre obrigatoriamente "".  
 * @param nivelRec - Controle de nivel de recursividade, para que só sejam criadas palavras até 
 * quando o tamanho for o tamanho definido, para esse valor quando for incrementado não se pode 
 * usar nivelRec++ pois não estou trabalhando com incremento,a penas com parâmetro. O valor inicial 
 * dessa variavel deverá ser sempre obrigatoriamente 0.    
 * @param qtdLetras - tamanho em letras máximo das palavras gerada. 
 */    
private void montaPalavra(String palavra, int nivelRec, int qtdLetras) 
{ 
  for(String letra: alfabeto) 
  { 
    nivelRec == 0 ? palavra = letra : palavra += letra; 
    System.Out.println(palavra); 
    nivelRec <= qtdLetras ? montaPalavra(palavra, nivelRec + 1, qtdLetras) : return; 
  } 
}

Ele precisa ser recursivo?

Pelo tipo do problema, acho potencialmente perigoso mante-lo assim, já que o número de combinações deve aumentar muito.

Você pode eliminar as palavras duplicadas se copia-las para um TreeSet antes de retornar o resultado final.

HelloWorld Membro desde: 21/10/2008 08:26:53 Mensagens: 12 Offline

A principio não precisa ser recursivo, eu fiz dessa forma pois não encontrei outra forma que não limitasse o tamanho máximo das palavras geradas. O número de combinações depende somente do tamanho da plavra que for gerada, para palavras de 4 letras ele gera todas as palavras com 1 até 4. Mas acredito que o nivel de recursividade não se aprofunda tanto a ponto de causar um estouro de pilha pois ao gerar palavras ou frases de até 100 caracteres existirão apenas 100 niveis de recursividade, e isso acredito que é pouco pois em liguagens bem menos robustas do que o java, como o action script por exemplo, o nivel de recrsividade ronda em torno do valor 255.

Como que funciona esse TreeSet? Ele é algo que faz o gerenciamento de palavras repetidas sozinho ou seria um gerenciamento de forma parecida com vatores onde eu teria que criar um for percorrendo e verificando se existe ou não a palavra?

GUJ Hacker Membro desde: 26/09/2009 09:18:56 Mensagens: 5750 Offline

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2639.pdf

Procure (já que o paper acima é em C++, não Java) também por "lexicographically sorted permutations".

HelloWorld Membro desde: 21/10/2008 08:26:53 Mensagens: 12 Offline

entanglement wrote:http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2639.pdf

Procure (já que o paper acima é em C++, não Java) também por "lexicographically sorted permutations".

vou dar uma olhada no pdf, valeu pela indicação. E C++, Java no fundo se você entende a lógica não tem problema nenhum pois para portar para qualquer outra linguagem é simples questão de sintaxe.

Faz sozinho. Internamente o TreeSet usa uma árvore binária. Ele descarta automaticamente palavras duplicadas e as ordena, de acordo com o comparador fornecido (como o String já é comparable, será ordenada pela ordem alfabética).

Outra possibilidade, se vc não precisar usar ordenação, é o HashSet. É um pouco mais rápido, mas não garante nenhum tipo de ordem.

Esse código está mesmo lento? Talvez o ideal seja usar um profiler para identificar onde. Também experimente trocar o String pelo StringBuilder. A recursividade, por si só, não deveria deixar tão lento.

HelloWorld Membro desde: 21/10/2008 08:26:53 Mensagens: 12 Offline

ViniGodoy wrote:Faz sozinho. Internamente o TreeSet usa uma árvore binária. Ele descarta automaticamente palavras duplicadas e as ordena, de acordo com o comparador fornecido (como o String já é comparable, será ordenada pela ordem alfabética).

Outra possibilidade, se vc não precisar usar ordenação, é o HashSet. É um pouco mais rápido, mas não garante nenhum tipo de ordem.

Esse código está mesmo lento? Talvez o ideal seja usar um profiler para identificar onde. Também experimente trocar o String pelo StringBuilder. A recursividade, por si só, não deveria deixar tão lento.

Obrigado pela dica do TreeSet, vou dar uma pesquisada sobre o mesmo para aplicar no meu código.

E eu tenho consiencia que meu código está lento por causa do tamanho das palavras que estou tentando gerar, e por causa também do alfabeto que estou utilizando, uma vez que para colar aqui colei um alfabeto reduzido para exemplificar apenas, no meu caso estou usando todos os caracteres minusculos, todos os maiusculos, numeros e caracteres especiais, incluindo nisso caracteres acentuados, então é um alfabeto bastante extenso, também estou colocando para gerar expressões de até 200 caracteres.

Então eu sei que pela forma que eu fiz ele inevitavemente ficará pesado pela quantidade de combinações, então pensei se alguém teria uma forma mais otimizada de fazer recursividade, ou se teria alguma idéia de quebrar isso em threads para que possa ser feito utilizando um quadricore com HT por exemplo.

GUJ Hacker Membro desde: 26/09/2009 09:18:56 Mensagens: 5750 Offline

Você obviamente deve saber que o número de permutações com repetição aumenta exponencialmente, e o expoente é o comprimento da sequência, ou seja, para você listar as permutações com repetição de 52 símbolos (só as letras minúsculas e maiúsculas), de comprimento 4 (que é bem pequeno), você tem 52 ^ 4 = 7.311.616 possibilidades. Se você quer as permutações de 52 símbolos que tenham comprimento entre 1 e 4, você terá
52 + 52^2 + 52^3 + 52^4 = 7.454.980 possibilidades.

Ou seja, se você não limitar muito os parâmetros passados, você vai esgotar logo a memória da sua máquina, ou seu disco - não importa se você vai usar 100 CPUs para calcular as permutações.

Por que é que você precisa listar as permutações?

GUJ Hacker Membro desde: 26/09/2009 09:18:56 Mensagens: 5750 Offline

Uma dica bem boba: você sabe fazer conversão de bases? A idéia, para você gerar as permutações de comprimento 4 de um alfabeto de 52 símbolos, é contar de 0 até 52 ^ 4 - 1, e converter a contagem para "base 52". Vou dar um exemplo.

Digamos que você queira obter a permutação de número 4889287. Então você faria:

4889287 % 52 = 39
4889287 / 52 = 94024
94024 % 52 = 8
94024 / 52 = 1808
1808 % 52 = 40
1808 / 52 = 34
34 % 52 = 34

Ou seja, a sua permutação seria composta pelos símbolos de ordem: 34, 40, 8 e 9. (O primeiro símbolo teria ordem 0). Se o alfabeto fosse "abcdef...zABCDEF...Z" então teríamos a permutação "INij". (dê uma conferida, fiz de cabeça).

aahahahahaha. Entaglement, essa foi exatamente a solução que eu pensei, quando li o tópico a primeira vez.

GUJ Expert Membro desde: 18/02/2008 16:17:53 Mensagens: 3002 Offline

entanglement wrote:Uma dica bem boba: você sabe fazer conversão de bases? A idéia, para você gerar as permutações de comprimento 4 de um alfabeto de 52 símbolos, é contar de 0 até 52 ^ 4 - 1, e converter a contagem para "base 52". Vou dar um exemplo.

Digamos que você queira obter a permutação de número 4889287. Então você faria:

4889287 % 52 = 39
4889287 / 52 = 94024
94024 % 52 = 8
94024 / 52 = 1808
1808 % 52 = 40
1808 / 52 = 34
34 % 52 = 34

Ou seja, a sua permutação seria composta pelos símbolos de ordem: 34, 40, 8 e 9. (O primeiro símbolo teria ordem 0). Se o alfabeto fosse "abcdef...zABCDEF...Z" então teríamos a permutação "INij". (dê uma conferida, fiz de cabeça).

Achei um show essa solução, muito bem pensada.

GUJ Hacker Membro desde: 26/09/2009 09:18:56 Mensagens: 5750 Offline

Essa é uma variação de "gere as placas de carros em ordem". Nesse caso, a base é 10 para os dígitos e 26 para as letras. Você teria então

26 ^ 3 * 10 ^ 4 = 175.760.000

combinações. Digamos que você queira emplacar seu carro com a 100.000.000 combinação. Então:

100.000.000 % 10 = 0
10.000.000 % 10 = 0
1.000.000 % 10 = 0
100.000 % 10 = 0
10.000 % 26 = 16
384 % 26 = 20
14 % 26 = 14

Ou seja, a placa é NUP 0000.

HelloWorld Membro desde: 21/10/2008 08:26:53 Mensagens: 12 Offline

Realmente essa solução da conversão de base é uma solução bastante interessante, porém quand eu resolvo usar um alfabeto de 80 letras +/- e palavras de até 200 caracteres (1 a 200) eu não iria estourar o tamanho de variavel? uma vez que 80^200 irá me gerar um resultado monstruoso, algo em torno de: 414951556888099295851284078636912 seguidos de 349 zeros, não é possivel precisar o valor exato pois essa foia limitação que eu tive com a calculadora do windows. Pelo modo de que essa lista iria ser descomunalmente grande eu pensei em apenas listar elas.

Mesmo usando um alfabeto de 52 letras ao chamar uma lista com palavras de tamanho 100 já estoura ao tamanho máximo de um número, não?

Essa brincadeira foi um desafio que eu criei pra mim mesmo que era criar um algoritmo de permutação que permita todas as opções existentes para uma determinada quantidade de letras, da forma que ficasse o mais simples possivel e que ficasse com um desempenho bom. Para testes pequenos de permutação simples ele funcionou que é uma beleza, porém quando comecei a aumentar a brincadeira começou a me dar problemas, então resolvi vir perguntar se alguém tem alguma idéia pra melhorar a brincadeira.

[off: ViniGodoy você é o cara daquela engine de inteligencia artificial SOFIA?]

GUJ Hacker Membro desde: 26/09/2009 09:18:56 Mensagens: 5750 Offline

Ainda não entendi por que que você quer listar as opções (permutações).

Você não consegue listar mais de 10^15 permutações em tempo razoável para a sua espera, mesmo sem guardá-las, gravá-las em disco, etc. Imagine 80 ^ 200.

O que você pode fazer é achar uma permutação ao acaso e testá-la contra o que você quer, em vez de listá-las todas (o que você deve ter percebido que é inviável para grandes alfabetos e/ou tamanhos).

GUJ Hacker Membro desde: 26/09/2009 09:18:56 Mensagens: 5750 Offline

Uma variação desse modo de fazer (conversão de bases) é semelhante ao odômetro (marcador de quilometragem) dos veículos antigos. Para facilitar, vou supor que o tamanho é fixo em N (tal como o odômetro).

Como é que o marcador funciona? Ele funciona assim: a rodinha de cada dígito gira de 0 até 9. Quando o dígito passar de 9 para zero, ele arrasta consigo a rodinha imediatamente à esquerda, para incrementar o dígito à sua esquerda.

00001
00002
...
00009
00010

Você pode começar com uma string inicializada com N caracteres correspondentes ao caracter inicial de seu alfabeto, e ir fazendo exatamente como é feito com o odômetro. Exemplo para o alfabeto "ABCDEF... .Z" e comprimento de 4 caracteres:

AAAA
AAAB
...
AAAZ
AABA

e assim por diante.

Notícias, artigos e o maior fórum brasileiro sobre Java