4

Tenho um determinado int e gostaria de transformá-lo em um outro que seja resultado da soma de seus dígitos da melhor forma possível. Por exemplo:

int n = 2601;

Deve resultar em 9 já que este é o resultado de 2+6+0+1. Qual a forma com o melhor desempenho para obter este comportamento?

Baseado nesta resposta do Stack Overflow vou listar duas formas, mas não pensei em um modo de testar qual tem melhor desempenho e não sei se há alguma outra possibilidade que se sobressaia a essas também:


Forma 1:

public int somarDigitos(int numero) {
  int resultado = 0;

  while (numero != 0) {
    int digito = numero % 10;
    numero = numero / 10;
    resultado = resultado + digito;
  }

  return resultado;
}

Forma 2:

public int somarDigitos2(int numero) {
  String texto = String.valueOf(numero);
  int resultado = 0;

  for (char digito : texto.toCharArray()) {
    resultado = resultado + Character.getNumericValue(digito);
  }

  return resultado;
}
5
  • 2
    A primeira alternativa evita a criação de dois objetos (a String cria o primeiro objeto, aí o toCharArray cria p segundo), então sou tendencioso a achar que a primeira será mais rápida Commented 27/11/2017 às 9:22
  • Seguindo a linha do comentário acima, acho que evitar Strings é a melhor opção... Commented 27/11/2017 às 10:15
  • 1
    Quase de certeza que trabalhar só com números é mais rápido que com strings, mas talvez ainda faça uns testes e coloque como resposta
    – Isac
    Commented 27/11/2017 às 10:26
  • Cheirinho de problema XY?
    – mari
    Commented 27/11/2017 às 17:42
  • @Sorack Performance depende muito do problema que se quer resolver: é mais "performático" em relação ao tempo de execução? em relação ao uso de memória?... Curto o sistema do SO de perguntas+respostas objetivas, para problemas reais, mas ok, to each his own.
    – mari
    Commented 27/11/2017 às 18:21

1 Resposta 1

3

A melhor forma de saber qual é mais rápido é fazendo testes executando o algoritmo esperado muitas vezes e comparar.

Claro que o teste precisa de cuidados para não dar resultados tendenciosos. Respondi algo voltado para C#, mas quase tudo vale parta Java.

Manipulação de números é uma operação nativa do processador e tem alta performance.

O algoritmo com número fará 3 operações matemática, no máximo 3 transportes de dados (é provável que exista alguma otimização que mantenha algo no registrador e fique bem mais rápido e terá um branch, o que pode mais trazer demora, mas acho que a predição de desvio do processador deve funcionar bem neste caso.

Vou descartar a carga necessária para converter a string para array de char imaginando que a linguagem faça alguma otimização e não precise fazer nada pesado, mas se tiver que realmente fazer um trabalho físico aqui já deve ter um compromisso de performance. A pergunta não quer saber detalhes :)

Tem pelo um branch do for, talvez mais porque o que eu vi da getNumericValue() ela faz verificações sobre a procedência do conteúdo. No mínimo tem uma operação matemática e um transporte dentro da função. Se não conseguir linearizar a função fica muito pior porque não poderá otimizar para uso de registrador, haverá mais 2 transportes e mais overhead para gerenciar a chamada da função.

Tem uma operação matemática e um transporte visível no código. Mas muita coisa invisível. E parece que esta parte é bem mais pesada do que aparenta.

Eu fiz um teste e a diferença é de duas ordens de magnitude. Mas pode variar em certas circunstâncias. Eu espera uma boa diferença, mas não tão grande assim, por isso que testar é importante.

Testei o algoritmo, porque sequer saber a diferença de desempenho é ele que deve ser analisado.

Testei em ambientes diferentes e os resultados foram consistentes.

Porém em uso real tem uma série e outras coisas para resolver. E me parece que o Java não é bom de otimizar isto. Se você chamar uma função com o algoritmo a chamada da função pesará muito e coloca os dois algoritmo mais perto da paridade.

Se não tiver algo que eu não sei fazer no Java faz muita diferença chamar uma função ou executar de forma direta. Aí fica para os Javeiros com larga experiência nisso falar. Admito que posso ter errado na avaliação, mas nada fácil de perceber.

class Main{
    public static void main(String []args) {
        int numero = 123456;
        long time = System.nanoTime();
        for (int i = 0; i < 10000000; i++) {
            int resultado = 0;
            while (numero != 0) {
                numero /= 10;
                resultado += numero % 10;
            }
        }
        System.out.println((System.nanoTime() - time) + "ns");
        time = System.nanoTime();
        for (int i = 0; i < 10000000; i++) {
            String texto = String.valueOf(numero);
            int resultado = 0;
            for (char digito : texto.toCharArray()) {
                resultado = resultado + Character.getNumericValue(digito);
            }
        }
        System.out.println((System.nanoTime() - time) + "ns");
    }
}

Veja funcionando no ideone. E no repl.it. Também coloquei no GitHub para referência futura.

6
  • Sobre a sua metodologia, refaço a observação que fiz ao @Isac. Também questiono que você fez com um só tamanho de inteiro. Tamanhos distintos talvez pudesse oferecer uma análise para detectar a mudança de branch. Commented 27/11/2017 às 11:30
  • Eu testei o que ele criou, se eu testar com alguma outra coisa aí não é o que ele está propondo.
    – Maniero
    Commented 27/11/2017 às 11:32
  • 1
    Minha crítica não é em relação ao que foi testado :-) Mas sim que na sua medição acaba entrando o tempo de manutenção do laço. 1.000.000 (ou são mais do que 6 zeros?) de incrementos e comparações e desvios que não fazem parte do que realmente está sendo estudado acabam entrando na medição. Detalhes de metodologia, mas ainda assim uma pulga atrás da minha orelha fica me cutucando. Assim como a invocação de lambdas nas minhas medições também me incomoda... Commented 27/11/2017 às 11:36
  • 1
    @JeffersonQuesado eu concordo, como você eliminaria isto?
    – Maniero
    Commented 27/11/2017 às 11:37
  • 1
    Nunca fiz no Java, mas em todos os testes que fiz em outras plataformas não dá certo.
    – Maniero
    Commented 27/11/2017 às 11:43

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .