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