[MathUtils]Vamos Brincar um pouco

Eh meio dificil imaginar alguem pulando e dando gritinhos de felicidade ao ver uma classe chamada MathUtils…

so pra animar… :lol:

public static int soma(int x, int y) {
   return x + y;
  }

 public static int subtraiint x, int y) {
   return x - y;
 }

  public static void naoFazPorraNenhuma(String porraNenhuma) {
   
  }

Prefiro alterar o fatorial() para isso:

public long fatorial(long n) { if (n < 0) throw new IllegalArgumentException("deu chabu"); long[] fat = new long[n]; fat[0] = 1; for (long i = 1; i < fat.length; i++) fat[i] = i * fat[i - 1]; return fat[n]; }

Schuenemann:

Prefiro alterar o fatorial() para isso:

public long fatorial(long n) { if (n < 0) throw new IllegalArgumentException("deu chabu"); long[] fat = new long[n]; fat[0] = 1; for (long i = 1; i < fat.length; i++) fat[i] = i * fat[i - 1]; return fat[n]; }

1. Porque for em vez de recursividade ?
2. Porque array para memorizar tudo ?

A verificação do n é uma boa

sergiotaborda:

Schuenemann:

Prefiro alterar o fatorial() para isso:

public long fatorial(long n) { if (n < 0) throw new IllegalArgumentException("deu chabu"); long[] fat = new long[n]; fat[0] = 1; for (long i = 1; i < fat.length; i++) fat[i] = i * fat[i - 1]; return fat[n]; }

1. Porque for em vez de recursividade ?
2. Porque array para memorizar tudo ?

A verificação do n é uma boa

também não vejo vantagens em fazer deste modo. até o código fica mais poluído.

Já que é para rodar em uma JVM, vamos lá:

package example;

object Factorial {
  // Calcula o fatorial de 10
  def main(args : Array[String]) : Unit = {
    Console.println ((1 to 10).reduceRight[Int] {_ * _})
  }
}

Calculo do numero de combinações calculando apenas o menor factorial necessário

public int combinations (int n , int k ){

    if (n <= 0 || k < 0 || k > n ){
           throw new IllegalArgumentException();
    }

    if (k==0 || k == n){
        return 1;
    }

    final int max = Math.max(k, n-k);
    final int min = n - max;

    int produto=1;
    for (int i = n ; n > max; i--){
         produto *= i;
   }
 
   return produto / factorial(min);
}

Ironlynx:

public class MathUtils{

   public long fatorial(long n){
   	 if (n==0)
   	 	return 1;   	 
   	 else
   	 	return n*fatorial(n-1);  	
   }
}

melhor como:

public class MathUtils{

   public long fatorial(long n){
   	 retunr n<=1 ? 1 : n*fatorial(n-1);  	
   }
}

A forma recursiva é apenas ruim porque polui o stack. Tlv melhor seja assim

public class MathUtils{

   public long fatorial(long n){

         if (n<0){
                throw new IlegalArgumentException();
        }
   	 F f = new F(n);
         while(!f.isFinished()){
             f.factorize();
         } 
         return f.value;
   }

   private class F {
        long n;
        long value=1;
         
F(long n){
 this.n =n;
}
        boolean isFinished(){
               return n<=1;
        }
        void factorize(){
           value *= n; 
           n--; 
        }
  }
}

sergiotaborda:

Ironlynx:

public class MathUtils{

   public long fatorial(long n){
   	 if (n==0)
   	 	return 1;   	 
   	 else
   	 	return n*fatorial(n-1);  	
   }
}

melhor como:

public class MathUtils{

   public long fatorial(long n){
   	 retunr n<=1 ? 1 : n*fatorial(n-1);  	
   }
}

A forma recursiva é apenas ruim porque polui o stack. Tlv melhor seja assim

Hummm, prefiro a primeira opção, a segunda esta apenas mais difícil de ler.

sergiotaborda:

public class MathUtils{

   public long fatorial(long n){

         if (n<0){
                throw new IlegalArgumentException();
        }
   	 F f = new F(n);
         while(!f.isFinished()){
             f.factorize();
         } 
         return f.value;
   }

   private class F {
        long n;
        long value=1;
         
F(long n){
 this.n =n;
}
        boolean isFinished(){
               return n<=1;
        }
        void factorize(){
           value *= n; 
           n--; 
        }
  }
}

De 8 linhas de código passamos a 30, e com uma private class.
Oba! A idéia agora passou a ser complicar ao máximo o código. :D

Como fatorial cresce muito rapidamente, seria interessante usar BigInteger, não?

Eh meio dificil imaginar alguem pulando e dando gritinhos de felicidade ao ver uma classe chamada MathUtils…

Só se alguem implementar ao menos uma Transformada de Fourier. Se não fica difícil alguem dar uns gritinho de euforia mesmo.

http://en.wikipedia.org/wiki/Fourier_transform

xandroalmeida:

De 8 linhas de código passamos a 30, e com uma private class.
Oba! A idéia agora passou a ser complicar ao máximo o código.

