Approche de type TDD aux problèmes algorithmiques

J'ai échoué à un test algorithmique avec Codility parce que j'ai essayé de trouver une meilleure solution, et finalement je n'avais rien.

Cela m'a donc fait penser si je pouvais utiliser une approche similaire à TDD? C'est-à-dire si je peux généralement développer progressivement une solution de la même manière?

Si j'écrivais un algorithme de tri, je pourrais passer d'un Bubblesort standard à un Bubblesort bidirectionnel, mais alors quelque chose de plus avancé comme Quicksort serait un "saut quantique", mais au moins j'aurais des données de test que je peux facilement valider.

D'autres conseils pour de tels tests? Une chose que je ferais la prochaine fois est d'utiliser plus de méthodes / fonctions que de boucles internes. Par exemple, lors du tri, vous avez souvent besoin d'un échange. S'il s'agissait d'une méthode, je n'aurais qu'à modifier le code appelant. Je pourrais même avoir des solutions plus avancées en tant que classes dérivées.

Par problèmes «algorithmiques» ou «normaux», je veux dire des problèmes où la complexité temporelle est importante. Donc, au lieu de passer plus de tests comme dans TDD, vous le feriez "mieux se comporter".

Par "similaire à TDD", je veux dire:

1. Ecrire un test relativement automatique pour gagner du temps sur les tests manuels pr incrément.
2. Développement incrémental.
3. Test de régression, capacité à détecter si le code casse ou au moins si la fonctionnalité change entre les incréments.

Je pense que cela devrait être facile à comprendre si vous comparez

1. Écrire un shell-sort directement
2. Saut de Bubblesort à QuickSort (réécriture totale)
3. Déplacement incrémentiel d'un tri à bulle unidirectionnel vers un tri shell (si possible).

Voir aussi la tentative de Ron Jeffries de créer un solveur Sudoku avec TDD , qui malheureusement n'a pas fonctionné.

L'algorithme nécessite une compréhension significative des principes de conception des algorithmes. Avec ces principes, il est en effet possible de procéder progressivement, avec un plan, comme l'a fait Peter Norvig .

En fait, pour les algorithmes nécessitant un effort de conception non trivial, c'est presque toujours que l'effort est de nature incrémentale. Mais chaque "incrément", qui est minuscule aux yeux d'un concepteur d'algorithmes, ressemble à un saut quantique (pour emprunter votre phrase) à une personne qui n'a pas eu la même expertise ou connaissance avec cette famille particulière d'algorithmes.

C'est pourquoi une formation de base en théorie CS combinée à de nombreuses pratiques de programmation d'algorithmes sont tout aussi importantes. Savoir qu'une «technique» particulière (petits blocs d'algorithmes) existe est un long chemin vers ces sauts quantiques incrémentiels.

Il existe cependant des différences importantes entre la progression incrémentielle des algorithmes et TDD.

Une des différences a été mentionnée par JeffO : un test qui vérifie l'exactitude des données de sortie est distinct d'un test qui affirme les performances entre différentes implémentations du même algorithme (ou différents algorithmes rivalisant pour donner la même solution).

En TDD, on ajoute une nouvelle exigence sous forme de test, et ce test ne doit initialement pas réussir (rouge). Ensuite, l'exigence est satisfaite (vert). Enfin, le code est refactorisé.

Dans le développement d'algorithmes, l'exigence ne change généralement pas. Le test de vérification de l'exactitude des résultats est écrit en premier, ou peu de temps après la fin d'un projet (très confiant mais lent) de mise en œuvre de l'algorithme. Ce test d'exactitude des données est rarement modifié; on ne le change pas pour échouer (rouge) dans le cadre du rite TDD.

Cependant, dans cet aspect, l'analyse des données est nettement différente du développement d'algorithmes, car les exigences d'analyse des données (à la fois les ensembles d'entrées et les résultats attendus) ne sont définies que de manière vague dans la compréhension humaine. Ainsi, les exigences changent fréquemment au niveau technique. Ce changement rapide place l'analyse des données quelque part entre le développement d'algorithmes et le développement général d'applications logicielles - tout en étant lourd en algorithmes, les exigences changent également "trop ​​vite" au goût de tout programmeur.

Si l'exigence change, elle appelle généralement un algorithme différent.

Dans le développement d'algorithmes, changer (resserrer) le test de comparaison des performances en échec (rouge) est stupide - cela ne vous donne aucune idée des modifications potentielles de votre algorithme qui amélioreraient les performances.

Par conséquent, dans le développement d'algorithmes, le test de correction et le test de performance ne sont pas des tests TDD. Au lieu de cela, les deux sont des tests de régression . Plus précisément, le test de régression de l'exactitude vous empêche d'apporter des modifications à l'algorithme qui briseront son exactitude; le test de performances vous empêche d'apporter des modifications à l'algorithme qui le ralentiront.

Vous pouvez toujours incorporer le TDD comme style de travail personnel, sauf que le rituel "rouge - vert - refactor" n'est pas strictement nécessaire ni particulièrement bénéfique pour le processus de réflexion du développement d'algorithmes.

Je dirais que les améliorations des algorithmes résultent en fait de permutations aléatoires (pas nécessairement correctes) aux diagrammes de flux de données de l'algorithme actuel, ou de les mélanger et de les faire correspondre entre des implémentations précédemment connues.

TDD est utilisé lorsqu'il existe plusieurs exigences qui peuvent être ajoutées de manière incrémentielle à votre ensemble de tests.

