TDD como enfoque a problemas algorítmicos

Fallé en una prueba algorítmica con Codility porque intenté encontrar una solución mejor y al final no tuve nada.

¿Entonces me hizo pensar si podría usar un enfoque similar a TDD? Es decir, si generalmente puedo desarrollar una solución gradualmente de manera similar.

Si estuviera escribiendo un algoritmo de clasificación, podría pasar de un Bubblesort estándar a un bubbleort de 2 vías, pero luego algo más avanzado como Quicksort sería un "salto cuántico", pero al menos tendría datos de prueba que puedo validar fácilmente.

¿Otros consejos para tales pruebas? Una cosa que haría la próxima vez es usar más métodos / funciones que los bucles internos. Por ejemplo, en la clasificación, a menudo necesita un intercambio. Si fuera un método, solo necesitaría modificar el código de llamada. Incluso podría tener soluciones más avanzadas como clases derivadas.

Con problemas "algorítmicos" versus problemas "normales" me refiero a problemas en los que la complejidad del tiempo es importante. Entonces, en lugar de pasar más pruebas como en TDD, lo haría "comportarse mejor".

Con "similar a TDD" quiero decir:

1. Escriba pruebas relativamente automáticas para ahorrar tiempo en incrementos de pruebas manuales.
2. Desarrollo incremental.
3. Pruebas de regresión, capacidad de detectar si el código se rompe o al menos si la funcionalidad cambia entre incrementos.

Creo que esto debería ser tranquilo fácil de entender si comparas

1. Escribir un tipo de shell directamente
2. Saltar de bubbleort a quicksort (reescritura total)
3. Pasar de forma incremental de una clasificación de burbuja unidireccional a una clasificación de shell (si es posible).

Vea también el intento de Ron Jeffries de crear un solucionador de Sudoku con TDD , que desafortunadamente no funcionó.

El algoritmo requiere una comprensión significativa de los principios de diseño de algoritmos. Con estos principios, de hecho, es posible proceder gradualmente, con un plan, como lo hizo Peter Norvig .

De hecho, para algoritmos que requieren un esfuerzo de diseño no trivial, casi siempre es que el esfuerzo es de naturaleza incremental. Pero cada "incremento", que es pequeño a los ojos de un diseñador de algoritmos, parece un salto cuántico (para tomar prestada su frase) a una persona que no ha tenido la misma experiencia o conocimiento con esta familia particular de algoritmos.

Esta es la razón por la cual una educación básica en teoría CS combinada con mucha práctica de programación de algoritmos es igualmente importante. Saber que existe una "técnica" particular (pequeños bloques de construcción de algoritmos) es un largo camino para hacer estos saltos cuánticos incrementales.

Sin embargo, existen algunas diferencias importantes entre el progreso incremental en algoritmos y TDD.

JeffO ha mencionado una de las diferencias : una prueba que verifica la exactitud de los datos de salida es independiente de una prueba que afirma el rendimiento entre diferentes implementaciones del mismo algoritmo (o diferentes algoritmos que compiten para dar la misma solución).

En TDD, uno agrega un nuevo requisito en la forma de una prueba, y esta prueba inicialmente no pasará (rojo). Entonces se cumple el requisito (verde). Finalmente el código se refactoriza.

En el desarrollo de algoritmos, el requisito generalmente no cambia. La prueba de verificación de la corrección del resultado se escribe primero o poco después de que se complete un borrador (altamente seguro pero lento) de la implementación del algoritmo. Esta prueba de corrección de datos rara vez se cambia; uno no lo cambia para fallar (rojo) como parte del rito TDD.

Sin embargo, en este aspecto, el análisis de datos es claramente diferente del desarrollo de algoritmos, porque los requisitos de análisis de datos (tanto los conjuntos de entrada como los resultados esperados) solo se definen libremente en la comprensión humana. Por lo tanto, los requisitos cambian con frecuencia a nivel técnico. Este cambio rápido coloca el análisis de datos en algún lugar entre el desarrollo de algoritmos y el desarrollo de aplicaciones de software en general, aunque aún requiere mucho algoritmo, los requisitos también están cambiando "demasiado rápido" al gusto de cualquier programador.

Si el requisito cambia, normalmente requiere un algoritmo diferente.

En el desarrollo de algoritmos, cambiar (ajustar) la prueba de comparación de rendimiento para que falle (rojo) es una tontería: no le da ninguna idea sobre los posibles cambios en su algoritmo que mejorarían el rendimiento.

Por lo tanto, en el desarrollo de algoritmos, tanto la prueba de corrección como la prueba de rendimiento no son pruebas TDD. En cambio, ambas son pruebas de regresión . Específicamente, la prueba de regresión de corrección le impide realizar cambios en el algoritmo que romperá su corrección; la prueba de rendimiento le impide realizar cambios en el algoritmo que lo hará correr más lento.

Todavía puede incorporar TDD como un estilo de trabajo personal, excepto que el ritual "rojo - verde - refactor" no es estrictamente necesario ni particularmente beneficioso para el proceso de pensamiento del desarrollo de algoritmos.

Yo diría que las mejoras en el algoritmo en realidad resultan de realizar permutaciones aleatorias (no necesariamente correctas) a los diagramas de flujo de datos del algoritmo actual, o mezclarlas y combinarlas entre implementaciones previamente conocidas.

TDD se utiliza cuando hay múltiples requisitos que se pueden agregar de forma incremental a su conjunto de prueba.

