sábado, 23 de marzo de 2013

Simulando operaciones de conjuntos con C#.

Es comun encontrarnos con problemas que involucran conjuntos de elementos los cuales hay manejar como tales, o sea garantizando que no contengan elementos repetidos y que esten definidas las operaciones de union, interseccion y diferencia.
Aqui dejo un ejemplo de una clase que he nombrado ObjectSet que implementa estos servicios sobrecrgando los operadores +, - y * para realizar las operaciones de unión, diferencia e intersección respectivamente.

La clase tiene un miembro privado una lista genérica.
private List<T> items;

A continuación se implementan los siguientes servicios que se esperan por parte los clientes para poder manipular los elementos contenidos en el conjunto.

AddItem
RemoveItem
RemoveAt
Count
Y una enumeración para obtener/establecer el valor de elementos dentro de la lista items.
Todo ello se encuentra en la seccion Wrappers de código.


Podrían seguirse declarando o incluso utilizar un acercamiento diferente haciendo que la clase sea un descendiente de List<>, preferí hacerlo así para poder controlar a que servicios de la clase los clientes tienen acceso y a cuales no de forma más simple.

Más adelante se sobreescriben algunos métodos para personalizar el comportamiento de la clase como por ejemlo a la hora de mostrala por pantalla [ToString], comparar entre sí objetos de la clase. Esto se encuentra en la seccion Overridings.

A continuación aparecen los constructores de la clase. Son tres y puede extenderse la clase creando otros.
  1. El constructor sin parámetros solo inicializa la lista.
  2. El constructor que toma como paramétro otro objecto copia los elementos del objeto hacia el nuevo
  3. El constructos que toma como parámetro un arreglo nos sirve inicializar un objeto de la clase partiendo del arreglo.

Y ahora, la próxima sección del código de implementación de la clase define como se comportarán los operadores: +, - y * para obtener el resultado de la operación Unión, Diferencia e Intersección respectivamente. Es aquí que se realiza el trabajo.
 
Por último un ejemplo sencillo de tres arreglos de cadenas y obtener el conjunto unión de los tres.
El código que usa esta clase pues es muy simple:
  

Conviene decir que esta clase no está completamente desarrollada ni he probado exahustivamente su código. Muchas mejoras se podrían hacer, por ejemplo se podria habilitar un método que devuelva los elementos del conjunto como un arreglo; pero creo que para ilustrar el propósito del post es suficiente.

Esta debería ser la filosofía para este tipo de problemas.

domingo, 10 de febrero de 2013

Cálculo con numeros relativamente grandes.

En algunas ocasiones el sentido común puede ser una guía mas bien engañosa. Sobre todo cuando tratamos problemas simples en los cuales se ven envueltos, a veces sin que estemos completamente conscientes de ello, números grandes.

Por ejemplo veamos un problema clásico:

No todos los juegos, son deportes. Aun más son pocos los deportes que tienen asociado a su nacimiento una leyenda que contiene un problema matemático. Me estoy refiriendo a la leyenda que cuenta el origen del juego de ajedrez. A grandes rasgos la leyenda cuenta que en el momento en que el sultán conoció el juego, este le gustó tanto que quiso premiar a su creador. Teniéndose sí mismo por un gran hombre, le pidió que el expresara un deseo y lo vería hecho realidad. La respuesta fue insólita. El creador del juego pidió un grano de trigo por la primera casilla del tablero, dos por la segunda, cuatro por la tercera, ocho por la siguiente y así sucesivamente. El sultán se sintió menospreciado por este hombre y le ordenó que esperase fuera; que inmediatamente le sería entregado dentro de un saco lo que pidió.

Nuestro sultán terminó sin saberlo con dos regalos, un juego trascendental y una lección de humildad. A veces lo grandes hombres reciben más regalos de los que pueden apreciar. 

Volviendo a C#, si nos correspondiese a nosotros desempeñar el rol de matemático de la corte, nuestra respuesta debería ser la misma que recibió el sultán de la leyenda: ni sembrando toda la superficie de a tierra durante varios años y entregando hasta el último grano cosechado podrían satisfacer la petición formulada por su creador. La única diferencia es que nosotros podemos llegar más rápido a esa conclusión. Escribir unas pocas líneas de código C# dentro del cuerpo de una función es todo lo que tenemos que hacer. Estas líneas podrían tener el siguiente aspecto:

static long CantidadSemillas(int alto = 8, int ancho = 8)
{
long resultado = 0;
int celdas = alto * ancho;

for (int i = 0; i < celdas; i++)
resultado += (long)Math.Pow(2, i);

return resultado;
}

Utilizando esta función para un tablero de 4x4 casillas, obtendríamos rápidamente la respuesta: 65535 granos de trigo. Sin embargo para un tablero normal de 8x8 casillas obtenemos -1. No hay errores en tiempo de ejecución y sin embargo la respuesta es incorrecta. Esta es la parte donde el “gran hombre” nos mandaría a decapitar. Aún sin cabeza deberíamos preguntarnos ¿qué fue lo que ocurrió y por qué recibimos una respuesta disparatada en lugar de un mensaje de error? 

Modifiquemos el código anterior para usar enteros largos sin signo. Quedaría así.

static ulong CantidadSemillas(int alto = 8, int ancho = 8)
{
ulong resultado = 0;
int celdas = alto * ancho;

for (int i = 0; i < celdas; i++)
resultado += (ulong)Math.Pow(2, i);

return resultado;
        }

Al ejecutar este código recibimos la respuesta correcta: 18446744073709551615

De aquí podemos deducir que anteriormente hubo un error de desborde, tanto la respuesta como algunos de los cálculos intermedios para determinar la respuesta era representable usando variables de tipo entero largo. Las variables de tipo entero largo utilizan 8 bytes y pueden tomar valores enteros entre -9223372036854775808 y 9223372036854775807.

Pero aún tenemos la curiosidad, ¿por qué no nos fue notificado que había ocurrido un error? Volvamos a modificar el código para que utilice checked y quede así:

       static ulong CantidadSemillas(int alto = 8, int ancho = 8)
       {
            ulong resultado = 0;

            int celdas = alto * ancho;
           
            checked
            {
                for (int i = 0; i < celdas; i++)
                    resultado += (ulong)Math.Pow(2, i);
            }

            return resultado;
       }

Ahora calculamos la cantidad de semillas de trigo a entregar si usásemos un ajedrez modificado al estilo Sheldon Cooper y las dimensiones del tablero fueran de 16X16 casillas.

Ahora sí recibimos nuestra querida Overflow Exception que nos notifica que algo fue mal evitándonos respuestas incorrectas. Si comentamos la línea de código que contiene checked y volvemos a correr el programa pues obtenemos una respuesta incorrecta que tomaríamos como correcta con todas las consecuencias que podría traer esto. Las computadoras no se equivocan pero este comportamiento es lo más parecido.

La palabra clave checked se utiliza para habilitar precisamente el chequeo de errores de desbordamiento para expresiones no constantes en tiempo de ejecución. Es necesario prever la aparición de números grandes en cálculos intermedios para habilitar esta opción o no. Esta trivialidad ha causado comportamientos anómalos en más de una ocasión que pueden hacernos sentir que "perdemos la cabeza".