4

Objetivo: otimizar a performance

Descrição do problema:

Tenho uma função que me retorna se a palavra é um palíndromo com true senão com `false, até ai tranquilo, porém preciso melhorar a performance da função.

Código:

static bool checkPalindrome(string inputString) 
{
    
    if(inputString.Length>=1 && inputString.Length <= Math.Pow(10, 5))
     {
        string palindromo = "";

        for (Int32 i = inputString.Length-1; i >= 0; --i)
        {
                  palindromo += inputString[i];   
        }
         if (palindromo.ToLower().Equals(inputString.ToLower()))
             return true;
         else
             return false;
        
     }
     else
     {
        return false;
     }
}

2 Respostas 2

8

Além deste código não ser idiomático C# (parece que foi escrito em outra linguagem), ele faz muitas coisas sem necessidade, inclusive alocação de memória.

A principal mudança é não alocar um novo objeto que é algo que pode criar um problema de mudança, só fiz comparações porque o problema só pede isso. E comparar um por um é a melhor forma. Apesar de não ser visível esses métodos que está usando são compostos por laços, eles varrem os dados inteiros todas as vezes, é muito ruim.

Outra mudança é sair tão logo saiba que não é palíndromo, e isso deve ocorrer muito, é fácil não ser. Quando você já sabe que não é não tem porque continuar o algoritmo.

Por último verifico apenas até a metade, porque se eu continuar o resultado já é sabido. O que diferiria eu analisar o primeiro com o último e depois o último com o primeiro? Dá no mesmo.

Não melhorei a validação porque não sei os requisitos.

using static System.Console;
                    
public class Program {
    public static void Main() {
        WriteLine(checkPalindrome("ana"));
        WriteLine(checkPalindrome("abba"));
        WriteLine(checkPalindrome("oki"));
    }
    static bool checkPalindrome(string inputString) {
        if(inputString.Length >= 1 && inputString.Length <= 100_000) {
            for (var i = 0; i < inputString.Length / 2; i++) if (char.ToLower(inputString[i]) != char.ToLower(inputString[inputString.Length - i - 1])) return false;
            return true;
        }
        return false;
    }
}

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

1
  • Maniero depois de ver o seu código vi o quanto o meu faz coisas sem necessidade rs.. Obrigado pela ajuda!
    – rlimadev
    Commented 1/02/2019 às 12:19
1

Minha sugestão é essa, primeiro converte a String em um Array. Depois inverte o Array. Volta numa String para então fazer a comparação em maiúsculas.

public bool éPalindromo(string entrada)
{            
    return !string.IsNullOrEmpty(entrada) && new string(entrada.ToCharArray()
    .Reverse().ToArray()).ToUpper() == entrada.ToUpper();
}
4
  • 2
    Isto piorará a performance imensamente.
    – Maniero
    Commented 1/02/2019 às 10:01
  • @Maniero me explica uma coisa(não é uma pergunta, só um esclarecimento). O Runtime do c# não vai criar um binder para cada método invocado? Esses binders, não serão armazenados um único callsite para ToCharArray().Reverse().ToArray(). Então depois da terceira chama os únicos métodos que terão impacto não serão string.IsNullOrEmpty, CallSiteBinder.Bind() e entrada.ToUpper()? Commented 1/02/2019 às 12:39
  • 1
    Não, nada disso existe. Na verdade o que está afirmando também não faz sentido do ponto de vista lógico. E o problema maior é a alocação de memória de vários objetos e que são percorridos várias vezes. O único método que não tem impacto é o que você disse que terá. São 6 loops (todos alocam). O dele tinha 3, o meu tem 1 sem alocação.
    – Maniero
    Commented 1/02/2019 às 12:44
  • Faz o teste de performance e veja o quarto resultado. Commented 1/02/2019 às 12:46

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 .