Alternativement, si votre algorithme est piloté par les données, chaque élément de données de test / cas de test peut être ajouté de manière incrémentielle. TDD serait également utile. Pour cette raison, une approche "de type TDD" consistant à "ajouter de nouvelles données de test - améliorer le code pour qu'elles gèrent correctement ces données - refactoriser" fonctionnera également pour un travail d'analyse de données à composition non limitée, dans lequel les objectifs des algorithmes sont décrits en humain les mots centrés et leur mesure du succès sont également jugés en termes définis par l'homme.

Il prétend enseigner un moyen de le rendre moins écrasant que d'essayer de satisfaire toutes (des dizaines ou des centaines) d'exigences en une seule tentative. En d'autres termes, TDD est activé lorsque vous pouvez dicter que certaines exigences ou certains objectifs d'extension peuvent être temporairement ignorés pendant que vous implémentez quelques premières versions de votre solution.

TDD n'est pas un substitut à l'informatique. C'est une béquille psychologique qui aide les programmeurs à surmonter le choc d'avoir à satisfaire de nombreuses exigences à la fois.

Mais si vous avez déjà une implémentation qui donne un résultat correct, TDD considérerait son objectif atteint et le code prêt à être remis (au refactoring, ou à un autre utilisateur-programmeur). Dans un certain sens, il vous encourage à ne pas optimiser prématurément votre code, en vous donnant objectivement un signal que le code est "assez bon" (pour passer tous les tests de correction).

Dans TDD, l'accent est également mis sur les «micro-exigences» (ou qualités cachées). Par exemple, les validations de paramètres, les assertions, le lancement et la gestion des exceptions, etc. TDD aide à garantir l'exactitude des chemins d'exécution qui ne sont pas fréquemment utilisés dans le cours normal de l'exécution du logiciel.

Certains types de code d'algorithme contiennent également ces éléments; ceux-ci se prêtent au TDD. Mais comme le flux de travail général de l'algorithme n'est pas TDD, ces tests (sur les validations de paramètres, les assertions et le lancement et la gestion des exceptions) ont tendance à être écrits après que le code d'implémentation a déjà été (au moins partiellement) écrit.

Pour votre problème, vous auriez deux tests:

1. Un test pour s'assurer que l'algorithme est toujours précis. Par exemple, est-il trié correctement?
2. Test de comparaison des performances - les performances ont été améliorées. Cela peut devenir délicat, il est donc utile d'exécuter le test sur la même machine, les mêmes données et de limiter l'utilisation d'autres ressources. Une machine dédiée aide.

Ce qu'il faut tester ou la couverture complète des tests est discutable, mais je pense que les parties complexes de votre application qui doivent être affinées (changées beaucoup) sont des candidats parfaits pour les tests automatisés. Ces parties de la demande sont généralement identifiées très tôt. L'utilisation d'une approche TDD avec cette pièce aurait du sens.

La capacité de résoudre des problèmes complexes ne devrait pas être entravée par une réticence à essayer différentes approches. Un test automatisé devrait aider dans ce domaine. Au moins, vous saurez que vous ne faites pas empirer les choses.

Donc, au lieu de passer plus de tests comme dans TDD, vous le feriez "mieux se comporter".

Sorte de.

Vous pouvez tester la durée d'exécution et la complexité. Les tests d'exécution devront être un peu indulgents pour permettre la contention sur les ressources système. Mais, dans de nombreux langages, vous pouvez également remplacer ou injecter des méthodes et compter les appels de fonction réels. Et, si vous êtes sûr que votre algorithme actuel n'est pas optimal, vous pouvez introduire un test qui exige simplement que l' sort()invocation soit compare()moins fréquente que l'implémentation naïve.

Ou, vous pouvez comparer sort()sur deux ensembles et vous assurer qu'ils évoluent dans les compare()appels en fonction de la complexité de votre cible (ou à peu près, si vous prévoyez une certaine incohérence).

Et, si vous pouvez théoriquement prouver qu'un ensemble de taille Nne devrait strictement pas exiger plus que des N*log(N)comparaisons, il pourrait être raisonnable de restreindre votre déjà-fonctionnement sort()aux N*log(N)invocations de compare()...

Cependant ...

Le respect d'une exigence de performances ou de complexité ne garantit pas que l'implémentation sous-jacente est {AlgorithmX} . Et je dirais que c'est normalement OK. Peu importe l'algorithme utilisé, à condition que vous atteigniez votre mise en œuvre répond à vos exigences, y compris toute exigence de complexité, de performances ou de ressources importante.

Mais, si vous voulez vous assurer qu'un algorithme particulier est utilisé, vous devrez être plus fastidieux et obtenir beaucoup plus de détails. Des choses comme..

• Veiller à ce que le nombre exact d'appels compare()et swap()(ou autre) soit effectué
• Envelopper toutes les fonctions / méthodes principales et garantir, avec un ensemble de données prévisible, que les appels se produisent exactement dans l'ordre attendu
• Examiner l'état de fonctionnement après chacune des N étapes pour s'assurer qu'il a changé exactement comme prévu

Mais encore une fois, si vous essayez de vous assurer que {AlgorithmX} est utilisé en particulier, il y a probablement des fonctionnalités de {AlgorithmX} que vous vous souciez qui sont plus importantes à tester que si {AlgorithmX} a été réellement utilisé à la fin ...

Gardez également à l'esprit que TDD ne nie pas la nécessité de rechercher, de penser ou de planifier dans le développement de logiciels. Cela ne supprime pas non plus le besoin de remue-méninges et d'expérimentation, même si vous ne pouvez pas facilement affirmer votre recherche sur Google et votre tableau blanc dans votre suite de tests automatisée.