Ordenamiento externo: Mezcla Natural (Natural Merge Sort)

1. Algoritmo original.
2. Algoritmo genérico.
3. Ordenando cadenas binarias.
4. Ordenando cadenas.
5. Ordenando enteros grandes.
6. Ordenando objetos.

Entre los métodos de ordenamiento externos más comunes se encuentran el de Mezcla Directa (o Merge Sort) y el de Mezcla Natural (o Natural Merge Sort). El método de Mezcla Natural consiste en aprovechar la existencia de secuencias ya ordenadas dentro de los datos de los archivos. A partir de las secuencias ordenadas existentes en el archivo, se obtienen particiones que se almacenan en dos archivos o ficheros auxiliares. Las particiones almacenadas en estos archivos auxiliares se fusionan posteriormente para crear secuencias ordenadas cuya longitud se incrementa arbitrariamente hasta conseguir la total ordenación de los datos contenidos en el archivo original.

Para ilustrar la Mezcla Natural es muy conveniente utilizar números enteros como los datos almacenados en un archivo, de tal manera que este método funciona como se ilustra en el siguiente ejemplo (se utilizan corchetes o paréntesis cuadrados para separar las secuencias en las particiones):

Nombre del archivo original: Origen
Archivos auxiliares: Auxiliar1 y Auxiliar2

Origen: [10,17],[5,8,9],[3,22,50],[4],[2,20,30],[11,16,19],[6,21,23]

Primera Iteración: Las secuencias que se encuentren dentro del archivo origen se almacenan de forma alternada en los archivos auxiliares:
Partición
Auxiliar1: [10,17],[3,22,50],[2,20,30],[6,21,23]
Auxiliar2: [5,8,9],[4,11,16,19]

Aquí vale la pena resaltar lo que sucede con la secuencia [4] del archivo origen: cuando se realizan las particiones (aún sin entrar al proceso de fusión) los elementos 11, 16 y 19 se convierten en una sola secuencia junto con el 4.

La fusión se realiza por pares de secuencias de manera ordenada, así, la primer nueva secuencia está formada por los elementos de la primera secuencia en el archivo Auxiliar 1 y los elementos de la primera secuencia en el archivo Auxiliar2. Si uno de los archivos auxiliares llega a su fin, las secuencias que se encuentren en el otro archivo sin terminar se vacían directamente después de las nuevas secuencias:
Fusión en el archivo original
Origen: [5,8,9,10,17],[3,4,11,16,19,22,50],[2,20,30],[6,21,23]

Segunda Iteración: Se repite el proceso de partición con las nuevas secuencias:
Partición
Auxiliar1: [5,8,9,10,17],[2,20,30]
Auxiliar2: [3,4,11,16,19,22,50],[6,21,23]

Cuando al comparar un par de secuencias en los archivos auxiliares una de ellas llega a su fin, entonces simplemente se vacía el resto de la secuencia que aún contiene elementos en la nueva secuencia. Este caso se observa claramente en el par de secuencias azules: cuando se llega al elemento 17 del archivo Auxiliar1, la nueva secuencia en la fusión simplemente incluye los elementos 19, 22 y 50 del archivo Auxiliar2 al final.
Fusión en el archivo original
Origen: [3,4,5,8,9,10,11,16,17,19,22,50],[2,6,20,21,23,30]

Tercera Iteración: En este punto se cuenta ya con sólo un par de secuencias. La fusión de éstas da como resultado una secuencia que contiene todos los elementos del archivo Origen en orden ascendente.
Partición
Auxiliar 1: [3,4,5,8,9,10,11,16,17,19,22,50]
Auxiliar 2: [2,6,20,21,23,30]

Fusión
Origen:  [2,3,4,5,6,8,9,10,11,16,17,19,20,21,22,23,30,50]

En este último paso, los datos contenidos en el archivo origen se encuentran ordenados de manera ascendente. En la Mezcla Natural se comparan pares de secuencias contenidas en los archivos auxiliares con el objetivo de formar nuevas secuencias durante el proceso de fusión.