Eficiencia do Código não se mede em linhas de codigo :twisted: . A ideia era ser mais eficiente ao não pesar no stack. A ideia era aumentar a eficiencia.

A ideia do BigInteger seria interessante tb se houver interesse em aumentar o contra-dominio da função.
Para implementar FFT precisa de numeros complexos. Implemente numeros complexos primeiro :lol:

(nota: tudo isto existe no commons-math , e suponho que com implementações inteligentes e eficientes, estamos só exercitando)

A idéia é justamente o contrário(hahah), para podermos termos um link de referência para os iniciantes, que vivem perguntando essas coisas…

certamente, algo + ou - do tipo:

public BigInteger fatorial(String s){ BigInteger cont=BigInteger.ONE; BigInteger resultado=BigInteger.ONE; BigInteger valor=new BigInteger(s); while(cont.compareTo(valor)<0){ cont= cont.add(BigInteger.ONE); resultado=resultado.multiply(cont); } return resultado; }
Mas pode levar um zilhão de anos se o número for muito grande…aí só com algoritmos específicos para otimizar o troço.

Colocando um fibonacci(rec) para aumentarmos a nossa classe:

public static long fibonacci(int n){ if(n<=1) return n; else return fibonacci(n-1) + fibonacci(n-2); }

(nota: tudo isto existe no commons-math , e suponho que com implementações inteligentes e eficientes, estamos só exercitando)

Hmm… Já que estamos falando em fatorial, deixa eu postar um problema aqui que envolve fatorial (e que até poderíamos colocar na MathUtils, apesar de eu não conhecer nenhuma utilidade para a função que irei apresentar).

A função Z(n) é uma função que recebe um número natural como parâmetro e retorna o número de zeros presentes no final do fatorial desse número. Por exemplo:

Z(5): 5 * 4 * 3 * 2 * 1 = 120. O número de zeros no final de 120 é 1, então Z(5) é igual a 1.
Z(10): 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 3628800. O número de zeros no final é 2, então Z(10) é igual a 2.

Outros exemplos: Z(60) = 14, Z(100) = 24, etc. O n pode ser um número muito grande. Posso querer saber Z(1000), por exemplo.

Como resolver esse problema? Obviamente, calcular o fatorial e contar o número de zeros não é viável. A minha solução foi a seguinte: o número de zeros no final vai depender do número de 10 presentes na multiplicação, por exemplo:

Z(5): 5 * 4 * 3 * 2 * 1 => 10 * 4 * 3 * 1 => Um 10, então possui um zero no final.
Z(10): 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 => 10 * 9 * 8 * 7 * 6 * 10 * 4 * 3 * 1 => Dois 10, então possui dois zeros no final.

Mas é possível simplificar isso dizendo que o número de zeros no final é igual ao número de 5s na multiplicação, tendo em vista que o número de 2s que existem na multiplicação é bem maior que o de 5s e esses 2s que sobram não influenciam no número de 10s, pois o 2 precisa estar com o 5 pra produzir um 10.

Exemplo:

10! = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
Z(10!) = (2*5 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1) = Dois cincos, dois zeros no fim.

30! = 30 * 29 * 28 * 27 * … * 6 * 5 * 4 * 3 * 2 * 1
Z(30!) = 30 * 25 * 20 * 15 * 10 * 5 (descartamos o restante pois precisamos apenas dos múltiplos de 5)
Z(30!) = 65 * 55 * 45 * 35 * 2*5 * 5 = Sete cincos, implica em 7 zeros no final.

Pra contar o número de 5s, eu fiz essa função:

public static int z(int n) {
   int cincos = 0; // o número de cincos
   int aux;

   while (n > 0) {
        aux = n;
        while (aux > 0) {
            if (aux%5 == 0)
                cincos++;
            else
                break;
            aux /= 5;
        }
        n--;
   }

   return cincos;
}

Esse código está retornando o resultado certo, mas ele tem complexidade O(n log n) e o local onde eu vi o problema dizia que dava pra fazer com O(log n). Alguém tem alguma idéia de como fazer isso?

jingle:

sergiotaborda:

Schuenemann:

Prefiro alterar o fatorial() para isso:

public long fatorial(long n) { if (n < 0) throw new IllegalArgumentException("deu chabu"); long[] fat = new long[n]; fat[0] = 1; for (long i = 1; i < fat.length; i++) fat[i] = i * fat[i - 1]; return fat[n]; }

1. Porque for em vez de recursividade ?
2. Porque array para memorizar tudo ?

A verificação do n é uma boa

também não vejo vantagens em fazer deste modo. até o código fica mais poluído.

Se livrar da recursão é uma vantagem e tanto. Tenta ver até que número consegue calcular na primeira forma. Não sei nem pra que o argumento é um long, acho que não vai nem conseguir extrapolar um byte

A idéia do array era só organizar melhor, usando o valor como índice do array. Poderia usar um List e gravar os resultados, talvez.

O exemplo de fibonacci recursivo é ainda pior, porque você recalcula várias vezes a mesma coisa. Além de ser recursivo, claro.

