domingo, 10 de marzo de 2019

Ordenamiento mezcla natural: objetos

Como ejemplo final en esta serie, veremos cómo ordenar un objeto que nosotros definimos. Vamos usar un objeto Persona que tiene nombre y edad. El único requisito para poder ordenarlo es que podamos compararlo. Esto lo logramos implementando el método compareTo() de la interface Comparable, nuestra implementación ordenará primero por edad y luego por nombre.

Las implementaciones de Lector y Escritor son exactamente iguales a las del ejemplo anterior en donde ordenamos enteros grandes.

Para crear nuestro archivo de prueba, leemos nuestro archivo de texto con nombres y a cada nombre le asignamos una edad para crear un objeto Persona. Noten que la clase Persona también implementa la interface Serializable. Esta interface no requiere que implementemos ningún método y nos permite serializar el objeto para escribirlo y leerlo de archivos.

Espero que los ejemplos en esta serie sirvan como base por si desean ordenar otro tipo de datos.

$ javac MezclaNaturalGenerico.java MezclaNaturalEjemplo4.java
$ java MezclaNaturalEjemplo4
Error en el ordenamiento
Fusion 1
Fusion 2
...
EL ARCHIVO ESTA ORDENADO
MezclaNaturalEjemplo4.java

domingo, 3 de marzo de 2019

Ordenamiento mezcla natural: enteros grandes

Ahora veremos como ordenar enteros grandes con el algoritmo genérico de mezcla natural. Este ejemplo es muy parecido al primer ejemplo donde ordenamos cadenas binaria. Pero en lugar de usar Data[Input|Ouput]Stream ahora usamos Object[Input|Output]Stream. Esto nos permite leer y escribir objetos serializados en lugar de sólo datos primitivos.

La principal diferencia, que me tomó por sorpresa, es que el método available() no regresa 0 para indicar fin del archivo. En este caso, tenemos que capturar EOFException para detectar cuando acabamos de leer los datos.

El programa crea y ordena un archivo con 100,000 enteros.

$ javac MezclaNaturalGenerico.java MezclaNaturalEjemplo3.java
$ java MezclaNaturalEjemplo3
Error en el ordenamiento
Fusion 1
Fusion 2
...
EL ARCHIVO ESTA ORDENADO
MezclaNaturalEjemplo3.java

sábado, 2 de marzo de 2019

Ordenamiento mezcla natural: cadenas

La versión original de este algoritmo ordena cadena binarias porque fue un requerimiento del proyecto. Pero ahora que ya tenemos la versión genérica, podemos ordenar otros datos. Empecemos por ordenar cadena simples (no binarias). Nuestro archivo de entrada tiene un nombre por línea.

Noten que en el Lector tenemos que obtener la línea por adelantado para poder implementar adecuadamente hasNext().

Después de ejecutar el ejemplo, pueden corroborar el resultado abriendo el archivo nombres_copia.txt.

$ javac MezclaNaturalGenerico.java MezclaNaturalEjemplo2.java
$java MezclaNaturalEjemplo2
MezclaNaturalEjemplo2.java

domingo, 24 de febrero de 2019

Ordenamiento mezcla natural: cadenas binarias

Ahora veremos cómo usar el algoritmo genérico de mezcla natural con cadenas binarias. Tenemos que implementar las dos interfaces que permiten aislar los detalles de lectura y escritura de datos.

  public static class Lector implements MezclaNaturalGenerico.Lector<String> 
  public static class Escritor implements MezclaNaturalGenerico.Escritor<String>

La implementación de estas dos interfaces es bastante directa. Por ejemplo, el método next() ecapsula readUTF() y el método hasNext() encapsula dis.available() != 0. También comentaba que el algoritmo se inicializa con fábricas para generar Lectores y Escritores. Eso lo podemos ver en esta línea:

  new MezclaNaturalGenerico<>(Lector::new, Escritor::new);

Vale la pena explicar qué está pasando aquí. La forma extendida sería implementar la interface que está esperando el constructor.

  static class FabricaLectores implements
      Function<File, MezclaNaturalGenerico.Lector<String>> {
    @Override
    public MezclaNaturalGenerico.Lector apply(Object o) {
      return new Lector(o);
    }
  }

Y la usamos así:

  new MezclaNaturalGenerico<>(new FabricaLectores(), ...);

La parte principal de FabricaLectores es new Lector(o), lo demás sólo causa ruido. Dado que Function es una interface funcional, es decir, que sólo tiene un método abstracto, la podemos reemplazar con una lambda.

  new MezclaNaturalGenerico<>(o -> new Lector(o), ...)

Pero como la única instrucción de la lambda es un new, la podemos reemplazar por una referencia al constructor. Y así es cómo llegamos al resultado final.

new MezclaNaturalGenerico<>(Lector::new, ...);

Al ejecutar este ejemplo deben obtener lo siguiente:

$ javac MezclaNaturalGenerico.java MezclaNaturalEjemplo1.java
$ java MezclaNaturalEjemplo1
Error en el ordenamiento
Fusion 1
...
EL ARCHIVO ESTA ORDENADO
1) AARON
2) ABBEY
3) ABBIE
4) ABBY
5) ABDUL
...
MezclaNaturalEjemplo1.java