En el archivo adjunto se encuentra el código que implementa la Mezcla Natural utilizando nombres de personas como datos de los archivos, por lo que las comparaciones que se llevan a cabo a la hora de realizar las particiones y fusiones utilizan el método "compareTo" propio de la clase String.

NOTA: Este código maneja archivos de tipo binario, para probarlo se puede utilizar el archivo de prueba que se encuentra en el post Archivo para probar algoritmos de Ordenamiento Externo.


MezclaNatural.java

Desarrollo de Software dirigido por Pruebas: árboles binarios (Parte 1)

Te encuentras en la primera parte de la serie "Desarrollo de Software dirigido por Pruebas":

1. Diseño de las pruebas
2. Implementación
3. Refactoring
4. Conclusiones y código

El Desarrollo de Software dirigido por Pruebas (Test Driven Development, en inglés) es una técnica que se basa en la elaboración de pruebas para el software previas a la implementación del código. Puede parecer extraño, ya que normalmente estamos acostumbrados a implementar un código y después probar que funcione. Sin embargo, esto tiene sentido ya que antes de la implementación, ya conocemos el funcionamiento del programa y podemos estar seguros de cuál o cuáles son los resultados esperados a la hora de correr dicho programa.

El desarrollo de las pruebas antes del desarrollo del software es muy útil para comprender a profundidad la funcionalidad y el comportamiento del mismo. Realizar test cases utilizando JUnit es muy conveniente ya que a la hora de probar la aplicación, se puede estar seguro de que cumple con el objetivo establecido desde un principio si pasa todas las pruebas y además, es posible realizar cambios con mayor seguridad ya que al correr nuevamente las pruebas, si éstas fallan, se puede tener una muy buena idea de dónde está el error para corregirlo rápidamente. Una vez que las pruebas han pasado satisfactoriamente, aún con la implementación de cambios, es muy probable que dicha aplicación esté desarrollada correctamente. Además, si se desarrollan pruebas de forma creativa, tal y como se explica en el post Prueba Unitaria (Unit Testing) con Netbeans, es muy posible que se estén cubriendo escenarios que quizá no se consideren al realizar las pruebas manualmente.

En esta ocasión, voy a ilustrar el proceso de desarrollo dirigido por pruebas utilizando un conjunto de clases que servirán para implementar árboles binarios. Dos de las operaciones básicas para un árbol binario son la inserción y el borrado de nodos. En esta serie, utilicé valores enteros como el tipo de dato que almacenan los árboles, pero esta información puede ser de cualquier otro tipo.

En este punto, aún no he implementado los cuerpos de los métodos, solamente he creado los esqueletos de las clases, ya que comenzaré por implementar las pruebas. Por ejemplo, para probar el método de inserción (al que llamé insertion), utilizaré los tres recorridos por profundidad de un árbol básicos: recorrido preorden, recorrido inorden y recorrido postorden. Realizaré tres pruebas dentro de las cuales insertaré valores de manera que las estructuras de los árboles sean lo más distintas posibles. Una vez instanciado un objeto árbol, "insertaré" (es decir, haré varias llamadas al método de inserción) ciertos valores, llamaré a los métodos que realizan los recorridos y que devuelven un arreglo con los resultados y los compararé con otro arreglo que contiene esos mismos valores pero que yo ordené de acuerdo con lo que espero obtener de cada recorrido. Un primer caso de prueba para la inserción podría ser insertar los siguientes valores: 10, 6, 7, 5, 4, 11, 13, 12, 15, 3. El árbol binario que se obtiene como resultado es el siguiente:

De acuerdo con esta información, la implementación de esta primera prueba luciría de la siguiente manera:

@Test
    public void insertion01() {
        //Crea una instancia de tipo SimpleBinaryTree para el test
        SimpleBinaryTree simpleTree = new SimpleBinaryTree();

        //Verificar que el arbol esta vacio al inicio
        assertTrue(simpleTree.isEmpty());

        //Insertar elementos al arbol
        simpleTree.insertion(10);
        simpleTree.insertion(6);
        simpleTree.insertion(7);
        simpleTree.insertion(5);
        simpleTree.insertion(4);
        simpleTree.insertion(11);
        simpleTree.insertion(13);
        simpleTree.insertion(12);
        simpleTree.insertion(15);
        simpleTree.insertion(3);

        //Corroborar que todos los datos se hayan insertado
        assertArrayEquals(simpleTree.preOrder(),
                     new int[]{10, 6, 5, 4, 3, 7, 11, 13, 12, 15});
        assertArrayEquals(simpleTree.inOrder(),
                     new int[]{3, 4, 5, 6, 7, 10, 11, 12, 13, 15});
        assertArrayEquals(simpleTree.postOrder(),
                     new int[]{3, 4, 5, 7, 6, 12, 15, 13, 11, 10});
    }

