¿Debemos aprender una nueva forma de escribir bucles?

English version 

 

Hasta el momento, cada vez que alguien menciona los peligros potenciales que comenzarán a “rondar” al programador con la introducción de las nuevas características de C# 3.0 (la inferencia de tipos de variables locales –léase var- y los métodos extensores, principalmente), mi reacción es siempre la misma: considero que son recursos necesarios para ofrecer el soporte a las consultas integradas, no son en principio características carentes de atractivo ni mucho menos “impresentables”, y a través de la educación podremos alertar a los desarrolladores para que sean capaces de evitar los peligros que el uso de estas características podría esconder.

 

Hace unos días he visto un post de Luke Hoban que ha reforzado mi convicción en el papel que tendremos los formadores en la educación de los programadores .NET; en este caso, enseñándoles a no utilizar las consultas integradas para lo que no tiene sentido. El post en cuestión muestra cómo resolver la distribución de pesas en una balanza utilizando un enfoque de fuerza bruta: una serie de “bucles” anidados que se modelan utilizando el operador de consulta estándar Range(min, max), que produce secuencialmente los valores enteros entre min y max, ambos inclusive. Me pareció una situación en la que la consulta integrada no aporta nada con relación a bucles tradicionales, y que sí podría comprometer el rendimiento.

 

El problema en cuestión me recordó ciertos ejercicios que poníamos hace 20 años en la Universidad a los estudiantes de la asignatura “Introducción a la Programación” (bajo la inestimable dirección del Dr. Miguel Katrib). Así que decidí programar uno de estos ejercicios por las dos vías: mediante bucles “tradicionales” y “a la Hoban”, para comparar ambas implementaciones.

 

Enunciado: Escriba un programa que determine todos los números de cuatro cifras que son iguales a la suma de las cuartas potencias de cada una de las cifras que lo componen. Por ejemplo, uno de esos números es 1634:

 

                 1634 = 14 + 64 + 34 + 44

 

Solución (naïve): Iteramos en un cuádruple bucle anidado sobre todos los posibles valores de cada una de las cuatro cifras del número.

 

Al final de este post se presenta el código del programa que prueba ambas variantes; en la variante basada en bucles, hemos introducido una lista genérica para hacerla lo más parecida posible a la variante LINQ.

 

En mi portátil, la relación entre los tiempos consumidos fue de 80:95. Honestamente, esperaba un desequilibrio bastante mayor. Pero lo importante es: ¿aporta algo la utilización de una consulta integrada aquí? Las opiniones son bienvenidas.

 

//*********************************************************************

class Program

{

    static void Main(string[] args)

    {

        Stopwatch sw = new Stopwatch();

        sw.Start();

        // versión "clásica"

        List<int> cumplen = new List<int>();

        for (int i1 = 1; i1 <= 9; i1++)

        for (int i2 = 0; i2 <= 9; i2++)         for (int i3 = 0; i3 <= 9; i3++)

        for (int i4 = 0; i4 <= 9; i4++)

            if (Condicion(i1, i2, i3, i4))

                cumplen.Add(Numero(i1, i2, i3, i4));

        foreach (int n in cumplen)

            Console.WriteLine(n);

        sw.Stop();

        Console.WriteLine("Transcurrido: " + sw.ElapsedMilliseconds.ToString());

        sw.Start();

        // versión LINQ

        IEnumerable<int> cumplen2 =

            from j1 in Enumerable.Range(1, 9)

            from j2 in Enumerable.Range(0, 9)

            from j3 in Enumerable.Range(0, 9)

            from j4 in Enumerable.Range(0, 9)

                where Condicion(j1, j2, j3, j4)

                    select Numero(j1, j2, j3, j4);

        foreach (int n in cumplen2)

            Console.WriteLine(n);

        sw.Stop();

        Console.WriteLine("Transcurrido: " + sw.ElapsedMilliseconds.ToString());        Console.ReadLine();

    }

    static bool Condicion(int a, int b, int c, int d)

    {

        return Numero(a, b, c, d) == Cuarta(a) + Cuarta(b) + Cuarta(c) + Cuarta(d);

    }

    static int Numero(int a, int b, int c, int d) { return 1000 * a + 100 * b + 10 * c + d; }

    static int Cuadrado(int a) { return a * a; }     static int Cuarta(int a) { return Cuadrado(a) * Cuadrado(a); }

}

//*********************************************************************

 

Published 25/4/2007 2:19 por Octavio Hernández
Archivado en:
Comparte este post:

Comentarios

Wednesday, April 25, 2007 3:06 AM por Alfredo Novoa

# re: ¿Debemos aprender una nueva forma de escribir bucles?

Dos cosas.

La versión LINQ no es completamente LINQ por que el método Condición se debería de eliminar y volver a comparar velocidades.

La versión LINQ en principio es mejor por que es mucho más optimizable por el compilador.

