Programación de Algoritmos – Algunos Consejos

Como dije en un anterior post, hay que empezar con las pruebas. Unos buenos casos de prueba son esenciales. ¿Cómo hacer esto? Pues bien, el primero es fácil, la descripción del problema comúnmente te da un ejemplo, ese ejemplo es el primer caso de prueba.

Luego intenta hacer un ejemplo similar por ti mismo, y ese será el segundo caso de prueba,

Luego viene la regla de chico, mediano y grande. El problema normalmente te da limites, números de 1 a 100,000 por ejemplo, bueno, pues hacemos una prueba para números chicos menores de 100, una media de entre 40 y 60 mil y una para numeros grandes cercanos al 100,000.

Luego vienen los intentos de “tronar” el algoritmos. ¿Quie pasa si pones un solo elemento? ¿Si no hay elementos? ¿Si pones el límite de elementos, 100,000, por ejemplo? Es decir, te vas a los extremos.

Luego casos más específicos ¿Que pasa si no se cumple una condición? Por ejemplo, buscas números perdidos en un arreglo, ¿Que pasa si no hay perdidos? ¿Que pasa si el perdido esta al principio del arreglo? ¿Que pasa si está hasta el final del arreglo?

Todos estos casos de prueba, y todos los que se ocurran, debemos usarlos para probar bien el algoritmo antes de enviarlo a revisión. Repasemos:

1. Primero la prueba del ejemplo
2. Luego prueba similar manualmente generada
3. Luego prueba chica, mediana y grande.
4. Luego casos particulares y excepciones

Recordemos, probar a querer tronar el algoritmo, para que nos quede sólido como roca. Ahora, hay un problema con los números grandes, si tienes que probar por ejemplo arreglos de miles de núimeros, manualmente no vas a poder hacerlo, así que, además de la implementación del algoritmo tendrás que escribir una pequeña rutina que los genere.

Posiblemente tendrás que manipularlos manualmente después para que queden en los casos de pruebas o mejor aún, desde el mismo script. Un buen caso de pruebas tiene datos de entrada y una salida esperada. Las revisiones de algoritmos son automátizadas, así que es conveniente también automatizar este procesos.

Podemos, por ejemplo, crear una rutina que lea los casos de prueba de un archivo, mande ejecutar nuestro algoritmo en un script con los datos de entrada, y la compare con la salida, emulando un poco la manera en que lo hace el robot de revisión.

La buena noticia es que podemos crearnos fácilmente un pequeño framework para hacer este proceso más rápido y automátizado.

Complejidad de Tiempo

Tenemos que tomar muy en cuenta la complejidad de tiempo, es decir, el número de veces que tenemos que calcular. Sobre todo si se trata de arreglos muy largos, si se especifica que el peor escenario es O(n), quiere decir que solo le podemos dar una vuelta al arreglo.

Para muchos algoritmos esto se nos complica, puesto que necesitamos dos arreglos para llevar a cabo los cálculos, por ejemplo, cuando debemos como “pasar lista” de los números que ya calculamos. Si no tenemos cuidado, esto nos puede elevar a complejidad de tiempo cuadrática.

Un truco es utilizar un segundo arreglo para “pasar lista”, donde sus índices serán los números que ya visitamos, siendo el valor un booleano, si ya lo visitamos es verdadero, sino, falso. De esta manera, si consultamos el valor del elemento en el arreglo, no necesitaremos recorrerlo en cada iteración, manteniendo la complejidad en O(n), es decir, un solo recorrido de arreglo, vuelta sencilla.

Por ejemplo:

// Suponemos $a es el arreglo y $n su número de elementos.

$list = array();

for( $i = 0; $i < $n; $i++ ) {

  if ( ! $list[$a[$i]] ) {

    // Aqui lo ponemos como visitado

    $list[$a[$i]] = true;

  }

  // Aqui seguimos con el algoritmos

  // TODO with $a[$i]

} // end for

Con esto no tenemos que recorrer el segundo arreglo, utilizamos sus índeces para almacenar el valor y con ellos pasamos lista sin gastar operaciones de más como lo hariamos con un segundo arreglo y buscando su elemento en el para verificar si ya lo visitamos.

Un saludo a todos, chicos.

L.