David, nesse link tem uma fórmula pra calcular essa quantidade de zeros ( nem me pergunte entendi a fórmula mas não entendi sua origem )

http://www.pagalguy.com/forum/quantitative-questions-and-answers/20789-finding-number-zero-s-factorial.html

Acho que a complexidade dela é bem menor q n log(n)

iterar é humano, recorrer é divino.

Agora alguém poste uma implementação do block-lanczos, pois fatorial já perdeu a graça e pq não algo útil.

Até é útil, pois no próprio algorítimo citado, se usa fatoração internamente.

Boom Shankar 8)

Algoritmos com alguns cálculos matriciais:
http://www.unicamp.br/~hans/mc102/java/book/matrizes.pdf

O Tiago Peczenyj tinha postado uma vez o livro do Tao Pang, nesse tópico http://www.guj.com.br/posts/list/69379.java:

“An Introduction to Computational Physics, 2nd Edition”

Exercícios do livro:
http://www.physics.unlv.edu/~pang/cp2_j.html

Ajuda a validar seus algoritmos de cálculo numérico…

mfjeng:

Algoritmos com alguns cálculos matriciais:
http://www.unicamp.br/~hans/mc102/java/book/matrizes.pdf

É pena que não se use OO nesse codigo.
Por exemplo, a transposta da matriz é simplesmente um adaptator que troca as colunas com as linhas
É muito mais rápido que um for num for.

Sim. Mas a partir daí…

sergiotaborda:

mfjeng:

Algoritmos com alguns cálculos matriciais:
http://www.unicamp.br/~hans/mc102/java/book/matrizes.pdf

É pena que não se use OO nesse codigo.
Por exemplo, a transposta da matriz é simplesmente um adaptator que troca as colunas com as linhas
É muito mais rápido que um for num for.

Até onde eu sei, por parte de diversos professores que trabalham em institutos de pesquisa, uma parte enorme dos códigos de cálculo numérico utilizados pelo CPTEC/INPE e outros institutos de pesquisas são totalmente procedurais. O povo nestes locais não gosta de OO, dizem que é lento demais comparado ao C puro ou ao Fortran…
O problema é que criam monstros impossíveis de manter

cassio:

sergiotaborda:

mfjeng:

Algoritmos com alguns cálculos matriciais:
http://www.unicamp.br/~hans/mc102/java/book/matrizes.pdf

É pena que não se use OO nesse codigo.
Por exemplo, a transposta da matriz é simplesmente um adaptator que troca as colunas com as linhas
É muito mais rápido que um for num for.

Até onde eu sei, por parte de diversos professores que trabalham em institutos de pesquisa, uma parte enorme dos códigos de cálculo numérico utilizados pelo CPTEC/INPE e outros institutos de pesquisas são totalmente procedurais. O povo nestes locais não gosta de OO, dizem que é lento demais comparado ao C puro ou ao Fortran…
O problema é que criam monstros impossíveis de manter :-)

Se não fizessem isso não teriam trabalho. Muito poucos conhecem OO, para começo de conversa.

sergiotaborda:

cassio:

sergiotaborda:

mfjeng:

Algoritmos com alguns cálculos matriciais:
http://www.unicamp.br/~hans/mc102/java/book/matrizes.pdf

É pena que não se use OO nesse codigo.
Por exemplo, a transposta da matriz é simplesmente um adaptator que troca as colunas com as linhas
É muito mais rápido que um for num for.

Até onde eu sei, por parte de diversos professores que trabalham em institutos de pesquisa, uma parte enorme dos códigos de cálculo numérico utilizados pelo CPTEC/INPE e outros institutos de pesquisas são totalmente procedurais. O povo nestes locais não gosta de OO, dizem que é lento demais comparado ao C puro ou ao Fortran…
O problema é que criam monstros impossíveis de manter :-)

Se não fizessem isso não teriam trabalho. Muito poucos conhecem OO, para começo de conversa.

Infelizmente isso é um fato. E vários dos que conhecem não usam, pelos motivos (na opinião deles) que eu já citei.

hehe,

legal esse link do livro do Tao, vou incluir em meus favoritos...

public class MatrizUtils {
    
    public static String toText(Integer[][] m) {
        StringBuilder sb = new StringBuilder();
        
        int linhas = m.length;
        for(int i=0; i<linhas ; i++ ) {
            int colunas = m[i].length;
            sb.append("[ ");
            for(int j=0; j<colunas; j++) {
                if( j==0 ) {
                   sb.append( m[i][j] );
                } else {
                   sb.append( ", "+m[i][j] );
                }
            }
            sb.append(" ]\n");
        }
        return sb.toString();
    }

