El propósito de la Kata es sencillo: practicar.
Los músicos practican escalas, arpegios, acordes, estudios, piezas completas, etc.
Los artistas marciales practican los movimientos individuales una y otra vez y después los combinan en secuencias de ataque-defensa-contra.
Los programadores... esperamos hasta la hora de la verdad... hmmm... tal vez no es la mejor estrategia.
El propósito del Kata no es buscar la solución a un problema. De hecho, la mayoría están basados en problemas simples, que han sido resueltos y documentados ampliamente en los libros de introducción a la ciencia de la computación.
Más bien, el valor de practicar un kata es practicar y afinar nuestras habilidades y disciplinas.
¿Cuantas veces nos hemos dicho a nosotros mismos que ahora si escribiré pruebas para el código de mi próximo proyecto?
¿O cuantas veces nos hemos prometido que ahora si vamos a aprender a usar correctamente los atajos de teclado del nuevo IDE que estamos comenzando a usar?
Dado que los kata son ejercicios controlados, sobre problemas cuya solución ya conocemos, nos dan la oportunidad perfecta para concentrarnos no tanto en la parte de descubrir o aprender el algoritmo, sino las partes mecánicas del proceso.
A continuación, procedo a desarrollar un kata muy básico: la búsqueda binaria.
Mi propósito para esta sección es hacerlo paso a paso siguiendo estrictamente el método de Desarrollo Dirigido por Pruebas (TDD por sus siglas en ingles)
El ritmo del TDD:
- Fallo
- Éxito
- Refactorizar
También conocido como "Red, Green, Refactor!".
Las tres leyes del TDD:
- No se permite escribir nada de código de producción hasta no tener una prueba que falle (y no compilar es fallar).
- No se permite escribir una prueba más allá de lo necesario para que falle.
- No se permite escribir más código de producción que el necesario para pasar la prueba.
Escribimos nuestra primera prueba: El caso degenerado.
def test_bsearch(): assert_equal(-1, bsearch(3, [])) if __name__ == '__main__': test_bsearch()
puesto que no existe la función bsearch, obtenemos un error:
Traceback (most recent call last): File "chop.py", line 64, in <module> test_bsearch() File "chop.py", line 61, in test_bsearch assert_equal(-1, bsearch(3, [])) NameError: global name 'bsearch' is not defined
A continuación hacemos lo mínimo necesario para corregir el error:
def bsearch(what, seq): pass
Ahora tenemos:
Traceback (most recent call last): File "chop.py", line 67, in <module> test_bsearch() File "chop.py", line 64, in test_bsearch assert_equal(-1, bsearch(3, [])) File "chop.py", line 47, in assert_equal assert expected == actual, message AssertionError: -1 was expected, but got None
Ahora hacemos lo más simple que pueda funcionar para lograr que pase la prueba:
def bsearch(what, seq): return -1
Con esto es bastante (si, algo bobo será, pero tengamos paciencia. Apenas estamos comenzando). Ahora escribamos la siguiente prueba:
def test_bsearch(): assert_equal(-1, bsearch(3, [])) assert_equal(-1, bsearch(3, [1]))
Pasa sin hacer nada. Sigamos:
def test_bsearch(): assert_equal(-1, bsearch(3, [])) assert_equal(-1, bsearch(3, [1])) assert_equal(0, bsearch(1, [1]))
Falla. ¿Qué es lo más simple que podemos hacer para que pase, junto con las dos anteriores?
def bsearch(what, seq):
if len(seq):
if seq[0] == what:
return 0
return -1
La prueba pasa. Sigamos:
def test_bsearch(): assert_equal(-1, bsearch(3, [])) assert_equal(-1, bsearch(3, [1])) assert_equal(0, bsearch(1, [1])) assert_equal(-1, bsearch(0, [1, 3])) assert_equal(0, bsearch(1, [1, 3])) assert_equal(1, bsearch(3, [1, 3]))
Las pruebas 4 y 5 pasan sin modificación. La 6 falla, sin embargo.
def bsearch(what, seq):
if len(seq):
if seq[0] == what:
return 0
if seq[1] == what:
return 1
return -1
¡¡Woops!!
Traceback (most recent call last): File "chop.py", line 79, in <module> test_bsearch() File "chop.py", line 71, in test_bsearch assert_equal(-1, bsearch(3, [1])) File "chop.py", line 65, in bsearch if seq[1] == what: IndexError: list index out of range
Claro, debemos tomar en consideración las dimensiones de la lista:
def bsearch(what, seq):
start, end = 0, len(seq) - 1
if start <= end:
if seq[start] == what:
return start
elif seq[end] == what:
return end
return -1
Listo. Continuamos:
def test_bsearch(): assert_equal(-1, bsearch(3, [])) assert_equal(-1, bsearch(3, [1])) assert_equal(0, bsearch(1, [1])) assert_equal(-1, bsearch(0, [1, 3])) assert_equal(-1, bsearch(2, [1, 3])) assert_equal(-1, bsearch(4, [1, 3])) assert_equal(0, bsearch(1, [1, 3])) assert_equal(1, bsearch(3, [1, 3])) assert_equal(0, bsearch(1, [1, 3, 5])) assert_equal(1, bsearch(3, [1, 3, 5]))
Ahora el problema es que el elemento que buscamos se encuentra justo en medio de la lista. Podríamos hacer algo bobo como if seq[1] == what: return 1, pero eso no nos lleva a ningún lado. Recordemos que...
"Conforme las pruebas se vuelven más específicas, el código se vuelve más genérico."
def bsearch(what, seq):
start, end = 0, len(seq) - 1
if start <= end:
half = (start + end) / 2
if seq[half] == what:
return half
if seq[start] == what:
return start
if seq[end] == what:
return end
return -1
Siguiente prueba:
def test_bsearch(): assert_equal(-1, bsearch(3, [])) assert_equal(-1, bsearch(3, [1])) assert_equal(0, bsearch(1, [1])) assert_equal(-1, bsearch(0, [1, 3])) assert_equal(0, bsearch(1, [1, 3])) assert_equal(1, bsearch(3, [1, 3])) assert_equal(0, bsearch(1, [1, 3, 5])) assert_equal(1, bsearch(3, [1, 3, 5])) assert_equal(2, bsearch(5, [1, 3, 5])) assert_equal(-1, bsearch(0, [1, 3, 5])) assert_equal(-1, bsearch(2, [1, 3, 5])) assert_equal(-1, bsearch(4, [1, 3, 5])) assert_equal(-1, bsearch(6, [1, 3, 5]))
Esto se está comenzando a poner algo redundante... tiempo de refactorizar:
def impares(cuantos):
limite = 2 * cuantos
return [indice for indice in xrange(1, limite, 2)]
def pares(cuantos):
limite = 2 * (cuantos + 1)
return [indice for indice in xrange(0, limite, 2)]
@trace
def bsearch(what, seq):
start, end = 0, len(seq) - 1
if start <= end:
half = (start + end) / 2
if seq[half] == what:
return half
if seq[start] == what:
return start
if seq[end] == what:
return end
return -1
def test_bsearch(limite):
for cuantos in xrange(limite):
lista = impares(cuantos)
for indice, valor in enumerate(lista):
assert_equal(indice, bsearch(valor, lista))
for not_found in pares(cuantos):
assert_equal(-1, bsearch(not_found, lista))
if __name__ == '__main__':
test_bsearch(4)
Bien, hasta este punto todas las pruebas pasan:
$ python chop.py bsearch(0, []) -> -1 bsearch(1, [1]) -> 0 bsearch(0, [1]) -> -1 bsearch(2, [1]) -> -1 bsearch(1, [1, 3]) -> 0 bsearch(3, [1, 3]) -> 1 bsearch(0, [1, 3]) -> -1 bsearch(2, [1, 3]) -> -1 bsearch(4, [1, 3]) -> -1
Siguiente prueba:
if __name__ == '__main__': test_bsearch(5)
Falla:
... bsearch(1, [1, 3, 5, 7]) -> 0 bsearch(3, [1, 3, 5, 7]) -> 1 bsearch(5, [1, 3, 5, 7]) -> -1 AssertionError: 2 was expected, but got -1
Bien, ahora el resultado no está ni al principio, ni al final ni tampoco en el medio (recordemos que estamos usando aritmética entera, por lo que (0 + 3) / 2 = 1).
Eso significa que debemos examinar los elementos intermedios. Pero recordemos que si procedemos a evaluarlos uno por uno como lo hemos venido haciendo, la búsqueda se convierte en una operación con un tiempo de ejecución de O(n). Por ello, solo hemos de examinar la mitad con probabilidad de contener el elemento buscado:
def bsearch(what, seq):
start, end = 0, len(seq) - 1
while start <= end:
half = (start + end) / 2
if seq[half] == what:
return half
if seq[half] < what:
start = half + 1
else:
end = half - 1
return -1
Todas las pruebas pasan:
... test_bsearch(14) ... test_bsearch(19) ... test_bsearch(25)
¿Qué pasa si en lugar de listas de números impares usaramos listas de números pares?
if __name__ == '__main__': test_bsearch(5) pares, impares = impares, pares test_bsearch(5)
Desarrollo
Como los músicos harían, una vez que tenemos una técnica bajo nuestro comando, habrá que buscar todas las variaciones posibles.
¿Podemos escribir una versión recursiva en lugar de iterativa?, ¿Usar multiples threads?, ¿En cuantos lenguajes podemos desarrollar nuestra kata, logrando que nuestra implementación no solo sea correcta, sino también idiomática del lenguaje seleccionado?
Saludos
Apéndice
A continuación, incluyo el código de las funciones trace y assert_equal, usadas en el desarrollo del kata.
class ArgFormatter(object):
def __init__(self, args, kwds):
(self.args, self.kwds) = (args, kwds)
self.params = []
def _clear(self):
self.params = []
def _addPositional(self):
self.params.extend(repr(arg) for arg in self.args)
def _addKeywords(self):
self.params.extend('%s=%r' % (k, valor) for (k, valor) in self.kwds.iteritems())
def _assemble(self):
return ', '.join(self.params)
def Format(self):
self._clear()
self._addPositional()
self._addKeywords()
return self._assemble()
def trace(f):
from functools import wraps
def formatParams(args, kwds):
return ArgFormatter(args, kwds).Format()
@wraps(f)
def decorator(*args, **kwds):
result = None
params = formatParams(args, kwds)
print '%s(%s) ->' % (f.__name__, params),
result = f(*args, **kwds)
print repr(result)
return result
return decorator
def assert_equal(expected, actual):
message = "%s was expected, but got %s" % (expected, actual)
assert expected == actual, message