lunes, 18 de febrero de 2019

Ordenamiento mezcla natural: algoritmo genérico

Esta serie de posts está inspirado en uno de nuestros posts más populares: Ordenamiento externo: Mezcla Natural. En ese post recibimos algunas preguntas de cómo reusar el código para ordenar otro tipo de datos. El código original sólo maneja cadenas en formato binario. Por lo que decidí actualizarlo para manejar cualquier tipo de dato. En este post hablaré de los cambios necesarios y en los siguientes posts mostraré ejemplos de cómo usarlo. El algoritmo base no cambió, lo que tuve que aislar es el tipo de dato y la forma en la que lo leemos y escribimos.

Tipo de dato.

El tipo de dato lo podemos ver por las menciones del tipo String a lo largo del código original. Tenemos que reemplazar String con un tipo genérico. La única operación que necesitamos del tipo de dato es que lo podamos comparar. Eso lo podemos observar cuando invocamos el método compareTo. Esto nos lleva a cambiar la definición de la clase de:

public class MezclaNatural

a:

public class MezclaNaturalGenerico<T extends Comparable<T>>

Noten que exigimos que el tipo de datos genérico implemente la interface Comparable, la cual declara el método compareTo. Ahora podemos reemplazar String con el parámetro genérico. Por ejemplo:

    String actual = null;
    String anterior = null;

con:

    T actual = null;
    T anterior = null;

Lectura de datos.

Para leer datos estábamos usando los métodos available() y readUTF() de un DataInputStream. Además invocamos el método close() de este Stream cuando terminamos de usarlo. Vamos a reemplazar este DataInputStream con una interface que provea una funcionalidad similar. En lugar de crear una interface completamente nueva, decidí crear una interface que extiende dos interfaces de las librerías de Java:

  public interface Lector<T> extends Iterator<T>, Closeable { }

Un usuario tiene que implementar esta interface para que nuestro algoritmo no se preocupe de cómo leer datos. Observen cómo volvemos a usar el parámetro genérico en esta definición. Los métodos hasNext() y next() de la interface Iterator reemplazarán a los métodos available() y readUTF().

Un pequeño detalle de implementación es que nuestro algoritmo tiene que instanciar varios Lector(es) a lo largo de su ejecución. Por lo que un usuario debe proporcionar una fábrica de Lectores. Esto lo podemos ver en el siguiente parámetro de nuestro constructor:

    Function<File, Lector<T>> generaLector

La fábrica (Function) tomará como entrada un archivo abstracto e instanciará un Lector.

Escritura de datos.

Este caso es paralelo a la lectura de datos. Para escribir usamos el método writeUTF() de un DataOutputStream. Esto la abstraemos con la interface:

  public interface Escritor<T> extends Consumer<T>, Closeable { }

El método accept() de Consumer reemplazará al método writeUTF(). Y también necesitamos una fábrica de Escritores.

    Function<File, Escritor<T>> generaEscritor

Esto es todo por este post. Si lo comparan con el código original, verán que la lógica es la misma y la mayoría fueron reemplazos directos (por ejemplo: readUTF con next) En el siguiente post veremos cómo usarlo.

MezclaNaturalGenerico.java

miércoles, 30 de enero de 2019

Condiciones en Makefiles

De vez en cuando me toca lidiar con Makefiles. La mayoría de las veces, tengo que tomar tips de varias fuentes para poder completar un solo comando. En este post, me gustaría compartirles una de esas ocasiones. Mi objetivo era ejecutar condicionalmente comandos basado en la versión instalada de Java. Les muestro primero el resultado final.

prueba_java:
ifneq (,$(findstring build 1.8, $(shell java -version 2>&1)))
 @echo "Java 8"
else
 @echo "No Java 8"
endif

El comando java -version retorna algo similar a esto:

openjdk version "1.8.0_191"
OpenJDK Runtime Environment (build 1.8.0_191-8u191-b12-0ubuntu0.16.04.1-b12)
OpenJDK 64-Bit Server VM (build 25.191-b12, mixed mode)

Noten el uso de “2>&1”. El comando anterior no imprime la versión a stdout sino a stderr. Por lo que tengo que redireccionar stderr a stdout.

El siguiente paso es buscar la cadena build 1.8 en el resultado de java -version usando la función findstring. Noten que el primer argumento no lleva comillas. Aquí aprendí que las comillas son necesarias sólo si el comando que se ejecutará en la terminal las necesita. Como es el caso del comando echo. Pero en esta situación, findstring es un comando que make ejecutar directamente, y los comandos nativos de make no necesitan comillas.

Por último, comparamos el resultado de findstring con la cadena vacía. El comando findstring retorna build 1.8 si encuentra la cadena en el segundo argumento o una cadena vacía en caso contrario. Noten nuevamente la forma en la que representamos la cadena vacía al no dejar espacio entre el primer paréntesis y la coma.

Les dejo un enlace a un sitio con muy buenos ejemplos. Una vez estaba tratando de entender algo similar a las siguientes lineas:

foo := a.o b.o c.o
bar := $(foo:%.o=%)

Y no sabía ni cómo buscar. Navegando por este tutorial encontré este ejemplo que era muy parecido al código que estaba analizando, y eso me dio la pista de que esto es equivalente al comando patsubst

domingo, 27 de enero de 2019

Java classpath y jar

Recientemente me topé con la forma en la cual las opciones classpath y jar interactúan. Usemos un ejemplo muy sencillo para ilustarlo.

Supongamos que queremos usar una clase que viene en un jar. Por ejemplo:

public class MiClase {
  public static String saludo() {
    return "Saludos de MiClase";
  }
}

Podemos construir un jar de la siguiente manera.

javac MiClase.java
jar cf MiClase.jar MiClase.class

Ahora usemos este jar desde otra clase.

public class Inicio {
  public static void main(String[] args) {
    System.out.println(MiClase.saludo());
  }
}

Si sólo queremos ejecutar esta clase.

javac -cp MiClase.jar Inicio.java
java -cp .:MiClase.jar Inicio

Qué pasa si también queremos crear un jar de esta clase.

jar cfe Inicio.jar Inicio Inicio.class

Noten que el parámetro Inicio indica el punto de entrada a nuestra aplicación. Este fue mi primer intento para ejecutar el programa.

java -cp MiClase.jar -jar Inicio.jar

El cual me generó este error:

Exception in thread "main" java.lang.NoClassDefFoundError: MiClase

Resulta que la opción jar funciona con jars que contienen todas sus dependencias, también les llaman jar ejecutables. La solución es poner los jars en el classpath e indicar el punto de entrada.

java -cp MiClase.jar:Inicio.jar Inicio

domingo, 15 de mayo de 2016

C++ unique_ptr

En esta nueva serie de C++, voy a cubrir algunos tópicos que me han resultado útiles en el último año. Los primeros artículos serán acerca de la creación de objetos y manejo de memoria. Uno de las principales mejoras en C++11 son unique_ptr's y shared_ptr's para facilitar el manejo de memoria. Para los ejemplos que estaré presentando, creé la clase MiClase, que imprime mensajes para ayudar a visualizar que partes de la clase son invocadas. Nuestro primer ejemplo muestra como un unique_ptr se encarga de llamar el destructor, a diferencia de un apuntador normal, donde tenemos que recordar llamar a delete para evitar posibles fugas de memoria.

domingo, 25 de octubre de 2015

Cómo aprender a resolver problemas en programación: Recomendaciones

  1. Introducción
  2. Recomendaciones

¿Cómo podemos empezar a aprender a resolver problemas de programación? En este post me gustaría analizar algunas de las estrategias propuestas en el capítulo 1 del libro Think Like a Programmer. An Introduction to Creative Problem Solving y cómo cada una de estas estrategias sí me han ayudado a mejorar mi habilidad para resolver problemas de programación.

Antes de intentar escribir código para cualquier problema de programación, es importante saber que existen algunas recomendaciones para ordenar nuestros pensamientos y posteriormente poner manos a la obra. Si organizamos nuestro entendimiento de lo que el problema está pidiendo, es mucho más fácil llegar a una primera solución, y aunque ésta sea una solución parcial o muy rudimentaria, es crucial entender que este es un muy buen primer paso y que con práctica, podremos ser capaces de saltarnos algunos pasos intermedios. Pero por ahora, lo más esencial es detenernos un poco y analizar qué se está pidiendo.