El método de borrado (al que llamé deletion)  se probará de manera muy similar: primero se "insertarán" algunos valores, después se hará una llamada al método de borrado y finalmente se comparará el resultado obtenido de los recorridos contra arreglos que contienen los valores esperados.

El proyecto que estoy utilizando para demostrar el desarrollo de software dirigido por pruebas consta de cinco clases: BinaryTree, TreeNode, SimpleBinaryTree, AVLTree y RedBlackTree. Esta estructura y los resultados de las pruebas se discutirán con mayor detalle en el siguiente post.

Cómo evaluar integrales múltiples utilizando Wolfram Alpha

Wolfram Alpha es una herramienta muy versátil. Además de poder evaluar derivadas e integrales simples, también permite conocer el resultado de integrales múltiples. Solamente hay que acostumbrarse a la notación utilizada para poder introducir una de estas integrales. Por ejemplo, si queremos conocer el resultado de evaluar la siguiente integral en Wolfram Alpha:

Debemos introducirla en el recuadro naranja donde se llevan a cabo las consultas y cálculos de la siguiente manera:

int (z) dz dx dy, z = 0 to sqrt(4 - x - y^2), x=0 to sqrt(1 - y^2), y=0 to 1

Donde "int" representa la operación de integración, el argumento entre paréntesis siguiente al operando int es el integrando (si es que lo hay), seguido por las diferenciales de las variables (en este caso x, y, y z) y finalmente los límites para cada variable comenzando con aquélla cuya diferencial aparezca enseguida del integrando. Los límites para cada variable se separan por comas.

El resultado en la página de Wolfram Alpha luciría de la siguiente manera:

Porción de la página de Wolfram Alpha que contiene la operación realizada

En ocasiones es posible obtener un procedimiento y una gráfica, sin embargo, cuando esto no es posible, aún podemos utilizar Wolfram Alpha para corroborar los resultados obtenidos en nuestros cálculos al aplicar técnicas conocidas de integración. Si das click en el letrero "More digits", Wolfram Alpha te proporcionará varias decenas de los dígitos que corresponden al resultado si es que éste es un número irracional.

Dentro de las funciones que también podemos utilizar se encuentran las trigonométricas (como el seno que se  escribe sin), las exponenciales (únicamente introduciendo la letra "e" seguida del símbolo de exponente y lo que se desea que constituya el exponente para la base e), las logarítmicas (Wolfram Alpha utiliza el símbolo "log" para identificar al logaritmo natural) e inclusive las hiperbólicas (ejemplo: sinh es el seno hiperbólico).

Para poder introducir una integral fácilmente, es posible utilizar como plantillas los ejemplos que ya proporciona Wolfram Alpha, para ello, hay que dirigirse desde la página principal al enlace que dice "Examples by Topic", de ahí a "Mathematics" -> "Calculus" -> "Integrals" y en el apartado de "Multiple Integrals", utiliza la plantilla que más se parezca al ejemplo que deseas evaluar.

¿Qué hacer si Wolfram Alpha no muestra los pasos intermedios para llegar a un resultado?

Ahora bien, en ocasiones Wolfram Alpha no despliega los pasos intermedios que sigue para obtener un resultado. Esto puede deberse a que utiliza técnicas que quizá desde el punto de vista de una computadora son más sencillas (por ejemplo a través de aproximaciones), mientras que nosotros obtenemos el resultado de la operación de manera simbólica (a través de identidades, fórmulas, despejes sencillos).

