Três técnicas com as quais programar com mais eficiência

perfomence_functional

Neste artigo, veremos três técnicas que nascem diretamente da programação funcional . Vamos ver como seria sua implementação em C #, temos que levar em consideração que nem todas as linguagens de programação fornecem as ferramentas para executar esse tipo de algoritmo e, nas quais elas podem ser implementadas, isso não é feito da mesma maneira, em muitos aspectos a sintaxe É muito elegante, como poderia ser o caso do F #.

Avaliação preguiçosa

A avaliação preguiçosa é uma técnica que atrasa a avaliação de uma expressão até que ela seja usada . Vejamos um exemplo no qual os números primos estão sendo retornados. Vamos ver primeiro como seria a função de força bruta:

public static IEnumerable<int> FB(int inicio, int fin)
    {
        List<int> l = new List<int>();
        for (int i = inicio; i < fin; i++ )
        {
            if (IsPrimoEsperate(i))
                l.Add(i);
        }
        return l;
    }

E como seria com a avaliação preguiçosa ou preguiçosa. Seriam duas funções, embora você pudesse colocar tudo em uma .

   private static IEnumerable<int> Lazy()
    {
        int n = 1;
        while (true)
        {
            if (IsPrimoEsperate(n))
                yield return n;
            n++;
        }
    }

    public static IEnumerable<int> Lazy(int inicio, int fin)
    {
        return Lazy().Skip(inicio).Take(fin);
    }

Ambos os métodos usarão uma função auxiliar que determina se o número é primo. Além de fazer nossos testes , adicionamos um atraso artificial :

private static bool IsPrimoEsperate(int n)
    {
        Thread.Sleep(1);
        bool isPrime = true;
        for (int i = 2; i <= Math.Sqrt(n) && isPrime; i++)
            isPrime = n % i != 0;
        return isPrime;
    }

Para mim, essa é minha técnica favorita, mas condiciona que o que estamos retornando seja uma coleção que implemente a interface IEnumerable genérica . Como veremos mais adiante, todas as estruturas fundamentais do C Sharp implementam essa interface. Uma maneira fácil de ver se uma classe implementou essa classe é se podemos executar um foreach nela . Se observarmos essa técnica em vez de retornar a coleção depois que ela for totalmente processada, o que ela faz é que, em cada iteração, ela retorna um elemento que fará parte da coleção , é necessário usar a sintaxe:

  yield return elemento ;

Memorização

Memorização é uma técnica pela qual os resultados da aplicação de uma função pura a uma coleção são mantidos em cache . Uma função pura é aquela que, para um parâmetro, sempre e sempre retornará o mesmo resultado. Por exemplo, esses tipos de funções são típicas da biblioteca de classes Math de C # e Java , e outra que não é será a função Random. Vamos ver um exemplo semelhante ao anterior, no qual estamos retornando os números primos de uma coleção:

 public static IEnumerable<int> Memoriza(int inicio, int fin)
    {
        List<int> l = new List<int>();
        for (int i = inicio; i < fin; i++)
        {
            if (v1.Keys.Contains(i))
                l.Add(i);
            else
                if (IsPrimoEsperate(i))
                {
                    l.Add(i);
                    v1.Add(i, i);
                }
        }
        return l;
    }

Sua técnica utiliza uma estrutura adicional, um dicionário:

Relacionado:  Qual é o padrão de design do adaptador?
 static IDictionary<int, int> v1 = new Dictionary<int, int>();

Um problema óbvio ao usar esta técnica é que teremos que ter um cache que ocupará muita memória , teremos que ver se o que obteremos com o tempo da CPU nos compensa com o que nos ocupará na memória.

Avaliação e memorização preguiçosas híbridas

É simplesmente uma combinação de ambas as técnicas. Pode ser visto como uma avaliação lenta que usará um cache . Portanto, novamente teremos um dicionário:

 static IDictionary<int, int> v2 = new Dictionary<int, int>();

E vamos implementá-lo com duas funções:

  public static IEnumerable<int> LM()
    {
        int i = 1;
        while (true)
        {
            if (v2.Keys.Contains(i))
                yield return v2[i];
            else
                if (IsPrimoEsperate(i))
                {
                    v2.Add(i, i);
                    yield return i;
                }
            i++;
        }
    }

    public static IEnumerable<int> LM(int inicio, int fin)
    {
        return LM().Skip(inicio).Take(fin);
    }

Tempos de medição

Para decidir qual é o melhor, teremos que medi-los de alguma forma, usaremos o seguinte código:

    static void Main(string[] args)
    {

        var crono = new Stopwatch();
        crono.Start();
        var result = FB(0, 100);
        crono.Stop();
        long a = crono.ElapsedTicks;
        Console.WriteLine("Fuerza bruta 1: {0:N} ticks. Result: {1}.", a,    result.Last(x => IsPrimoEsperate(x)));

        crono.Restart();
        result = FB(0, 100); crono.Stop();
        a = crono.ElapsedTicks;
        Console.WriteLine("Fuerza bruta 2: {0:N} ticks. Result: {1}.", a, result.Last(x => IsPrimoEsperate(x)));

        crono.Restart();
        result = Lazy(0, 26); crono.Stop();
        a = crono.ElapsedTicks;
        Console.WriteLine("Lazy 1: {0:N} ticks. Result: {1}.", a, result.Last(x => IsPrimoEsperate(x)));

        crono.Restart();
        result = Lazy(0, 26); crono.Stop();
        a = crono.ElapsedTicks;
        Console.WriteLine("Lazy 2: {0:N} ticks. Result: {1}.", a, result.Last(x => IsPrimoEsperate(x)));

        crono.Restart();
        result = Memoriza(0, 100); crono.Stop();
        a = crono.ElapsedTicks;
        Console.WriteLine("Memoriza 1: {0:N} ticks. Result: {1}.", a, result.Last(x => IsPrimoEsperate(x)));

        crono.Restart();
        result = Memoriza(0, 100); crono.Stop();
        a = crono.ElapsedTicks;
        Console.WriteLine("Memoriza 2: {0:N} ticks. Result: {1}.", a, result.Last(x => IsPrimoEsperate(x)));

        crono.Restart();
        result = LM(0, 26); crono.Stop();
        a = crono.ElapsedTicks;
        Console.WriteLine("Memoriza y Lazy 1: {0:N} ticks. Result: {1}.", a, result.Last(x => IsPrimoEsperate(x)));

        crono.Restart();
        result = LM(0, 26); crono.Stop();
        a = crono.ElapsedTicks;
        Console.WriteLine("Memoriza y Lazy 2: {0:N} ticks. Result: {1}.", a, result.Last(x => IsPrimoEsperate(x)));
}

Testaremos cada técnica duas vezes, já que a técnica de memorização só é útil se usarmos o algoritmo mais de uma vez em uma execução.

Relacionado:  Estruturas de dados de rede: os gráficos

Resultados

Como podemos ver na imagem a seguir:

vezes

As técnicas que explicamos resolvem o problema com mais eficiência do que a técnica de força bruta, mas isso nem sempre precisa ser benéfico, pois essas técnicas (especialmente a memorização) tendem a consumir mais memória com o que os programadores Será vital decidir se o tempo de CPU que ganhamos nos beneficiará o suficiente para ter que sacrificar mais memória.

 

Você pode estar interessado:

Deixe um comentário