Algunas recomendaciones que he encontrado muy útiles en este primer paso de analizar un problema son las siguientes:

  1. Dividir el problema: Algunos problemas contienen muchos pasos o bien, es necesario hacer diferentes operaciones para encontrar la solución. Una buena estrategia es leer el problema más de una vez para poder identificar las diferentes partes en las que puede estar dividido. Dividir un problema nos permite hacer varias operaciones sencillas que combinadas, realizan una tarea compleja. Por ejemplo, supongamos que queremos contar el número de veces que un grupo de palabras aparece en un archivo de texto. Este problema lo podemos dividir en: leer el archivo, tokenizar el texto que contiene el archivo (es decir, desarrollar código que sea capaz de separar el texto del archivo en palabras individuales), leer palabra por palabra el texto del archivo, identificar si alguna palabra pertenece al grupo de palabras que queremos contar, llevar la cuenta de cuando una palabra de nuestro grupo aparece en el texto del archivo, repetir la cuenta para cada palabra de nuestro grupo de palabras y retornar nuestro resultado utilizando alguna estructura de datos. Si nos enfocamos en uno solo de estos pasos a la vez, resolver este problema es mucho más sencillo.
  2. Identificar las partes del problema que se nos hacen fáciles de resolver: Es posible que cuando estamos resolviendo un problema, existan ciertas partes que nos parecen más sencillas de resolver o con las que tenemos más experiencia. Esto es parecido a cuando resolvemos un examen: algunas preguntas son más sencillas que otras. En el libro Abre tu mente a los números: Cómo sobresalir en Ciencias aunque seas de Letras, aprendí que existe más de una manera de atacar las partes fáciles y difíciles de algo que queremos resolver. Volviendo al ejemplo del examen, algunas personas se sienten cómodas atacando las preguntas fáciles primero y dejando las difíciles para después. Pero otra estrategia que puede resultar exitosa de acuerdo con la autora es la siguiente: atacar lo más difícil primero y en cuanto comencemos a notar que estamos atorados, dirigir nuestra atención hacia preguntas o pasos fáciles y volver al problema difícil una vez que hayamos resuelto los fáciles. La idea detrás de esta técnica es que nuestro cerebro funciona en dos modos: en el primero se enfoca intensamente en una tarea y en el segundo procesa información de manera difusa (es decir, sin enfocarse particularmente en una idea). El modo difuso nos ayuda a seguir resolviendo el problema difícil mientras estamos resolviendo los problemas fáciles y es gracias a este modo de "pensar" que muchas veces recordamos información súbitamente o nos damos cuenta repentinamente de algún error que estábamos cometiendo.
  3. Reconocer o tratar de hacer analogías del problema a resolver: Con el paso del tiempo y con experiencia, reconocer problemas parecidos y recordar cómo los resolvimos se convierte en algo muy natural. En nuestro camino a adquirir esa experiencia es importante que podamos identificar si un problema se parece a algún otro o si podemos hacer alguna analogía. Las analogías nos ayudan a entender mejor el problema y en ocasiones nos pueden auxiliar a visualizarlo mejor. Una buena analogía es un excelente recurso que en un futuro cercano nos permite recordar más fácilmente aquéllo que aprendemos. Por ejemplo, en el problema de contar cuántas veces un grupo de palabras aparece en el texto de un archivo podemos visualizar una línea de producción en donde las palabras pasan frente a nosotros y nosotros tenemos que colocarlas en sus cajas correspondientes. Cada vez que clasificamos una de las palabras en las que estamos interesados, utilizamos un marcador para anotar cuántas palabras hay hasta el momento en cada caja tachando el valor anterior y escribiendo el nuevo valor que se incrementa en 1 unidad.
  4. Experimentar: El autor de Think Like a Programmer. An Introduction to Creative Problem Solving, deja muy claro que experimentar no significa solamente tomar piezas de código y comenzar a ver si alguna funciona de manera aleatoria. Experimentar se refiere a tratar de utilizar nuevo código de forma que parezca lógica y de acuerdo con nuestra (poca o mucha) experiencia. Supongamos que estamos tratando de generar algún tipo de gráfico y sabemos que existe una librería que puede contener la funcionalidad que estamos buscando. Para confirmar si podemos utilizar alguna función de la librería, podemos leer la documentación y hacer ejemplos simples para observar qué es lo que pasa. Si el resultado de estos experimentos es lo que nosotros necesitamos, entonces podemos utilizar esta librería para resolver nuestro problema de generar algún gráfico. Incluso en circunstancias en las que no necesitamos utilizar ninguna librería (como cuando estamos aprendiendo a utilizar un lenguaje de programación), experimentar haciendo pequeños ejemplos y observando el resultado es algo muy valioso que nos ayuda a entender realmente qué está pasando.
  5. Reducir la complejidad del problema: Imaginemos que estamos tratando de construir un programa para jugar al "gato" o "tic-tac-toe" en 3 dimensiones. Para poder resolverlo, es necesario que podamos manipular un arreglo en 3 dimensiones, sin embargo, quizá para familiarizarnos mejor con la forma de resolver este problema, es mejor enfocarnos en cómo resolveríamos el clásico juego en 2 dimensiones y posteriormente extender nuestra solución para tomar en cuenta un arreglo de 3 dimensiones.
  6. Evitar frustrarte: Esta es quizá solamente una recomendación, pero no por eso deja de ser valioso recordar que debemos respirar profundamente y no rendirnos. Si de verdad estás atorado resolviendo un problema, pide ayuda a alguien con más experiencia pero no te desesperes ni pienses que la programación no es para ti. Es muy válido pedir ayuda e incluso, es muy importante saber cuándo pedir ayuda y a quién.

Si bien estas no son las únicas estrategias para comenzar a resolver un problema, son las que más me han parecido útiles en mi camino a mejorar la manera en la que ataco los problemas de programación. Sin embargo, ninguna técnica puede reemplazar el hacer ejercicios. Es por esta razón que al terminar de leer este post, lo primero que debes hacer es resolver varios ejercicios. En el libro Think Like a Programmer el autor recomienda utilizar acertijos para practicar las recomendaciones que acabamos de analizar brevemente.

Las siguientes ligas contienen acertijos en español de varios tipos que pueden ayudarte a comenzar a utilizar estas estrategias. Trata de resolver aquéllos que no conozcas utilizando distintas formas de atacar el problema. Mientras más intentes, mejor:

http://www.parapensar.com/acertijos.html

http://www.elconfidencial.com/alma-corazon-vida/2014-07-28/10-acertijos-clasicos-que-pondran-a-prueba-tu-capacidad-logica_166413/

Si conoces otros sitios que contienen buenos acertijos, compártelos en los comentarios.

domingo, 11 de octubre de 2015

Cómo sincronizar Blogger y una página de Facebook automáticamente