Sea cual sea el caso, si no existen pasos intermedios, podemos utilizar Wolfram Alpha para verificar el resultado de nuestros cálculos. Independientemente de la técnica que utilicemos o las operaciones intermedias que realicemos para obtener una respuesta, podemos comparar nuestros resultados con los que nos ofrece Wolfram Alpha para verificarlos.

Por ejemplo, podemos descomponer la integral múltiple que se planteó al principio y utilizar Wolfram Alpha para calcular la más interna de la siguiente manera:

int (z) dz, z = 0 to sqrt(4 - x - y^2)

El resultado es el siguiente:

En esta ocasión Wolfram Alpha no muestra los pasos intermedios porque se trata de un caso básico de integracion. Lo que podemos hacer es realizar la integral y verificar que obtengamos el mismo resultado. Una vez que verificamos esta parte, podemos ahora sustituir este resultado para encontrar la integral siguiente en la integral múltiple original:

int (1/2(-x - y^2 + 4)) dx, x=0 to sqrt(1 - y^2)

Para obtener:

Y finalmente, el resultado de esta integral utilizarlo para resolver la última integral con respecto a y:

int (1/4((1 - 2*sqrt(1 - y^2))y^2 + 8*sqrt(1 - y^2) - 1)) dy, y=0 to 1

Y así verificar el resultado final:

De esta manera, si existe alguna duda acerca del resultado de una integral múltiple como esta, puede ser de más ayuda el observar cómo se van resolviendo cada una de las integrales mediante la sustitución del resultado de cada una de ellas desde la más interna hasta la última o más externa.

Cómo utilizar el cambio de ejes para resolver una integral múltiple (ejemplo)

Supongamos que se pide evaluar la siguiente integral:

Tal parece que para esta integral es inútil recurrir a la sustitución simple, la sustitución trigonométrica, las fórmulas de integración contenidas en los formularios más usuales y por supuesto, es virtualmente imposible realizarla de manera directa, así que, ¿Qué podemos hacer para simplificar la tarea de evaluar una integral semejante? La respuesta es muy simple: realizar un cambio de ejes. 

Primero debemos reconocer que al tratarse de una integral doble que posee un integrando, en realidad estamos ante una integral triple, es decir, debemos pensar en tres dimensiones. La gráfica de las curvas en cuestión se obtiene mediante el análisis de la expresión, observándola en términos de las dimensiones x y y, podemos apreciar que y está delimitada por una línea recta en y = 1 y cero y  x está delimitada por la curva "raíz de y" y la recta x = 1. La curva que representa el integrando se levanta sobre el eje z a partir de z = 1. De modo que si nos situamos hipotéticamente sobre el eje z y observamos la base de estas gráficas, este sería el resultado:

Gráfica realizada con ayuda de Wolfram Alpha

La base del volumen que se pretende evaluar por medio de esta integral está marcada en azul. Ahora bien, si observamos la integral tal y como está, nos encontraremos en serios problemas a la hora de encontrar una solución apropiada, sin embargo, podemos invertir el orden en el que están evaluando las variables x y y y obtener como resultado la siguiente expresión:

Ahora, el diferencial de x se evalúa desde cero hasta 1, por lo tanto, para poder obtener la expresión que corresponde a los límites del diferencial de y, es necesario despejar a y. Despejando la raíz de y obtenemos y = x^2, por lo que éste es el nuevo límite aplicable a y.

Esta expresión resulta muy sencilla de evaluar, ya que el integrando se encuentra en términos de x y la variable respecto de la que hay que integrar es y, por lo tanto, el integrando se convierte en una constante y se puede integrar como tal. El resultado es el siguiente:

Prueba Unitaria (Unit Testing) con Netbeans

¿Cómo pruebo mis programas de Estructura de Datos? ¿Existe algo mejor que imprimir resultados en la consola y analizar visualmente si el programa funcionó bien?

Por supuesto, desarrollando pruebas unitarias para tu código aseguras que tu implementación se comporta como esperas y mejor aún, si realizas algún cambio en el código, puedes correr tu prueba nuevamente para validar que todo siga funcionando correctamente. En resumen, una prueba unitaria es código que evalúa partes específicas de otro programa.

Suena como trabajo doble ¿Aparte de mi implementación tengo que hacer otro programa para probarlo?