Si en la siguiente versión de LINQ mejoran el optimizador, este podría fácilmente darse cuenta de que la expresión es constante, y calcularla solo en tiempo de compilación almacenando el resultado en el ejecutable, con lo que sería mucho más rápida que la versión procedimental.

Wednesday, April 25, 2007 11:55 AM por Octavio Hernández

# re: ¿Debemos aprender una nueva forma de escribir bucles?

Hola, Alfredo!

a) Lo de quitar el método Condicion - la idea original era llamarlo también en la versión de arriba para "equiparar".

He puesto la condición "en línea" y los tiempos siguen siendo los mismos. Seguramente una mejor idea de esto nos la daría el problema original de Hoban, donde hay ¡trece! bucles anidados...

b) Lo de la expresión constante, francamte no lo veo... ¿Qué expresión es constante ahí? Sobre todo, ¿qué optimización puede hacerse ahí que no podría hacerse en la versión de arriba?

c) Lo que creo está claro es q la versión LINQ es más declarativa. Lo único q me desentona un poco es el nombre de la clase "Enumerable". Creo q me gustaba más "Sequence" en la preview anterior. Pero es solo un detalle.

Salu2 - Octavio

Wednesday, April 25, 2007 12:39 PM por Alfredo Novoa

# re: ¿Debemos aprender una nueva forma de escribir bucles?

¡Hola Octavio!

Poniendo la condición "en línea" le das más oportunidades al optimizador para optimizar la consulta. Está claro que optimizar esa consulta aún está muy lejos de las posibilidades de Orcas (tampoco le podemos pedir mucho a una primera versión), pero eso puede cambiar con el tiempo, cosa que es extremadamente improbable con la versión clásica.

La expresión:

           from j1 in Enumerable.Range(1, 9)

           from j2 in Enumerable.Range(0, 9)

           from j3 in Enumerable.Range(0, 9)

           from j4 in Enumerable.Range(0, 9)

               where Condicion(j1, j2, j3, j4)

                   select Numero(j1, j2, j3, j4);

es una constante, y el compilador debería de tratarla como tal.

El que condición sea un método dificulta el que se pueda averiguar que es una expresión constante, pero tampoco es muy difícil de comprobar que Condición es una función referencialmente transparente (lo que implica que la expresión es constante).

Una cosa que le vendría muy bien a .NET es marcar con un atributo las funciones referencialmente opacas.

¡Cuando contratarán a un verdadero experto en bases de datos para hacer estas cosas! :)

Wednesday, April 25, 2007 1:52 PM por Octavio Hernández

# re: ¿Debemos aprender una nueva forma de escribir bucles?

Alfredo,

Ya veo por donde vas... ¡Genial! *TODA* la expresión de consulta podría calcularse en tiempo de compilación. En eso ni había pensado (está claro q queda lejos de lo q hará Orcas).

Bueno, creo q podría decirte "pero supongamos q añadimos una condición al problema de modo que los límites de iteración se determinen en ejecución, bla, bla, bla..." pero no lo voy a hacer :-) La idea está clara.

>> ¡Cuando contratarán a un verdadero experto en bases de datos para hacer estas cosas!

Cierto, una vez que metes estos recursos en el lenguaje hay q traer a gente con experiencia en optimización de consultas, etc. Me parece q para esta versión no se ha hecho mucho en ese sentido. Pero seguramte más adelante...

Wednesday, April 25, 2007 3:00 PM por Alfredo Novoa

# re: ¿Debemos aprender una nueva forma de escribir bucles?

Octavio,

La idea es que con este tipo de programación cada vez nos podemos centrar más en la especificación dejando la elección de los algoritmos al sistema.

Como tu dices la solución de los 4 bucles es ingenua. Si programas de forma procedimental eso es lo que tienes y tendrás siempre, en cambio con LINQ cada vez tendremos mejores optimizadores y alguno podría llegar a encontrar soluciones mejores sin que a nosotros nos cueste ningún esfuerzo.

Wednesday, April 25, 2007 11:41 PM por Octavio Hernández

# re: ¿Debemos aprender una nueva forma de escribir bucles?

>> La idea es que con este tipo de programación cada vez nos podemos centrar más en la especificación dejando la elección de los algoritmos al sistema.

Sí, vamos avanzando por ese camino...

Friday, April 27, 2007 1:43 PM por Sobre C#, LINQ y algo más...

# Should we learn a new way of writing loops?

(This post is a slightly-edited English translation of a previous one in Spanish , with some added comments

Monday, October 12, 2009 3:31 AM por Sobre C#, LINQ y algo más...

# Buscando "El símbolo perdido" con LINQ

Últimamente he estado leyendo en los ratos libres " El símbolo perdido ", la

Monday, October 12, 2009 4:08 AM por Sobre C#, LINQ y algo más...

# Buscando "El símbolo perdido" con LINQ

Últimamente he estado leyendo en los ratos libres " El símbolo perdido ", la