Hasta hace poco tiempo, había estado usando RSS graffiti para publicar autómaticamente en la página de Facebook de este blog un resumen de cualquier post nuevo aquí en Blogger. Esta herramienta era muy conveniente y durante muchos meses nunca tuve que preocuparme por la sincronización entre este blog y su página de Facebook. Sin embargo, RSS graffiti dejó de funcionar en Abril de este año (2015) y sin darme cuenta, los posts que creé después de Abril nunca aparecieron en la página de Facebook.
Ahora bien, la búsqueda de otra herramienta parecida a RSS graffiti me llevó a conocer otro sitio que parece ser bastante útil: If This Then That (IFTTT). En este sitio es posible crear "recetas" que conectan diferentes aplicaciones para hacer prácticamente todo tipo de tareas. En este post me gustaría explicar paso a paso cómo es que usé IFTTT para sincronizar nuevamente este blog con su página en Facebook.
Los siguientes pasos están basados en la explicación que aparece en el blog Technology And Life:
  1. Si no lo has hecho, abre la página de IFTTT dando click aquí
  2. Regístrate haciendo click en el botón de "Sign up". IFTTT requiere la creación de una cuenta mediante un correo electrónico y un password (esta cuenta es totalmente gratuita):
  3. Abre el correo electrónico que proveíste en el paso anterior y confírmalo dando click en la liga que IFTTT envía después de haberte registrado:
  4. Una vez que confirmaste tu cuenta, da click en la opción "My Recipes" (observa la imagen que sigue):
  5. Existen dos tipos de "recetas": IF y DO. Para conectar Blogger y Facebook Pages vamos a crear una receta de tipo IF. Selecciona la pestaña de recetas tipo IF y da click en el botón "Create a Recipe":
  6. Observa cómo aparece la frase "ifthisthenthat" (figura de abajo). Da click en la palabra "this" que aparece resaltada en azul cielo:
  7. A continuación, selecciona Blogger de entre las aplicaciones que IFTTT muestra (si no aparece entre ellas, puedes buscarla en el cuadro de texto que dice "Search Channels"). La primera vez que se selecciona un canal o app, podrás seleccionar qué tipo de información de tu perfil quieres compartir con IFTTT:
  8. Después de seleccionar Blogger como nuestra primera aplicación, tenemos que seleccionar el tipo de acción que se va a llevar a cabo cada vez que un nuevo post es publicado en nuestro blog. De entre las dos opciones mostradas abajo, selecciona la izquierda ("Any new post") para activar nuestra receta cada vez que cualquier nuevo post se publique:
  9. Presiona el botón azul para crear la acción que disparará la receta:
  10. Nuestra nueva receta refleja lo que acabamos de hacer y es momento de seleccionar la segunda aplicación que queremos conectar (en este caso Facebook pages). Da click en la palabra "that" que está resaltada en azul:
  11. Selecciona la segunda aplicación de entre las opciones, actívala si es que no la has usado antes y ajusta la información que quieras compartir. En este caso la segunda aplicación será Facebook pages (que aparece como un canal por separado con respecto a Facebook):
  12. Elige la acción que quieres que ocurra en este segundo canal. En este caso, para crear un post en la página de Facebook, elige la opción de enmedio:
  13. Elige los campos (IFTTT les llama "ingredientes") que quieras que aparezcan en el post. Esto se logra dando click en las cajas de texto y después dando click en el ícono que aparece a la derecha. El primer campo requiere la URL del blog post y ya está puesto automáticamente. En el segundo (y más grande) cuadro de texto, puedes elegir diferentes "ingredientes" para la liga del blog en la página de Facebook. En este caso, yo simplemente elegí compartir el título del post:
  14. Por último, crea la receta presionando el botón azul:
  15. La interpretación de la receta es la siguiente: Si se ha creado un nuevo post en tu blog, entonces crea un post en tu página de Facebook seleccionada que contiene un link a ese nuevo post del blog. Para probar esta nueva receta, crea un nuevo post y córrela presionando en el botón "Check now":

El resultado (en la página de Facebook de este blog) de crear la receta anterior es el siguiente:

Si no estás satisfecho con la apariencia del post en la página de Facebook, tienes que borrar el post en tu blog y volver a crear uno nuevo, aplicar los cambios que desees a la receta en IFTTT y correr la receta como se menciona en el último paso.

De acuerdo con el blog Technology And Life, la receta se corre automáticamente cada 15 minutos y solamente se ejecuta si encuentra un post nuevo en el blog.

IFTTT es una herramienta muy interesante y dentro de la página puedes encontrar cientos de otras recetas para conectar diferentes aplicaciones o ejecutar distintas acciones. Vale la pena explorarlo a fondo. Aprender a utilizar esta herramienta puede resultar en ahorros de tiempo y esfuerzo para manejar nuestras aplicaciones.

domingo, 30 de agosto de 2015

Cómo aprender a resolver problemas en programación: Introducción

  1. Cómo aprender a resolver problemas en programación: Introducción