    /**
     * A transposta de uma Matriz A<sub>mxn</sub> é uma matriz A<SUP>t</SUP><SUB>nxm</SUB>
     * onde cada elemento de A<SUP>t</SUP><SUB>ij</SUB> = A<SUB>ji</SUB>
     * 
     * @param m - matriz a ser calculada a transposta
     * @return matriz transposta
     */
    public static Integer[][] transposta(Integer[][] m) {
        int linhas = m.length;
        int colunas = m[0].length;
        Integer[][] t = new Integer[ colunas ][ linhas ];
        for(int i=0; i<linhas ; i++ ) {
            for(int j=0; j<colunas; j++) {
                t[j][i] = m[i][j];
            }
        }
        return t;
    }
    
    /**
     * matrizIgual - verifica a igualdade de duas matriz. Duas matrizes são ditas iguais
     * quando todos os elementos A<sub>ij</sub> forem iguais aos elementos B<sub>ij</sub>.
     * 
     * @param A - primeira matriz a ser comparada
     * @param B - segunda matriz a ser comparada
     * @return true se todos os elementos de A<sub>ij</sub> forem iguais aos elementos de B<sub>ij</sub>
     */
    public static boolean matrizIgual(Integer[][] A,  Integer[][] B) {
        int linhasA = A.length;
        int linhasB = B.length;
        int colunasA = A[0].length;
        int colunasB = B[0].length;
        if( linhasA != linhasB || colunasA != colunasB )
            return false;
        
        for(int i=0; i<linhasA ; i++ ) {
            for(int j=0; j<colunasA; j++) {
                if( A[i][j] != B[i][j] ) {
                    return false;
                }
            }
        }
        return true;
    }
    
    /**
     * Matriz Zero é uma matriz em que todos os elementos possuem o valor 0
     * 
     * @param linhas - número de linhas da nova matriz
     * @param colunas - número de colunas da nova matriz
     * @return matrizZero - matriz com todos os elementos com valor 0.
     */
    public static Integer[][] matrizZero(int linhas, int colunas) {
        Integer[][] m = new Integer[linhas][colunas];
        for(int i=0; i<linhas ; i++ ) {
            for(int j=0; j<colunas; j++) {
                m[i][j] = 0;
            }
        }
        return m;
    }

    /**
     * matrizDiagonal é a matriz em que todos os elementos a<sub>ij</sub>=0 para os elementos de índices i!=j.
     * @param mat que será extraida a matriz diagonal
     * @return matrizDiagonal
     */
    public static Integer[][] matrizDiagonal(Integer[][] mat) {
        int linhas = mat.length;
        int colunas = mat[0].length;
        Integer[][] m = new Integer[linhas][colunas];
        for(int i=0; i<linhas ; i++ ) {
            for(int j=0; j<colunas; j++) {
                if( i != j ) {
                   m[i][j] = 0;
                } else {
                   m[i][j] = mat[i][j];
                }
            }
        }
        return m;
    }
    
    /**
     * matrizIdentidade é a matriz em que os elementos da diagonal principal tem o 
     * valor 1 e os elementos que não fazem parte da matriz diagonal tem valor 0.
     * @param linhas - número de linhas da matriz Identidade
     * @param colunas  - número de colunas da matriz Identidade
     * @return matriz identidade
     */
    public static Integer[][] matrizIdentidade(int linhas, int colunas) {
        Integer[][] m = new Integer[linhas][colunas];
        for(int i=0; i<linhas ; i++ ) {
            for(int j=0; j<colunas; j++) {
                if( i != j ) {
                   m[i][j] = 0;
                } else {
                   m[i][j] = 1;
                }
            }
        }
        return m;
    }

    /**
     * Cria uma matriz identidade nas mesmas dimensões da mat informada.
     * @param mat matriz em que será copiado as dimensões
     * @return matriz identidade
     */
    public static Integer[][] matrizIdentidade(Integer[][] mat) {
        int linhas = mat.length;
        int colunas = mat[0].length;
        Integer[][] ret = matrizIdentidade(linhas,colunas);
        return ret;
    }
    
    /**
     * MatrizTriangularSuperior é a matriz em que os elementos i<j são zero.
     * @param mat
     * @return
     */
    public static Integer[][] matrizTriangularSuperior(Integer[][] mat) {
        int linhas = mat.length;
        int colunas = mat[0].length;
        Integer[][] ret = new Integer[linhas][colunas];
        for(int i=0; i<linhas ; i++ ) {
            for(int j=0; j<colunas; j++) {
                if( i>j ) {
                    ret[i][j] = 0;
                } else {
                    ret[i][j] = mat[i][j];
                }
            }
        }
        return ret;
    }

    /**
     * MatrizTriangularInferior é a matriz em que os elementos i>j são zero.
     * @param mat
     * @return
     */
    public static Integer[][] matrizTriangularInferior(Integer[][] mat) {
        int linhas = mat.length;
        int colunas = mat[0].length;
        Integer[][] ret = new Integer[linhas][colunas];
        for(int i=0; i<linhas ; i++ ) {
            for(int j=0; j<colunas; j++) {
                if( i<j ) {
                    ret[i][j] = 0;
                } else {
                    ret[i][j] = mat[i][j];
                }
            }
        }
        return ret;
    }
    