Alternativamente, si su algoritmo está basado en datos, cada pieza de datos de prueba / caso de prueba se puede agregar de forma incremental. TDD también sería útil. Por esta razón, un enfoque "similar a TDD" de "agregar nuevos datos de prueba - mejorar el código para que maneje estos datos correctamente - refactorizar" también funcionará para el trabajo de análisis de datos abierto, en el que los objetivos de los algoritmos se describen en humanos palabras céntricas y su medida de éxito también juzgadas en términos humanos definidos.

Pretende enseñar una manera de hacerlo menos abrumador que tratar de satisfacer todos (docenas o cientos) de requisitos en un solo intento. En otras palabras, TDD está habilitado cuando puede dictar que ciertos requisitos u objetivos de estiramiento pueden ignorarse temporalmente mientras implementa algunos borradores iniciales de su solución.

TDD no es un sustituto de la informática. Es una muleta psicológica que ayuda a los programadores a superar el impacto de tener que satisfacer muchos requisitos a la vez.

Pero si ya tiene una implementación que da el resultado correcto, TDD consideraría su objetivo cumplido y el código listo para ser entregado (para refactorizar, o para otro usuario programador). En cierto sentido, lo alienta a que no optimice prematuramente su código, al darle objetivamente una señal de que el código es "suficientemente bueno" (para pasar todas las pruebas de corrección).

En TDD, también se enfoca en los "microrequisitos" (o cualidades ocultas). Por ejemplo, validaciones de parámetros, aserciones, lanzamiento y manejo de excepciones, etc. TDD ayuda a garantizar la corrección de las rutas de ejecución que no se ejercen con frecuencia en el curso normal de la ejecución del software.

Ciertos tipos de código de algoritmo también contienen estas cosas; estos son susceptibles a TDD. Pero debido a que el flujo de trabajo general del algoritmo no es TDD, tales pruebas (en validaciones de parámetros, afirmaciones y manejo y excepción de excepciones) tienden a escribirse después de que el código de implementación ya se ha escrito (al menos parcialmente).

Para su problema, tendría dos pruebas:

1. Una prueba para asegurarse de que el algoritmo sigue siendo preciso. por ejemplo, ¿está ordenado correctamente?
2. Prueba de comparación de rendimiento: ha mejorado el rendimiento. Esto puede ser complicado, por lo que ayuda a ejecutar la prueba en la misma máquina, los mismos datos y limitar el uso de cualquier otro recurso. Una máquina dedicada ayuda.

Lo que se debe probar o la cobertura de prueba completa es discutible, pero creo que las partes complejas de su aplicación que deben ajustarse (cambiar mucho) son candidatos perfectos para las pruebas automatizadas. Estas partes de la aplicación generalmente se identifican muy temprano. Usar un enfoque TDD con esta pieza tendría sentido.

Ser capaz de resolver problemas complejos no debería verse obstaculizado por la renuencia a probar varios enfoques. Tener una prueba automatizada debería ayudar en esta área. Al menos sabrás que no lo estás empeorando.

Entonces, en lugar de pasar más pruebas como en TDD, lo haría "comportarse mejor".

Algo así como.

Puede probar el tiempo de ejecución y la complejidad. Las pruebas de tiempo de ejecución deberán ser un poco indulgentes para permitir la contención de los recursos del sistema. Pero, en muchos idiomas, también puede anular o inyectar métodos y contar llamadas a funciones reales. Y, si está seguro de que su algoritmo actual es subóptimo, puede introducir una prueba que simplemente exige sort()invocar compare()menos veces que la implementación ingenua.

O bien, puede comparar sort()en dos conjuntos y asegurarse de que se escalen en las compare()llamadas según la complejidad de su objetivo (o por ahí, si espera alguna inconsistencia).

Y, si puede demostrar teóricamente que un conjunto de tamaños no Ndebería requerir estrictamente más que N*log(N)comparaciones, podría ser razonable restringir su trabajo sort()a N*log(N)invocaciones de compare()...

Sin embargo ...

El cumplimiento de un requisito de rendimiento o complejidad no garantiza que la implementación subyacente sea {AlgorithmX} . Y, diría que esto normalmente está bien. No debería importar qué algoritmo se utilice, siempre que cumpla con su implementación cumple con sus requisitos, incluidos los requisitos importantes de complejidad, rendimiento o recursos.

Pero, si desea asegurarse de que se utilice un algoritmo particular, deberá ser más tedioso y profundizar mucho más. Cosas como..

• Asegurarse de que se realice exactamente el número esperado de llamadas compare()y swap()(o lo que sea)
• Envolviendo todas las funciones / métodos principales y asegurando, con un conjunto de datos predecible, que las llamadas ocurran exactamente en el orden esperado
• Examinando el estado de trabajo después de cada uno de los N pasos para asegurar que haya cambiado exactamente como se esperaba

Pero, de nuevo, si está tratando de asegurarse de que {AlgorithmX} se use en particular, probablemente hay características de {AlgorithmX} que le interesan que son más importantes para probar que si finalmente se usó {AlgorithmX} ...

También tenga en cuenta que TDD no niega la necesidad de investigar, pensar o planificar el desarrollo de software. Tampoco niega la necesidad de lluvia de ideas y experimentación, incluso si no puede afirmar fácilmente en Google y pizarra en su conjunto de pruebas automatizadas.