Come determinare i casi di test più difficili da testare qualsiasi algoritmo?

Supporrò che stiamo parlando di un algoritmo ragionevolmente complesso, ad esempio quello in cui di solito tiri fuori carta e penna e hai bisogno di un po 'di tempo prima di arrivare allo pseudocodice per una soluzione.

In uno scenario del genere, i casi di test più impegnativi sono i casi limite che probabilmente non hai pensato . Qui, il design basato sui test non può che farti arrivare così lontano, poiché la copertura del test è strongmente limitata dalla tua immaginazione. In questi casi, provo un approccio basato sulle filiali. Provo a creare sequenze di input che colpiranno tutte le possibili variazioni del flusso di controllo e asseriranno proprietà importanti che mi aiutano a credere che l'algoritmo sia effettivamente corretto.

La cosa importante è che per i problemi algoritmici, di solito c'è una densità piuttosto elevata di casi limite. È più facile scoprire cosa sono questi casi limite se si può guardare all'algoritmo, cioè eseguire test whitebox. In TDD, faresti il contrario: idealmente, scrivi tutti i casi di test prima ancora di iniziare a implementare il codice. Tuttavia, se il problema è stato complesso dal punto di vista dell'algoritmo, probabilmente hai già fatto in modo che il tuo algoritmo restituisse la soluzione corretta per tutte le istanze che hai ottenuto con anticipo.

Anche se sono d'accordo con la dichiarazione di Robert Harvey, che lo sviluppo guidato dai test è un approccio utile, spesso ho l'impressione che la gente pensi che con un numero sufficiente di test unitari sul posto siano sicuri e sia loro permesso di smettere di pensare test utili. Questo, penso, è lontano dall'essere vero.

Secondo me la creazione di test ragionevoli è qualcosa tra un'arte e una buona abilità artigiana, dove conoscere gli strumenti esistenti e le migliori pratiche insieme a loro e applicarli correttamente è la parte dell'artigianato. Una buona conoscenza degli errori di programmazione comuni come ingrediente aggiuntivo aiuterà anche a trovare test utili. Ma devi anche capire il problema risolto dall'algoritmo e devi avere un'idea di dove una implementazione rischia di fallire. Tu, almeno in parte, spesso sarai da solo qui. Cercherò di trovare almeno un algoritmo alternativo ed eseguirli contemporaneamente. Spesso ne scegli uno specifico per le prestazioni: nei test automatici puoi utilizzare uno più lento per il controllo dei croos. Qualsiasi cosa ti aiuti è qualcosa che puoi mettere nella scatola delle migliori pratiche.

Senza spendere troppo tempo su di esso, per il problema che hai fornito come esempio, proverei a trovare un modo (automatico) per (a caso) creare (molte) sequenze di lunghezza variabile per le quali posso prevedere il risultato. Quindi inserirli nell'algoritmo e registrare l'input nel caso in cui non riesca. Inoltre, lo farei per un insieme di sequenze fisse (non casuali) come protezione contro le modifiche al codice che potrebbero infrangere il codice. Farei in modo che ci siano sequenze con più di una soluzione e cercare di capire se esistono sequenze con soluzioni sovrapposte e se sì, prova a crearne anche alcune.

Vorrei aggiungere che per me, in quanto matematico, un algoritmo è corretto o sbagliato per almeno un insieme di dati di input ed è qualcosa per cui puoi (spesso) dare prova (il link è scelto più o meno a caso) - ovviamente c'è sempre il fattore umano .... Ma anche se ci credi, non puoi farlo (prova) per l'implementazione di un algoritmo (sufficientemente complesso), che è la cosa che è in realtà sotto test.

Modifica Penso che un esempio sufficientemente chiaro ed elaborato allo stesso tempo possa essere utile. Per questo vorrei attirare la vostra attenzione su "The art of computer programming" di Knuth vol 2, dove sotto il titolo "Gli algoritmi classici" viene presentato un algoritmo che mostra come dividere un intero positivo (arbitrario) con un altro intero positivo . Knuth in realtà fornisce (un po 'difficile da capire) la prova del perché il suo algoritmo è corretto. Una certa parte di quella dimostrazione mostra che esiste un modo semplice per eseguire una determinata attività in quell'algoritmo e un caso eccezionale. Il caso eccezionale (vedi la fase D3 dell'algoritmo D se si vuole veramente cercarlo) si verifica molto raramente e, in realtà, richiede un calcolo più complesso.

Ora, mentre esiste un modo abbastanza ovvio per creare test unitari per questo algoritmo (applicarlo a due interi e quindi eseguire l'operazione inversa per verificare se si arriva da dove si è iniziato) non è assolutamente ovvio come assicurarsi il caso eccezionale è testato. Per prima cosa devi conoscerlo (cioè devi capire i dettagli pelosi della dimostrazione dell'algoritmo), quindi devi trovare i dati per cui si verificherà effettivamente. Fare l'intera catena (trovare l'algoritmo, che in questo caso è fatto per te dall'autore, trovarne una dimostrazione, identificare i casi eccezionali e accertarsi che i dati dei test siano trovati che testano anche questo) non è coperto da qualsiasi tipo di best practice.

Come ha sottolineato @Thomas, la progettazione di buoni casi di test richiede esperienza. Ma c'è una buona notizia per te: puoi impararla, e ci sono molti libri là fuori dove sono descritti approcci sistematici. Ad esempio, uno "classico" è "The Art of Software Testing, Second Edition " di Glenford Myers.

Alcuni esempi di tecniche descritte qui

• test di copertura del codice / test di copertura delle filiali: crea una serie di casi di test in modo che ogni riga di codice sia eseguita, o che ogni ramo possibile sia eseguito (questa è una tecnica white-box per un programma in cui hai dentro il codice sorgente )
• classe di equivalenza: partiziona lo spazio dei dati di input in classi disgiunte e crea almeno un caso di test per ogni classe
• analisi del caso limite: nell'esempio sopra riportato che può significare creare un caso di test con un array vuoto, un array a un elemento, un array a due elementi, un array con solo elementi positivi, solo negativi o solo zeri, ecc.

Quindi, la risposta alla tua domanda è: non c'è solo una "sola" regola empirica, ce ne sono molti, e dovresti dare un'occhiata alla letteratura aggiuntiva per apprenderli.

Il modo migliore che conosco è scrivere programmi usando la metodologia Test-Driven-Development. Scrivendo prima i casi di test e poi solo il codice di scrittura che consente il passaggio dei casi di test, i tuoi algoritmi implementeranno solo i casi di test e pertanto il tuo codice avrà una copertura del 100%.

Questo è un po 'ironico, naturalmente. Scrivere casi di test e codice che supera quei casi di test non garantisce che il tuo codice non avrà un comportamento marginale oltre i casi di test, e non credo ancora che si possa semplicemente far crescere un'architettura sensibile da zero usando solo il rosso -green-refactoring.

La via d'uscita non è trovare i migliori algoritmi di test possibili (anche se è certamente una buona cosa da fare). Piuttosto, utilizzare le migliori pratiche di programmazione e progettare i programmi in modo tale da ridurre al minimo la quantità di comportamenti imprevisti. Imparare a farlo è la vita e l'apprendimento continui di ogni programmatore professionista.

Puoi anche utilizzare strumenti di copertura del codice per identificare i casi di test.