    /**
     * A matriz é chamada de simetrica quando A = A<sup>t</sup>.
     * 
     * @param A
     * @return
     */
    public static boolean matrizSimetrica(Integer[][] A) {
        Integer[][] At = transposta(A);
        return matrizIgual(A, At);
    }
    
    /**
     * A multiplicação de duas matrizes A e B, que são compatíveis no sentido que o
     * número de colunas de A é igual o número de linhas B, é definida por:
     * Se A=(a<sub>ij</sub>) é uma matriz m x n e B=(b<sub>jk</sub>) é uma matriz n x p,
     * então seu produto de matrizes C=AB é a matriz mxp C=(cik), onde:
     * c<sub>ik</sub>=somatório(j=1,n)a<sub>ij</sub>b<sub>jk</sub>
     * 
     * @param A primeira matriz, nas dimensões m x n.
     * @param B segunda matriz, nas dimensões n x p.
     * 
     * @return C - a matriz contendo o produto de A por B
     */
    public static Integer[][] produto(Integer[][] A, Integer[][] B) {
        int m  = A.length;
        int n  = A[0].length;
        int n2 = B.length;
        int p  = B[0].length;
        
        // verifica a compatibilidade
        if( n != n2 ) {
            throw new RuntimeException("Matriz incompátiveis para serem multiplicadas.");
        }
        Integer[][] C = new Integer[m][p];
        for(int i=0 ; i<m ; i++) {
           for(int j=0 ; j<p ; j++) {
               C[i][j] = 0;
               for(int k=0 ; k<n ; k++) {
                  C[i][j] = A[i][k] * B[k][j];
               }
           }
        }
        return C;
    }
    
    /**
     * verifica se uma matriz é quadrada. Diz-se matriz quadrada para as matrizes em que 
     * o número de linhas é igual o número de colunas.
     * 
     * @param A
     * @return true se matriz for quadrada.
     */
    public static boolean matrizQuadrada(Integer[][] A) {
        int m  = A.length;
        int n  = A[0].length;
        return m == n;
    }
    
    /**
     * Retorna o determinante, utilizando a decomposição LU.
     * 
     * técnica descrita em Algoritmos de Cormen, Leiserson, Rivest e Stein.
     * @param A matriz a ser calculado o determinante
     * @return determinante da matriz informada.
     */
    public static Integer determinante(Integer[][] A) {
        int linhas = A.length;
        int colunas = A[0].length;
        if( linhas != colunas ) {
            throw new RuntimeException("Não é possível calcular o determinante de matriz não quadrada.");
        }
        
        int J = 1;
        int[] permutacoes = new int[linhas];
        for(int i=0 ; i<linhas ; i++) {
            permutacoes[i] = i;
        }

        // método de decomposição LU
        int[][] lu = new int[linhas][colunas];
        for(int col=0 ; col<colunas ; col++) {
            int soma = 0;
            // triangulo superior (U)
            for(int lin=0 ; lin<col ; lin++) {
                soma = lu[lin][col];
                for(int i=0 ; i<lin ; i++) {
                    soma -= lu[lin][i] * lu[i][col];
                }
                lu[lin][col] = soma;
            }
            // triangulo inferior (L)
            int max = col; // permutation row
            int maior = 0;
            for (int lin=col; lin<linhas; lin++) {
                soma = lu[lin][col];
                for (int i=0; i<col; i++) {
                    soma -= lu[lin][i] * lu[i][col];
                }
                lu[lin][col] = soma;
                if (Math.abs(soma) > maior) {
                    maior = Math.abs(soma);
                    max = lin;
                }
            }
            
            if( Math.abs(lu[max][col]) < 10E-12) {
                lu = null;
                return 0; // matriz singular possui determinante igual a 0
            }
            
            if (max != col) {
                int tmp = 0;
                for(int i = 0; i<colunas; i++) {
                    tmp = lu[max][i];
                    lu[max][i] = lu[col][i];
                    lu[col][i] = tmp;
                }
                int temp = permutacoes[max];
                permutacoes[max] = permutacoes[col];
                permutacoes[col] = temp;
                J = -J;
            }

            for (int lin = col + 1; lin < linhas; lin++) {
                lu[lin][col] /= lu[col][col];
            }
        }
        int determinante = J;
        for(int i=0; i<linhas; i++) {
                determinante *= lu[i][i];
        }
        return determinante;        
    }
}

E parabéns ao Ironlynx pela iniciativa, as coisas estavam realmente calmas por aqui...

fw

cassio:

Até onde eu sei, por parte de diversos professores que trabalham em institutos de pesquisa, uma parte enorme dos códigos de cálculo numérico utilizados pelo CPTEC/INPE e outros institutos de pesquisas são totalmente procedurais. O povo nestes locais não gosta de OO, dizem que é lento demais comparado ao C puro ou ao Fortran…
O problema é que criam monstros impossíveis de manter :-)

Para muita coisa OO é simplesmente desnecessária ou cria um overhead indesejado. Tratamento de imagens, por exemplo, é uma área que Java e OO simplesmente não ajudam. Você quer que seu código seja o mais eficiente possível e para isso é necessário estar muito mais próximo do hardware do que é permitido com Java.