Durante la última mitad de mis estudios en la universidad me dediqué casi exclusivamente a trabajar con hardware y dejé un poco de lado la programación. Después de graduarme descubrí que había perdido bastante práctica y decidí comenzar a resolver problemas utilizando C++. Aunque C++ es el lenguaje que utilicé en mi último proyecto, éste no requirió del uso de programación demasiado extensivo y cuando decidí regresar a utilizar la programación me sucedió algo muy curioso: era capaz de entender lo que un problema me estaba pidiendo e inclusive, era capaz de seguir la solución propuesta por algún autor o programador pero al intentar construir mi propia solución me encontré con gran dificultad para poder comenzar a escribirla.

Para tratar de solucionar esta situación realicé una búsqueda en Google y para mi sorpresa, encontré un libro que describía exactamente qué estaba pasando: Think Like a Programmer. An Introduction to Creative Problem Solving. Mi problema no era la falta de conocimiento acerca del uso del lenguaje de programación sino la falta de práctica en cómo resolver problemas.

Desarrollar una técnica para resolver problemas eficiente y elegantemente cuesta tiempo, esfuerzo y paciencia. Aunque esta es una habilidad fundamental para todo buen programador, desafortunadamente no se enseña de manera sistemática en la escuela y en muchas ocasiones, el programador comienza realmente a aprender cuando ya se encuentra trabjando en la industria. Sin embargo, resolver problemas de programación es un arte y al no contar con una forma organizada para desarrollar este arte, muchos programadores capaces e inteligentes pueden llegar a frustrarse y pensar erróneamente que no poseen las habilidades necesarias para ser buenos programadores. En esta serie de posts me gustaría hablar acerca de cómo aprender a resolver problemas con el propósito de ayudar a todos aquellos que han vivido una situación similar a la mía: la falta de práctica para resolver un problema. En especial, me gustaría discutir acerca de lo que me fue más útil después de haber comprado y estudiado el libro que acabo de mencionar.

De la misma forma en que el autor propone ejercicios después de cada capítulo, estaré dejando ejercicios que considero útiles para todo aquél que quiera aprender o mejorar su técnica de resolución de problemas. Tal y como el autor del libro lo menciona al final de cada capítulo: de nada sirve leer los conceptos si no se practican. Por lo tanto, si de verdad quieres aprender a resolver problemas entonces resuelve lo más que puedas de los ejercicios: mientras más resuelvas, mejor.

domingo, 25 de enero de 2015

Soundex

Breve implementación del algoritmo soundex. Soundex es un algoritmo fonético, es decir, se utiliza para indexar palabras de acuerdo con su pronunciación. La mayoría de estos algoritmos se desarrollaron para ser ocupados en el idioma inglés. A diferencia del español en el que prácticamente todas las palabras se escriben de la manera en la que suenan, en el inglés existen varias formas de escribir una palabra. Por ejemplo, el apellido Smyth and el apellido Smith se pronuncian exactamente de la misma forma pero su escritura es diferente. En este caso, nos vamos a enfocar en el uso de Soundex con apellidos.

Las reglas del soundex son las siguientes:

Guía de codificación de Soundex
Número Letra que representa
1 B, F, P, V
2 C, G, J, K, Q, S, X, Z
3 D, T
4 L
5 M, N
6 R

Para las letras A, E, I, O, U, H, W , Y se utiliza el cero (0) o bien, se ignoran completamente (ejemplo: Lee se codifica como L-000).

  1. Cada apellido codificado con soundex consiste en una letra seguida por tres números, por ejemplo, el apellido Smith se codifica como S-530
  2. Si el apellido tiene letras repetidas (como por ejemplo Higgins), la letra repetida se cuenta una sola vez: H-252 (H es la primera letra, la "i" se ignora, la "g" se toma en cuenta una sola vez, la segunda "i" se ignora y los dos últimos dígitos corresponden a la "n" y "s" respectivamente)
  3. En los apellidos que tienen letras que se codifican con el mismo número y se encuentran juntas, estas letras se toman en cuenta como un solo caracter. Por ejemplo, Jackson se codifica como J-250 (J, 2 para la "c", la "k" se ignora, la "s" también se ignora, la "o" se ignora, 5 para la "n" y finalmente, se completa con 0 para cumplir con la primera regla)
  4. Si el apellido tiene prefijos como Van, Con, De, Di, La, o Le, entonces el apellido se puede codificar de dos formas: tomando en cuenta el prefijo o ignorándolo. Por ejemplo, VanDeusen se puede codificar como V-532 (V, 5 para la "n", 3 para la "d", la "e" y la "u" se ignoran, 2 para la "s" y la última "n" se ignora para no romper la primera regla) o como D-250 (D, la "e" y la "u" se ignoran, 2 para la "s", la "e" se ignora, 5 para la última "n" y se completa con 0 para cumplir con la primera regla)
  5. Si una vocal se encuentra en medio de dos consonantes que se codifican con el mismo número, se toma en cuenta la consonante que se encuentra a la derecha de la vocal. Por ejemplo, Tymczak se codifica como T-522 (T, la "y" se ignora, 5 para la "m", la "c" se ignora, la "z" se ignora, la "a" se ignora y solamente se escribe 2 para la "k")
  6. Si "H" o "W" se encuentran enmedio de dos letras que se codifican con el mismo número, entonces se ignora la consonante de la derecha. Por ejemplo, Ashcraft se codifica como A-261 (A, 2 por la "s", la "h" se ignora, la "c" se ignora, 6 por la "r", 1 por la "f" y la "t" se ignora)

