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.

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:

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!

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!

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!

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!