viernes, 31 de diciembre de 2010

Ordenamiento externo: Mezcla Natural (Natural Merge Sort)

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

39 comentarios:

  1. lo baje, lo probe y funcionó perfectamente...

    Felicidades...

    Voy a tratar de entender el codigo, de hecho, tengo la duda de la secuencia 4 como se fusionó sin el proceso de fusión propiamente.

    ResponderEliminar
  2. Ya vi el codigo y me queda bastante claro...
    Felicidades de nuevo...

    Que diferencia hay entre este metodo ( ordenamiento por mezcla natural ) contra el metodo de ordenamiento por mezcla????

    ResponderEliminar
  3. Hola,

    Gracias por los comentarios. Con respecto a tu pregunta:

    1. En el ordenamiento por mezcla natural las secuencias iniciales se forman con grupos de elementos en orden creciente, por ejemplo [10,17],[5,8,9],[3,22,50].

    2. En el ordenamiento por mezcla (directa) las secuencias iniciales son de tamaño 1 (por ejemplo [10],[17],[5],[8],[9],[3],[22],[50])y después de la primera mezcla, las nuevas secuencias serán de tamaño 2. Su tamaño se duplica con cada mezcla hasta que se forma una secuencia ordenada.

    Como puedes ver el procedimiento de ordenamiento es el mismo, lo único que cambia es la manera en que formas las secuencias iniciales.

    Saludos.

    ResponderEliminar
  4. Gracias por tu respuesta mariana, eres muy amable....

    Voy a modificar el algoritmo de mezcla natural para generar secuencias de tamaño 1,2, 4,8, etc... con la misma lógica y te comento....
    Saludos....

    ResponderEliminar
  5. Mariana, codifique otro algoritmo para mezcla batural y creo que me funciono...
    Quisiera subirlo para que le eches un vistazo pero no se como hacerlo...
    Si me puedes decir te lo agradeceré...
    Saludos....

    ResponderEliminar
  6. Hola gracias por el aporte solo tenia un par de dudas , donde debe estar el archivo para que el programa lo encuentre en la pc ? ya que siempre me da error y el segundo seria si este programa me podria servir para cuando tengo un medicamento con codigo , nombre y otros campos y quisiera tomar el campo codigo como clave... de antemanos muchas gracias..

    ResponderEliminar
  7. Hola seiryu,

    Ya que los programas no usan paquetes, en el mismo directorio donde los compilas y ejecutas, puedes copiar el archivo. Y al ejecutar el programa simplemente poner el nombre del archivo (muchosNombres.txt).

    El programa que desarrolló Mariana está enfocado en un archivo que contiene cadenas en formato UTF (http://docs.oracle.com/javase/1.5.0/docs/api/java/io/DataOutputStream.html#writeUTF%28java.lang.String%29), eso lo podemos observar en el uso de writeUTF y readUTF.

    La lógica del algoritmo de mezcla natural (métodos de partición y fusión) se puede reusar completamente. Pero debes modificar la forma de leer y escribir los datos de los archivos.

    Lo que recomiendo es usar una clase que represente tu medicamento (clave, nombre, precio, ...), esta clase la debes hacer serializable, para que la puedas leer y escribir a archivos. La siguiente página muestra un muy buen tip para realizar esto (http://www.java-forums.org/advanced-java/39706-serialization-deserialization-multiple-objects-single-file.html). Además, tu clase medicamento debe implementar la interface Comparable, para que puedas comparar medicamentos usando el método compareTo y de esta forma se puedan ordenar.

    También es recomendable que pongas los métodos crearArchivoDatos y desplegar en otra clase, ya que estos se van a encargar de pedir y desplegar los datos específicos de tu clase medicamento.

    Saludos.

    ResponderEliminar
  8. Hola Astolfo,

    Puedes subir tu código a un repositorio en la nube como Dropbox (que es gratuito). Si no tienes Dropbox, puedes adquirirlo en esta liga:

    http://db.tt/DPdeSSc

    Una vez que lo descargues e instales, abre tu fólder raíz de Dropbox, copia tu archivo *.java en el fólder Public (o Público). Después, da clic derecho al archivo dentro del fólder público -> selecciona Dropbox -> Copiar enlace (o liga o link) público y pega esta dirección en un comentario dentro de este post para que todos podamos descargar el archivo con tu código y aprender de él.

    Muchas gracias por tus aportaciones y saludos.

    ResponderEliminar
  9. hola gracias antonio me fue de utilidad tus consejos y he logrado hacerlo funcionar y logre leer el archivo crear copias del mismo y ordenarlo , pero aun no consigo leer un archivo que posea digamos por ejemplo

    01215 televisor 22.01 5% 3 45 Panasonic

    ya que no se como seria la manera correcta de leer un archivo que contenga datos asi y que me los ordenara en base al codigo se que se podria hacer con una tabla hash pero aun no consigo hacerlo..

    ResponderEliminar
  10. Descarga el codigo: http://dl.dropbox.com/u/51358943/Ap_mezcla_directa.java

    ResponderEliminar
  11. Descarga el codigo ( 2da parte ):
    http://dl.dropbox.com/u/51358943/MezclaDirecta.java

    ResponderEliminar
  12. Mariana:
    Seguí tus indicaciones y ya los subí al DropBox; Lo probe y funcionó perfectamente.
    Solo me queda una pregunta: Porque, en mi caso, tengo que copiar el enlace al navegador y en cambio contigo la descarga se hace desde aqui???
    Muchas gracias por tus indicaciones, eres muy amable...Saludos.

    ResponderEliminar
  13. Hola seiryu,

    Acabo de publicar un post que te puede ayudar con tu duda:

    Ordenar usando la interface Comparable

    Te recomiendo también leer la documentación de esa interface.

    Saludos.

    ResponderEliminar
  14. Respuestas
    1. Hola BEN,

      De acuerdo a las siguientes dos páginas, John von Neumann inventó ordedamiento por mezcla (algorithmist, wikipedia). En particular la variante de mezcla natural al parecer fue descrita por Donald E. Knuth en The art of computer programming, volume 3: (2nd ed.) sorting and searching.

      Saludos.

      Eliminar
  15. Hey Mariana!! mil gracias!! excelente trabajo, me has salvado jeje ;)

    ResponderEliminar
  16. hola mi duda comienza en... no importa como se divida Origen: [10,17],[5,8,9],[3,22,50],[4],[2,20,30],[11,16,19],[6,21,23] o tiene que haber un orden?? :S gracias :D

    ResponderEliminar
    Respuestas
    1. Hola, el método de mezcla natural aprovecha las secuencias ya ordenadas en el archivo origen. Pero no es necesario que el archivo origen tenga un orden en específico. Por ejemplo, el archivo de entrada podría estar en orden descendente ([10],[9],[8],[7],[6],[5],[4],[3],[2],[1]). En este caso todas las secuencias iniciales son de tamaño uno. Saludos.

      Eliminar
  17. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
  18. una pregunta descargue el programa pero al momento de ejecutarlo m pide nombre del archivo: que tengo k hacer para k m rekonozka el archivo muchosNombres.txt

    ResponderEliminar
  19. Hola Alvin, la respuesta la puedes encontrar arriba en el comentario de Antonio del 26 de noviembre de 2011. Gracias y saludos.

    ResponderEliminar
  20. ya tengo el codigo y corre pero ala ora de introducir el nombre me dice errror
    de lectura/escritura quisiera sabeer xq me pasa eso

    ResponderEliminar
    Respuestas
    1. Hola,
      Es muy posible que el archivo (muchosNombres.txt) no lo hayas copiado al mismo directorio donde compilas y ejecutas los archivos del programa. Echale un vistazo al comentario de Antonio del 26 de Noviembre de 2011.
      Gracias por el comentario y saludos.

      Eliminar
  21. Hola buenas noches amigos, ando en busca de este método de ordenamiento pero un poco... mas para principiantes, es mi segundo semestre y aun no entiendo mucho del codigo que publicas, si alguien me lo pudiera compartir en un código mas básico se lo agradeceria mucho. :)

    ResponderEliminar
  22. Hola amigos, gracias por el código Mariana ... me podrían decir cual método es más rápido? ... el de mezcla directa o el de mezcla natural?

    ResponderEliminar
    Respuestas
    1. Hola, si los datos son completamente aleatorios, los dos tienen desempeño similar. Si los datos tienen cierto orden, mezcla natural toma ventaja de ello y se ejecutara ligeramente mas rapido. Saludos.

      Eliminar
  23. y como seria este mismo código pero para grandes números enteros?

    ResponderEliminar
    Respuestas
    1. Hola, este codigo lee cadenas en formato binario desde los dos archivos de entrada. Si quieres seguir leyendo de archivos, tendrias que crear archivos de prueba serializando datos de tipo BigInteger. Y despues tendrias que modificar el codigo de MezclaNatural.java para de-serializar los datos, al parecer DataInputStream no tiene metodos para leer BigIntegers, probablemente necesites usar ObjectInputStream. Saludos.

      Eliminar
  24. Hola donde puedo conseguir el link del codigo, intente con el que esta publicado pero ya no lo contiene

    ResponderEliminar
    Respuestas
    1. Muchas gracias por reportarlo, el codigo esta nuevamente disponible.

      Eliminar
  25. una pregunta amigos para que se ocupa este método de ordenamiento?

    ResponderEliminar
    Respuestas
    1. Esta página de Wikipedia tiene una muy buena explicación:
      https://es.wikipedia.org/wiki/Ordenamiento_externo

      Muchas gracias por preguntar, esto me ayudo a descubrir que este algoritmo también se conoce como mezcla equilibrada.
      https://es.wikipedia.org/wiki/Ordenamiento_por_mezcla_equilibrada

      Eliminar
  26. cual es el nombre del archivo para poder probar el programa

    ResponderEliminar
    Respuestas
    1. Sigue el link al final del post ("Archivo para probar algoritmos de Ordenamiento Externo"), justo antes del codigo. Ahi encontraras el link al archivo de prueba: nombres.bin

      Eliminar
  27. Hola, alguien me puede ayudar con el codigo? Ya descargué el archivo nombres.bin y cambie la extensión a txt, pero no encuentro el archivo del codigo para poder probarlo

    ResponderEliminar
    Respuestas
    1. Hola, gracias por reportarlo, ya actualice el enlace al codigo al final del articulo: MezclaNatural.java.

      Eliminar