Para saber más acerca de Soundex, visita: The Soundex Indexing System.

La implementación es la siguiente:

sábado, 27 de diciembre de 2014

C++11 Sincronizacion de Hilos

El primer ejemplo muestra posibles errores que resultan cuando se modifica una variable compartida desde diferentes hilos sin ninguna protección. El programa laza dos hilos, los cuales ejecutan la misma función, la cual realiza 1000 incrementos unitarios a la variable compartida; idealmente el resultado debe ser 2,000.

Una posible salida de este programa es:
$ ./thread_race
305: 1375
417: 1937
419: 1208
534: 1393
619: 1037
655: 1934
688: 1805
699: 1457
Una forma de arreglar este programa es usar un mutex para proteger el acceso a esta variable. Además estamos midiendo el tiempo de ejecución.

Esta es una posible ejecución:
$ ./thread_mutex
tiempo= 1499 ms
Usar un mutex es la forma más directa de resolver este problema; sin embargo, en este caso, dado que sólo estamos compartiendo una variable entera, es posible usar una variable atómica, lo cual permite una ejecución correcta y más eficiente que usando un mutex.

Este es un ejemplo de ejecutar este código:
$ ./thread_atomic
tiempo= 560 ms
Saludos!

lunes, 22 de diciembre de 2014

C++ accumulate

Este es un pequeño tip que se me hizo interesante. Veamos el siguiente codigo:

Imprime lo siguiente:
resultado= 987459712
resultado= 5000000050000000

El segundo resultado es el correcto.

Cuando usamos, por ejemplo, contenedores de la STL, tenemos que especificar el tipo del elemento que queremos, por ejemplo: vector<double>. Pero en el caso de los algoritmos de la STL, por default se basan en los argumentos. En el caso anterior, el compilador deduce para el primer accumulate que queremos un tipo entero para guardar el resultado final, lo cual causa un overflow cuando se suman todos los elementos.

Para el segundo accumulate, gracias a que usamos 0L, el compilador deduce correctamente que queremos usar un long para guardar el resultado de la suma.

Esto es mas aparente cuando vemos en la referencia que esta función usa el tercer parámetro para deducir que tipo usar para acumular el resultado final.

Saludos.

C++11 Futures

Este programa es una variación del programa anterior. En el programa anterior usamos variables por referencia para obtener los resultados parciales de las sumas. En este ejemplo usamos futures, los cuales nos permiten especificar una tarea que se puede realizar de forma asíncrona, y podemos recuperar el resultado invocando el método get del future.
result= 5000000050000000
duration= 123 ms
Saludos!

domingo, 21 de diciembre de 2014

C++11 Hilos

Basados en el ejemplo anterior, ahora sumaremos los elementos usando varios hilos; veamos si eso ayuda en el tiempo de ejecución.
Este es el resultado en mi computadora que tiene 2 procesadores dual-core:
resultado= 5000000050000000
hilos=4
tiempo= 137 ms
Como podemos ver, el tiempo de ejecución no necesariamente es una cuarta parte del tiempo obtenido en la publicación anterior; esto nos permite observar que existe un costo por crear hilos, por lo cual debemos tener cuidado en balancear el número de hilos creados contra la cantidad de trabajo realizada por cada hilo.
De hecho, experimentado con el código, forcé el programa a usar sólo 2 o 3 hilos (línea 13), con 2 hilos el tiempo de ejecución fue alrededor de 150ms y con 3 hilos alrededor de 175ms, interesante!
Compilé este programa con:
g++ -std=c++11 sum_thread.cc -o sum_thread -pthread
Para poder obtener el resultado obtenido por cada hilo, pasamos una variable por referencia (línea 24), en la siguiente entrada veremos como podemos hacer esto más sencillo.
Saludos!

jueves, 18 de diciembre de 2014

C++11 Medir tiempo de ejecucion

El siguiente ejemplo mide el tiempo en milisegundos que la función accumulate toma en sumar un arreglo.

Esta es la salida del programa en mi computadora:
result= 5000000050000000
duration= 297 ms

Saludos!

domingo, 7 de diciembre de 2014

Multiples ventanas con ncurses

Ncurses permite crear simples interfaces en una terminal de comandos. El siguiente código muestra como crear 4 ventanas independientes, se lanzan también 4 threads (hilos) y cada uno actualiza un contador en una de las ventanas.
Para compilar el programa:

g++ -std=c++11 10_thread.cc -lncurses -pthread



Estos los recursos que utilice para crear este programa de ejemplo:
Saludos!

domingo, 30 de noviembre de 2014

Ubuntu Montar Partición NTFS

En los últimos meses he reinstalado un par de veces mi computadora con Ubuntu 14.04 y en ambas ocasiones tuve que hacer modificaciones para montar la partición NTFS que comparto entre Windows y Ubuntu.

