14 de jan de 2013

Armazenando resultados e melhorando desempenho. Exemplo prático!

Hoje eu estava lendo o GUJ e vi uma duvida de uma pessoa que precisava calcular todos os números primos que antecedem um número X. Me lembrei da época de maratona que o tempo de execução era bem importante. Resolver o problema dos números primos é bem simples, porém fazê-lo ficar eficiente é mais simples ainda.




Primeiramente vamos fazer da maneira mais simples possível, que é para cada número calcular todos os primos que o antecedem:

public static void testePrimoCalcularUmPorUm() {



        String pathIn = "/home/pognao/testePrimoCalcularUmPorUm";

        BufferedWriter wr = null;



        try {



            wr = new BufferedWriter(new FileWriter(pathIn));

            for (int numero = 2; numero < PAR_TESTE; numero++) {



                /*

                 * como verificar se um numero é primo ? Um número primo só pode

                 * ser divisível por 1 e por ele mesmo.

                 */

                ArrayList<Integer> numerosPrimos = new ArrayList<>();

                numerosPrimos.add(1);

                for (int i = 2; i < numero; i++) {

                    if (ehPrimo(i)) {

                        numerosPrimos.add(i);

                        wr.write(i);

                    }

                }

            }

            wr.close();

        } catch (Exception e) {



        }

    }



Agora a forma melhorada consistem em armazenar todos os primos até o teto definido em um array e depois apenas ir buscando neste array os resultados.


public static void testePrimoCalcularArray() {



        ArrayList<Integer> numerosPrimos = new ArrayList<>();

        numerosPrimos.add(1);

        for (int i = 2; i < PAR_TESTE; i++) {

            if (ehPrimo(i)) {

                numerosPrimos.add(i);

            }

        }



        String pathIn = "/home/pognao/testePrimoCalcularArray";

        BufferedWriter wr = null;



        try {



            wr = new BufferedWriter(new FileWriter(pathIn));

            for (int numero = 2; numero < PAR_TESTE; numero++) {



                for (Integer imprimir : numerosPrimos) {

                    if (imprimir < numero) {

                        wr.write(imprimir);

                    } else

                        break;



                }

            }

            wr.close();

        } catch (Exception e) {



        }

    }




Resultados


Para realizar os testes foram utilizados 3 parâmetros, o primeiro é calcular a lista de primos até o número 100, o segundo até o 1000 e o terceiro até 10000.
O resultado é mostrado na tabela e nos gráficos abaixo. Mas claramente percebemos que há uma melhora significativa de desempenho no caso de realizarmos os cálculos antes e armazenarmos em um array.





Execução
Parametro Tempo ms
testePrimoCalcularUmPorUm 100 19
testePrimoCalcularArray 100 2
testePrimoCalcularUmPorUm 1000 97
testePrimoCalcularArray 1000 16
testePrimoCalcularUmPorUm 10000 51959
testePrimoCalcularArray 10000 115

2 comentários:

  1. Diego, você poderia postar a definição da função ehPrimo() ! Por acaso você usou algum crivo? Queria poder fazer uma comparaçao!

    ResponderExcluir
  2. Neste caso utilizei a definição mais simples possível para é primo:

    Para X se X != de 1:

    Para i = 2; i < X ; i++ {
    if (i!=X && X%i==0) return false;
    }

    return true

    ResponderExcluir