Tres técnicas con las que programar de forma más eficiente

COMPARTIR 0 TWITTEAR

perfomence_functional

En este artículo veremos 3 técnicas que nacen directamente de la programación funcional. Vamos a ver como sería su implementación en C#, tenemos que tener en cuenta que no todos los lenguajes de programación proporcionan las herramientas para realizar este tipo de algoritmos y en los que se pueden implementar no se hace en todos igual, en muchos aspectos la sintaxis es muy prolija como podría ser el caso de F #.

Evaluación perezosa

La evaluación perezosa es una técnica por la que se demora la evaluación de una expresión hasta que esta sea utilizada. Veamos un ejemplo en el que se van devolviendo los números primos. Veamos primero como sería la función por fuerza 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;
    }

Y como sería con evaluación perezosa o Lazy. Serian dos funciones aunque se podría poner todo en una.

   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 métodos usarán una función auxiliar que determina si el número es primo. Además para hacer nosotros nuestras pruebas le añadimos un retardo 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 mi esta es mi técnica preferida, pero nos condiciona que lo que vayamos devolviendo sea una colección que implemente la interfaz genérica IEnumerable. Como ya veremos más adelante todas las estructuras fundamentales de C Sharp implementan esta interfaz. Una forma fácil de ver si una clase tiene implementada esta clase es si sobre ella podemos realizar un foreach. Si nos fijamos esta técnica en vez de devolver la colección una vez es enteramente procesada lo que hace es que en cada iteración va devolviendo un elemento que formará parte de la colección, es necesario utilizar la sintaxis:

  yield return elemento ;

Memorización

La memorización es una técnica por la que se van guardando en un caché los resultados de aplicar una función pura a una colección. Una función pura es aquella que para un parámetro siempre, y siempre, devolverá el mismo resultado. Por ejemplom este tipo de funciones son las típicas de la biblioteca de clases Math de C# y Java, y otra que no lo es será la función Random. Veamos un ejemplo similar al anterior en el que vamos devolviendo los números primos de una colección:

 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;
    }

Es técnica hace uso de una estructura adicional, un diccionario:

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

Un problema evidente a la hora de usar esta técnica es que tendremos que tener una cache que nos ocupará mucha memoria, tendremos que ver si lo que ganaremos de tiempo de CPU nos compensa con lo que nos ocupará en memoria.

Hibrido de evaluación perezosa y memorización

Es simplemente una combinación de ambas técnicas. Puede verse como una evaluación perezosa que utilizará una cache. Por tanto, nuevamente tendremos un diccionario:

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

Y la implementaremos con dos funciones:

  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);
    }

Midiendo tiempos

Para decidir cuál es mejor tendremos que medirlas de alguna forma, utilizaremos el siguiente 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)));
}

Probaremos dos veces cada técnica puesto que la técnica de memorización solo es útil si usamos el algoritmo más de una vez en una ejecución.

Resultados

Como observamos en la siguiente imagen:

tiempos

Las técnicas que hemos explicado resuelven el problema de forma más eficiente que la técnica por fuerza bruta, pero no tiene por qué ser siempre esto beneficioso, puesto que estas técnicas (en especial la de memorización) tienden a consumir más memoria con lo que como programadores será vital decidir si ese tiempo de CPU que ganamos nos beneficiará lo suficiente como para tener que sacrificar más memoria.

Archivado en C, C sharp, Curso de Programación, Evaluación perezosa, Memorización, Programación funcional
COMPARTIR 0 TWITTEAR

Comentarios (10)

Usa tu cuenta de Facebook para dejar tu opinión.

Otras webs de Difoosion