• Hola, con los nuevos cambios del sitio he puesto diferentes tipos de publicidad que podrian resultar algo molestas. Sin embargo, luego de registrarte e interactuar un poco con la pagina, van a ser reemplazados por otros mas sutiles y pequeños! * A mi tampoco me gusta la publicidad, pero es una de las piezas para que el sitio esté disponible. Si bloqueas la publicidad, probá desactivarla unos dias.
    Gracias

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

ice

Usuario con historia
#1
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 perezosaLa 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ónLa 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ónEs 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; 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 tiemposPara 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.

ResultadosComo observamos en la siguiente imagen:



 

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.