Dou como exemplo implementar os vários algoritmos de composição Porter-Duff, por mais que se tente, a versão java vai ser muito mais lenta que uma feita em C sem muita preocupação com performance.

Olá

E que tal se a forma recursiva implementasse uma uma forma simples da chamada “Tail Recursion”?

Não sei se todos aqui sabem, mas o Scala é simplesmente uma espécie de front end para o Java. O compilador Scala gera bytecode Java. Mas a linguagem é muito mais poderosa do que o Java e inclui um monte de facilidades a mais para o programador. Uma das facilidades é que o compilador Scala otimiza a recursão quando a última instrução chama a função novamente. Ele percebe isto e simplesmente volta para a instrução inicial sem precisar carregar nada na stack.

Vejam como ficaria o fatorial em Scala:

def fatorial(x: BigInt): BigInt = if (x == 0) 1 else x * fatorial(x - 1)

[]s
Luca

Luca:

Olá

E que tal se a forma recursiva implementasse uma uma forma simples da chamada “Tail Recursion”?

Não sei se todos aqui sabem, mas o Scala é simplesmente uma espécie de front end para o Java. O compilador Scala gera bytecode Java. Mas a linguagem é muito mais poderosa do que o Java e inclui um monte de facilidades a mais para o programador. Uma das facilidades é que o compilador Scala otimiza a recursão quando a última instrução chama a função novamente. Ele percebe isto e simplesmente volta para a instrução inicial sem precisar carregar nada na stack.

Vejam como ficaria o fatorial em Scala:

def fatorial(x: BigInt): BigInt = if (x == 0) 1 else x * fatorial(x - 1)

[]s
Luca

Luca, desculpa ser chato, mas teu exemplo não é tail recursive. A última instrução é “x * ___” e não uma chamada a outra função. Uma implementação de fatorial que é tail recursive fica assim:

def fatorial(x: BigInt): BigInt =
  fatorial (1, x)

def fatorial(cur : BigInt, x: BigInt) : BigInt =
  if (x == 0) cur else fatorial(cur * x, x - 1)

Agora um desafio, como implementar fibonacci de maneira tail recursive e que não tenha performance quadrática.

Olá

Certo, na verdade eu dei uma forçada de barra. O exemplo que ia copiar e colar do livro de Scala era este que realmente é tail recursive para o Scala

def approximate(guess: Domain) : Domain = if (isGoodEnough(guess)) guess else approximate(improve(guess))

Mas como o papo era sobre fatorial, forcei a barra para mostrar que o Scala tem muita coisa legal.

[]s
Luca (que hoje instalou o yaws para tentar usar o yaws com o rails através do fuzed, alguém já fez isto por aqui?)

Legal - se você, em Scala, usar “tail call” (não é exatamente como o Luca fez, mas um pouco mais complicado) o Scala remove a recursão na hora de gerar os bytecodes.

package example;

import scala.collection.mutable.ListBuffer

object Factorial {
  
  // Implementando o método "List.range" para BigInt.
  def range (start: BigInt, end: BigInt): List[BigInt] = {
    val b = new ListBuffer[BigInt]
    var i = start
    while (i < end) {
      b += i
      i += 1
    }
    b.toList
  }  
  
  // Fatorial sem recursão
  // A inferência de tipos indica que este método poderia
  // ser declarado como "def fact1 (n : BigInt) : BigInt"
  def fact1 (n : BigInt) = {
    range(1,n + 1).reduceLeft[BigInt] {_*_}
  }
  
  // Fatorial sem "tail call"
  // Note que como o Scala não consegue inferir os tipos,
  // precisamos declará-los explicitamente.
  def fact2 (n : Int) : BigInt = {
    n match {
      case 0 => 1
      case 1 => 1
      case _ => BigInt(n) * fact2 (n - 1)
    }
  }
  
  // Fatorial com "tail call"
  // Para usar "tail call" devemos usar um acumulador.
  // Usando "tail call", o Scala compila isto para um código não-recursivo
  // algo parecido com:
/*
public scala.BigInt factN(int, scala.BigInt);
  Code:
   0:   aload_0
   1:   astore_3
   2:   iload_1
   3:   istore  4
   5:   iload   4
   7:   tableswitch{ //0 to 1
                0: 47;
                1: 51;
                default: 28 }
   28:  iload_1
   29:  iconst_1
   30:  isub
   31:  getstatic       #36; //Field scala/BigInt$.MODULE$:Lscala/BigInt$;
   34:  iload_1
   35:  invokevirtual   #63; //Method scala/BigInt$.apply:(I)Lscala/BigInt;
   38:  aload_2
   39:  invokevirtual   #68; //Method scala/BigInt.$times:(Lscala/BigInt;)Lscala/BigInt;
   42:  astore_2
   43:  istore_1
   44:  goto    2
   47:  aload_2
   48:  goto    52
   51:  aload_2
   52:  areturn
 */
  def fact3 (n : Int) : BigInt = {
    // Note a função interna...
    def factN (n: Int, acc: BigInt) : BigInt = {
      n match {
        case 0 => acc
        case 1 => acc
        case _ => factN (n - 1, BigInt(n) * acc)
      }
    }
    factN (n, 1)
  }
 