Realmente no, ya que existen librerías que te ayudan a desarrollar las pruebas rápidamente. Es más, IDE´s como Netbeans incluyen atajos y opciones para generar y ejecutar las pruebas. La siguiente imagen muestra cómo el proyecto por default de Neatbeans ya incluye folders y librerías para desarrollar pruebas.

¿Cómo puedo probar una lista que tiene como tipo de datos enteros e inserta los valores en orden?

Supongamos que los métodos iniciales de la lista son los siguientes:

public class ListaDoble {
   public void insertar(int n){...}
   public NodoDoble remover(int valor){...}
   public boolean isEmpty(){...}
   public static void main(String args[]){...}
}

Primero, borrar el método main, ya que eso está fuera de las responsabilidades de la clase. Vamos hacer dos cambios a la clase:

1. Agregar una variable privada que mantenga el número de elementos en la lista: numElementos. Se incrementará cuando se inserte un elemento y se drecrementará en el método remover.
2. Adicionar un método que nos retorne la lista como un arreglo de enteros. Esta es una posible implementación:
   

       public int[] toArray(){
          int[] array = new int[numElementos];
          int i = 0;
          NodoDoble auxiliar = inicio;
          while (auxiliar != null) {
              array[i] = auxiliar.getDatos();
              auxiliar = auxiliar.getSiguienteNodo();
              i++;
          }
          return array;
      }

Ahora veamos lo rápido y fácil que es agregar una prueba.

1. Da clic derecho en la clase que queremos probar, selecciona la opcion Tools (Herramientas) > Create JUnit Tests
   
2. Aparece un diálogo con opciones para crear la clase que ejecutará las pruebas. Para esta prueba seleccioné lo mínimo, como puedes ver en la figura.
   
3. Borra el método por default que genera Netbeans y agrega el siguiente método.

       @Test
      public void testEscenario01() {
          ListaDoble lista = new ListaDoble();
          // La lista debe estar vacia al inicio
          assertTrue(lista.isEmpty());
   
          // Insertemos 5 elementos
          lista.insertar(100);
          lista.insertar(50);
          lista.insertar(200);
          lista.insertar(-50);
          lista.insertar(0);
          assertArrayEquals(lista.toArray(),
                  new int[]{-50,0,50,100,200});
      }

   Como puedes ver, este método crea una instancia de ListaDoble. Los métodos assert son parte de la librería JUnit, y sirven para verificar si cierta condición se cumple. Por ejemplo, recién creada la lista, se espera que esté vacía, esto lo logramos con assertTrue(lista.isEmpty()). Después insertamos 5 elementos y verificamos con assertArrayEquals que el contenido de la lista sea igual al arreglo que pasamos como segundo parámetro. Nota que el segundo arreglo está ordenado, ya que es lo que esperamos de la lista.
4. Para ejecutar la prueba, simplemente da clic derecho en el archivo de prueba (en este caso ListaDobleTest) y selecciona Test File
   
   Si tu implementación es correcta, aparecerá un mensaje como el siguiente.
   
   Para la siguiente imagen, introduje un error en la prueba para ver la salida de JUnit.
   

NOTA

Esto nos lleva a reflexionar, que pueden existir errores tanto en la implementación como en la prueba. Pero es importante notar que sin pruebas confiamos ciegamente en la implementación. Si hay un error al correr las pruebas, el error puede estar en la implementación o en las pruebas. Si las pruebas corrieron exitosamente, entonces la implementación cumple con los casos presentados en las pruebas; en otras palabras, puede que tanto la implementación como las pruebas estén mal. Obviamente, es más difícil equivocarse en dos lugares (implementación y pruebas) que sólo en uno (implementación).

También es importante mencionar que las pruebas sólo garantizan que nuestro programa cumple con los escenarios mencionados, más no que está 100% libre de errores.

¿Con una sola prueba basta para la clase ListaDoble?

