Comment tester l'implémentation des algorithmes?

Question

Je pense à tester la mise en œuvre de certains algorithmes

Si vous pensez à un TDD/focus BDD ... un test serait

Scenario: doubling search 
Given an ordered array "[2,3,4,5,6,7]" 
When I look for "4" with "doubling search" in it 
Then the result must be "2" 

Je veux vous assurer que mon algorithme va bien ... alors, comment testeriez-vous une implémentation d'algorithme?

Answer 1

Vous testez chaque implémentation d'un algorithme de la même manière: prenez une entrée, calculez à la main votre sortie attendue et comparez-la à la sortie fournie par l'algorithme. Si vous faites cela dans un langage avec des interfaces, vous pouvez avoir un test générique prendre un paramètre d'interface de type, et il doit être appelé par vos tests réels qui passent dans vos implémentations. Cela garantit que tous les algorithmes subissent le même test en fonction de leur interface.

// double search implemented by using the search and multiplying by 2 
algorithm multDoubleSearch 
    define input array 
    define input search 

    for each i in array 
     if i = search * 2 
      return index of i 
    end 
    return -1 
end. 

// double search implemented by dividing the values by 2 
algorithm divDoubleSearch 
    define input array 
    define input search 

    for each i in array 
     if i/2 = search 
      return index of i 
    end 
    return -1 
end. 


test mytest 
    define array {2 3 4 5 6 7} 
    define search 2 

    define resultMult = multDoubleSearch(array,search) 
    assert resultMult == 2 // 4 is index 2, assuming 0 indexed 

    define resultDiv = divDoubleSearch(array,search) 
    assert resultDiv == 2 // 4 is index 2, assuming 0 indexed 
end. 

Answer 2

Eh bien cela dépend de ce que vous avez sous la main. En dehors des tests habituels où vous fournissez les entrées et les sorties manuellement pour tester les cas d'angle et quelques autres entrées (voir JUnit ou une structure similaire dans n'importe quel langage populaire), vous pouvez également écrire une version inefficace mais simple de votre algorithme (ou pour être exact tout ce qui produit les mêmes résultats, généralement pas exactement le même algorithme) et tester contre cette version, soit pour toutes les entrées possibles ou si cela n'est pas possible avec un Fuzztester et une Randomisation. Un exemple pour ce dernier serait de tester un algorithme de tri complexe (disons heapsort) par rapport à SelectionSort. Cela fonctionne également bien si vous optimisez le code et que vous disposez déjà d'une version testée et testée (ce qui est en soi un problème récursif). Dans votre cas particulier, vous pourriez simplement comparer votre version à une simple recherche binaire - ce que la bibliothèque standard a déjà - créant des tableaux de taille aléatoire avec une entrée aléatoire ne devrait pas non plus poser de problème.