  def main(args : Array[String]) : Unit = {
    Console.println (fact1 (10))
    Console.println (fact2 (10))
    Console.println (fact3 (10))
  }
}

o Post me fez fuçar código velho. Alguém uns posts atrás calculou o numero de combinações, esse algoritmo calculas As combinações propriamente ditas.

T+

/**
	 * Construtor de FullKNSubset. C(n,p)
	 * @param n Numero do conjunto.
	 * @param p Numero das partes.
	 */
	public FullKNSubset(int n, int p) {
 	 this.n = n;
 	 this.p = p;
 	 x = new int[p];
 	 y = new int[p+1];
	}

	private int sum(int k, int j, int z) {
 	 for(i=0;i <= j;i++)
  	  z += y[i];
	return z+k;
	}

	private void combiner(int i) {
 	 for(x[i]=sum(i,i,0);x[i]<=n-(p-i);x[i]++)
  	  if (i != p-1) 
   	   combiner(i+1); 
  	  else 
   	   show();
 	  y[i+1]=0;
 	  y[i]++;
	}
	
	/**
	 * Invoca o metodo de combinatoria.
	 */
	public void combinatoriaAlgorithm() {
		combiner(0);
	}

	// Coloca o vetor de combinacao em uma string.
	private void show() {
	 for(i=0; i < p;i++)
	  System.out.print(x[i]+" ");
	 System.out.println();
	}

public static boolean isPar( int num ) { return ( num & 1 ) == 0; }

public static boolean isPrimo( int x ) { for( int i = 2; i < x; i++ ) { if( x % i == 0 ) { return false; } } return true; }

Há algum outro método melhor que esse para números primos?

MathUtils extends MakerMath {

}

Ganhei.

Carnevalli:

public static boolean isPrimo( int x ) { for( int i = 2; i < x; i++ ) { if( x % i == 0 ) { return false; } } return true; }

Há algum outro método melhor que esse para números primos?

Eu diria que existem alguns mais eficientes em certos casos:

T+

Carnevalli:

public static boolean isPrimo( int x ) { for( int i = 2; i < x; i++ ) { if( x % i == 0 ) { return false; } } return true; }

Há algum outro método melhor que esse para números primos?

Não é necessário testar de 2 até x, basta de 2 até o piso da raiz de x.

Versão eficiente do Fibonacci recursivo usando programação dinâmica:

public static long fibonacci(int n, long [] cache){
		
	if(cache[n] == -1){
		if(n < 2) cache[n] = n;
		else cache[n] = fibonacci(n - 1, cache) + fibonacci(n - 2, cache);
	}
			
	return cache[n];
}

Fibonacci com tail calls e outras coisas (em Scala)

package example
import scala.collection.mutable._

object Fibonacci {
  // A definição boba de Fibonacci.
  def fibo1 (n : Int) : BigInt = {
    n match {
      case 0 => 0
      case 1 => 1
      case _ => fibo1 (n - 1) + fibo1 (n - 2)
    }
  }
  // Tail call
  def fibo2 (n : Int) : BigInt = {
    def fibo (n: Int, current: BigInt, next: BigInt) : BigInt = {
      n match {
        case 0 => current
        case _ => fibo (n - 1, next, current + next)  
      }
    }
    fibo (n, 0, 1)
  }
  // "Memoizing" simples. Não tem tail calls, mas é útil quando
  // é complicado transformar um algoritmo recursivo 
  // em outro com tail calls. Neste caso, definimos
  // um mapa com os valores precalculados.
  // (Não sou Scala-man, então esta maneira de "memoizing" é bem ingênua.) 
  var f = Map.empty[Int,BigInt] 
  f(0) = BigInt (0)
  f(1) = BigInt (1)
  def fibo3 (n : Int) : BigInt = {
    if (!(f contains n)) 
      f(n) = fibo3(n - 1)  + f(n - 2)
    f(n)
  }
  
  def main(args : Array[String]) : Unit = {
    println (fibo1 (20))
    println (fibo2 (20))
    println (fibo3 (20))
  }
}

Esses códigos em Scala, e esse tópico aqui: http://guj.com.br/posts/list/86101.java me lembraram do tempo em que eu mexia com Haskell( http://osereojava.blogspot.com/2006/02/um-pouco-de-haskellrepost.html )… bateu um saudosismo. :-o