El objetivo no es crear tantas pruebas como sea posible. Más bien, es crear el mínimo número de pruebas que cubran el mayor número de casos o escenarios de nuestra implementación. Por ejemplo, supongamos que en la prueba uno insertamos 20,19, 18, 17, 16 y en la prueba dos insertamos 10,9,8,7,6. Realmente, en las dos pruebas estamos insertando elementos en orden descendente; es decir, las dos cubren el mismo escenario (son redundantes).

Con esto en mente, recomiendo crear escenarios que se complementen. Para el caso de la inserción en la lista doble: 1) insertar elementos en order ascendente, 2) insertar elementos en orden descendente, 3) insertar elementos tal que un elemento se inserte al inicio de la lista, el siguiente elemento al final de lista, y otro elemento en un punto medio de la lista y así sucesivamente, 4) insertar sólo elementos iguales.

Observa que estos casos son para la inserción, casos similares deben ser creados para el borrado. Y por último recomendaría un conjunto de casos que mezclaran operaciones de inserción y borrado.

Veo que al comparar la lista en forma de arreglo usamos un arreglo que nosotros calculamos new int[]{-50,0,50,100,200}, ¿cómo difiere esto de imprimirlo en la consola e inspeccionarlo visualmente?

Quizá las primeras dos o tres veces de inspeccionar el resultado visualmente resulte práctico, pero después de un buen rato de estar desarrollando verás que resulta demasiado tedioso y propenso a errores. Imagina que tienes una lista de 100 números, no suena muy divertido inspeccionar visualmente los 100 números cada vez que realices un cambio a la lista.

Además, como menciono en el punto anterior, es necesario probar varios escenarios. Si creas tus pruebas unitarias, entonces cada vez que las ejecutes estarás evaluando todos los escenarios en un abrir y cerrar de ojos. Esto te ayuda a tener más confianza al realizar cambios o mejoras en tu implementación, ya que puedes ir probando continuamente para validar si algo deja de funcionar o si algo ya está funcionando.

Fundamentos de Bases de Datos: Bases de Datos Orientadas a Objetos (apuntes)

He aquí una breve introducción a las Bases de Datos Orientadas a Objetos para el curso de Fundamentos de Bases de Datos del Instituto Tecnológico de Toluca. La práctica la pueden descargar en el link que se encuentra al final de la misma.

A las Bases de Datos Orientadas a Objetos también se les conoce como Sistemas de Manejo de Bases de Datos de Objetos (ODBMS, por sus siglas en inglés: Object Database Management Systems). Este tipo de bases de datos almacenan objetos en lugar de datos como enteros, cadenas o números reales. Los objetos ss utilizan en lenguajes de programación orientados a objetos tales como C++, Java y otros. Los objetos consisten básicamente en lo siguiente:

• Atributos. Es la información que define las características de un objeto. Puede ser de tipo simple como por ejemplo enteros, booleanos o caracteres o puede hacer referencia a otros objetos.
• Métodos. Los métodos definen el comportamiento de un objeto, son el equivalente a lo que se conoce como funciones o procedimientos en C, por ejemplo.

Otro término que vale la pena considerar es el de Clases. Las clases se utilizan en lenguajes de programación orientados a objetos para definir los datos y los métodos (características y comportamientos) que los objetos posean. Una clase es como una plantilla para crear un objeto y es usada para crear (instanciar) el objeto. Las clases pueden ser empleadas en bases de datos orientadas a objetos para re-crear partes de un objeto que puedan no estar almacenadas dentro de la base de datos como por ejemplo, los métodos.

Existen ventajas y desventajas de las Bases de Datos Orientadas a Objetos sobre las Bases de Datos de tipo Relacional, entre las ventajas cabe mencionar el hecho de que la navegación a través de la información en las primeras es más fácil que en las segundas, además de que el modelo de datos en las Orientadas a Objetos está basado y se ajusta mejor al mundo real. Entre las desventajas de las Orientadas a Objetos se encuentran la existencia de más herramientas para las Relacionales, la mayor estabilidad de los estándares de las Relacionales y una eficiencia más baja cuando se presentan datos y relaciones simples.

Fuente:
Object Oriented Databases
http://www.comptechdoc.org/independent/database/basicdb/dataobject.html 


DESCARGA LOS APUNTES DE LA PRÁCTICA DE LA CLASE AQUÍ!!!