Para ello, tuve que obtener el UUID de la particion usando el comando blkid y agregar la siguiente linea al archivo /etc/fstab:

UUID=1234567890 /ruta/para/montar ntfs-3g permissions,locale=en_US.utf8    0   0

El directorio /ruta/para/montar lo cree previamente usando sudo.

Es importante mencionar que el parámetro "permissions" habilita el poder ejecutar archivos guardados en esta partición.

Saludos.

domingo, 13 de octubre de 2013

Monitoreando ruteador con Raspberry Pi

Continuando con nuestros experimentos con el Rasperrry Pi. Decidimos crear un monitor de tráfico para el ruteador. Nuestra compañía de internet nos impone un límite mensual, por lo que nos es útil saber el consumo que llevamos en un día.

La primer opción fue escanear el tráfico directamente de la red e ir contando el tamaño de los datos transmitidos. Sin embargo, esta solución no funciono, ya que al estar conectados al ruteador, sólo recibimos paquetes que están destinados al Raspeberry o paquetes broadcast.

La segunda opción fue conectarse directamente al ruteador y extraer la información del tráfico del día. Para ello, primero nos conectamos manualmente al ruteador y monitoreamos el tráfico usando Wireshark, esto nos permitió aprender que el ruteador usa autenticación básica y que la página que contiene la información del tráfico se llama traffic.htm. Esto también nos ayudo a inspeccionar el contenido de traffic.htm y observar que una variable de javascript contiene la información que necesitamos.

Con toda esta información, la lógica del programa es muy sencilla.

  1. Inicializar IO y prender todos los LEDs durante 3 segundos para diagnosticar LEDs en mal estado.
  2. Ciclo infinito:
    1. Obtener traffic.htm del ruteador
    2. Extraer tráfico del día
    3. Desplegar en formato binario usando los LEDs el tráfico del día en cientos de MB
Está imagen es cuando el tráfico del día ha sido un poco más de 800MB.


El código en python es el siguiente:

import urllib2
import re
import base64
import time
import RPi.GPIO as GPIO

def get_router_page():
  theurl = 'http://192.168.1.1/traffic.htm'
  username = 'admin'
  password = 'your_password'
  req = urllib2.Request(theurl)
  
  # First try without username/password
  try:
    handle = urllib2.urlopen(req)
  except IOError, e:
    pass
  else:
    return handle.read()

  # Now try with authentication
  base64string = base64.encodestring(
                '%s:%s' % (username, password))[:-1]
  authheader =  "Basic %s" % base64string
  req.add_header("Authorization", authheader)
  
  try:
    handle = urllib2.urlopen(req)
  except IOError, e:
    print e
    return None
  
  return handle.read()


def get_traffic_in_MB(page):
  for line in page.split('\n'):
    match = re.search(
      r'\s*var\s*traffic_today_total\s*=\s*"(.*)"\s*;\s*', 
      line)
    if match:
      return match.group(1).replace(',','')
  return None


def is_bit_set(value, bit):
  mask = 1 << bit
  return (value & mask)


def display_traffic(traffic_MB):
  traffic_in_100_MB = int(float(traffic_MB) / 100)
  
  if traffic_in_100_MB > 31:
    traffic_in_100_MB = 31
  print traffic_in_100_MB
  GPIO.output(LED_0_PIN,is_bit_set(traffic_in_100_MB,0))
  GPIO.output(LED_1_PIN,is_bit_set(traffic_in_100_MB,1))
  GPIO.output(LED_2_PIN,is_bit_set(traffic_in_100_MB,2))
  GPIO.output(LED_3_PIN,is_bit_set(traffic_in_100_MB,3))
  GPIO.output(LED_4_PIN,is_bit_set(traffic_in_100_MB,4))


def init_IO():
  # Init outputs
  GPIO.setmode(GPIO.BCM)
  GPIO.setup(LED_0_PIN,GPIO.OUT)
  GPIO.setup(LED_1_PIN,GPIO.OUT)
  GPIO.setup(LED_2_PIN,GPIO.OUT)
  GPIO.setup(LED_3_PIN,GPIO.OUT)
  GPIO.setup(LED_4_PIN,GPIO.OUT)
  
  # Test all leds
  GPIO.output(LED_0_PIN,True)
  GPIO.output(LED_1_PIN,True)
  GPIO.output(LED_2_PIN,True)
  GPIO.output(LED_3_PIN,True)
  GPIO.output(LED_4_PIN,True)
  time.sleep(3)
  GPIO.output(LED_0_PIN,False)
  GPIO.output(LED_1_PIN,False)
  GPIO.output(LED_2_PIN,False)
  GPIO.output(LED_3_PIN,False)
  GPIO.output(LED_4_PIN,False)

LED_0_PIN = 23
LED_1_PIN = 24
LED_2_PIN = 25
LED_3_PIN = 8
LED_4_PIN = 7
init_IO()

while True:
  page = get_router_page()
  if page is not None:
    traffic = get_traffic_in_MB(page)
    if traffic is not None:
      display_traffic(traffic)
  time.sleep(60)
GPIO.cleanup()


Saludos.