Alguém tinha falado de “fatoriaisrápidas”, parece que um dos melhores algoritmos é o Prime Swing.Veja aqui(códigos em java e C++):
http://www.luschny.de/math/factorial/FastFactorialFunctions.htm
Aliás, essa página é bacana ( http://www.luschny.de/math/ ) pena que a parte em Alemão, eu não entendo bulhufas…

o Post me fez fuçar código velho. Alguém uns posts atrás calculou o numero de combinações, esse algoritmo calculas As combinações propriamente ditas.

Esse algoritmo apenas combina numeros. Existe algum algoritmo para , dado um conjunto populado com objetos criar as combinações ? algo como

combinacao ({"A","B","C"} , 2 ) 

// produz

AB
AC
BC

o Post me fez fuçar código velho. Alguém uns posts atrás calculou o numero de combinações, esse algoritmo calculas As combinações propriamente ditas.

Esse algoritmo apenas combina numeros. Existe algum algoritmo para , dado um conjunto populado com objetos criar as combinações ? algo como

combinacao ({"A","B","C"} , 2 ) 

// produz

AB
AC
BC

ué, mas aí basta voce usar os números gerados no algoritmo como índices.

int[] letras = {'A', 'B', 'C'}

int[] indices = {0,1,2}

e aplique o algoritmo em indice[] e evoque como indice[] em letras

letras[indices[i]];

Com isso voce consegue combinar qualquer coisa enumerável. Tipo:

Object[] objs = { new T1(), new T2(), new T3() ;

objs[indices[i]];

T+

Ok, mas eu me referia a algoritmos que não calculem primeiro os indices mas que usem estruturas como Set ou List.

Repare que, usando indices, o algoritmo é cego aos elementos. Se eu passar {A,A,A} o resultado seria AA, AA, AA.
mas isso é errado. Na realidade só tenho um elemento no conjunto. Sim, sim… poderia filtrar usando set ou alguma coisa… eu so achei que poderia existir um algoritmo famoso (desses que até têm nome) que fosse mais inteligente e já tomasse contas dessas coisas sem ter que “filtrar na mão”.

Vixi isso tudo é vontade de programar? perai que eu vou mandar uns casos de usos pra vocês, vou aproveitar, programação na faixa.

Acho que você está confundindo as estruturas. Se você ter um algoritmo que leve em consideração multiplicidade ((A,A,A) tem multiplicidade 3), você não está falando de combinações, e sim falando de String Theory, ou se a multiplicidade dos elementos tiverem uma estrutura bem definida, pode se enquadrar na família das partições ou composições. Numa estrutura de conjuntos, no caso de combinações, a mutiplicidade é ignorada

O que tem de famoso nisso é mudar a estrutura se voce tem (A,A,A), voce pode trata-lo como a estrutura que lhe convier. A mais abrangente nesse caso seria o objeto combinatorial String, e para (A, A, A), ele teria o alfabeto com um símbolo e dimensão 3, como o número de possibilidades de Strings é m^n, com m = numero de símbolos e n a dimensao da String, ficaria, nesse caso, 1^3 = 1. Em outro termos, voce só tem arranjo (A,A,A) dentro dessa definição.

Eu explico mais dessas coisas e sobre outras familias de estruturas aqui

T+

Esqueci de mencionar, mas se voce acha que tem alguma estrutura mais genérica que consiga transformar uma estrutura em outra, existe sim, (definida por um grafo, sendo mais exato), ela é descrita no capitulo 13 deste livro…mais ainda assim, ela tem uma fase de “encoding” e “decoding” de uma estrutura para outra.

T+

Proteu Alcebidiano:

sergiotaborda:

Ok, mas eu me referia a algoritmos que não calculem primeiro os indices mas que usem estruturas como Set ou List.

Repare que, usando indices, o algoritmo é cego aos elementos. Se eu passar {A,A,A} o resultado seria AA, AA, AA.
mas isso é errado.

Acho que você está confundindo as estruturas. Se você ter um algoritmo que leve em consideração multiplicidade ((A,A,A) tem multiplicidade 3), você não está falando de combinações, e sim falando de String Theory,

A não é uma string. É um objeto qualquer. A letra foi so para identificar o objeto sem usar numeros.
{A,A,A} é um conjunto formado por três instancias de A. Contudo, elas são a mesma instancia , logo é equivalente a {A} apenas. Combinações de 1 elemento 3 a 3 não são possiveis. Logo, o algoritmo de combinações teria que levar em conta isso. É só disso que estou a falar.

O n de C(n,k) é o tamanho do conjunto de elementos diferentes. não ?

A String que estou a definir não é exatamente a String tipo de dado, É uma estrutura combinatorial =D

Combinações de 1 elemento 3 a 3 não são possiveis justamente porque a definição de combinação é considerar os elementos de uma dada dimensão como diferentes.

Repetindo o que escrevi lá em cima, se voce tem {A,A,A} isso não é uma estrutura de combinação, é uma estrutura de String (lembre que a String que falo aqui é String do link que te passei ;)). Você não pode efetuar combinações em uma estrutura que não obedece a definição de KN-Subsets (objetos combinados). E como falei também, voce pode, usando a definição do livro que mencionei no post anterio, jogar uma estrutura qualquer (inclusive essa do seu exemplo) no grafo que ele saberá direcionar para a familia combinatorial desejada =)

T+

T+