Kata

Kata Chop en C++

Le Kata Chop est le problème classique de la recherche d’un élément dans un tableau trié. Dans ce Kata j’ai décidé d’utiliser l’environnement de compilation bjam et boost unit test, qui sont particulièrement simples à mettre en oeuvre.


Cela donnera l’occasion d’en produire une variante utilisant Makefile un autre jour.

Pour lancer les tests, rien de plus simple. On enregistre le fichier Jamroot ci dessous à la racine du projet et on tape bjam (installé par boost build, et il faut aussi la library boost unit test bien entendu). Le programme compile et les tests sont lancés.

Fichier Jamroot

import os ;
project Chop : requirements <include>/usr/include
 : default-build debug ;
# How to use predefined boost build target ?
lib libboost_unit_test : 
 : <name>boost_unit_test_framework-mt <link>static ;
import testing ;
unit-test test_chop 
 : test_chop.cpp chop.cpp libboost_unit_test 
 : <variant>debug ;

Définition du Kata

La fonction chop prend en entrée:

  • un nombre d’éléments
  • un pointeur vers le tableau qui les contient
  • l’élément recherché

elle retourne

  • la position de l’élément s’il est trouvé,
  • -1 si l’élément recherché n’est pas trouvé.

Fichier : chop.hpp

int chop(int n, int * data, int key);

Premier test : on ne trouve jamais

Le premier test est trivial : dans un tableau vide on ne trouve jamais l’élément

Fichier : test_chop.hpp

#define BOOST_AUTO_TEST_MAIN
#define BOOST_TEST_MODULE TestChop
#include 

#include "chop.hpp"

BOOST_AUTO_TEST_CASE(TestChopEmpty)
{
    int data[0];
    BOOST_CHECK_EQUAL(-1, chop(0, data, 10));
}

L’implémentation est directe

Fichier chop.cpp

#include "chop.hpp"

int chop(int n, int * data, int key){
    return -1;
}

Second test on trouve l’élément dans un tableau à une case

Le deuxième test, le plus simple qui échoue, consiste à fournir un tableau
contenant 1 élément seulement : l’élément recherché. On le trouve à la position
zéro.

BOOST_AUTO_TEST_CASE(TestChopFound)
{
    int data[1] = {10};
    BOOST_CHECK_EQUAL(0, chop(1, data, 10));
}
#include "chop.hpp"

int chop(int n, int * data, int key){
    switch (n){
    case 0:
        return -1;
    case 1:
        return 0;
    }
}

Evidemment l’implémentation à ce niveau échoue lorsque l’élément n’est pas trouvé, comme le montre le test ci-dessous.

BOOST_AUTO_TEST_CASE(TestChopNotFound)
{
    int data[1] = {20};
    BOOST_CHECK_EQUAL(-1, chop(1, data, 10));
}

Ce qu’on corrige facilement comme suit.

#include "chop.hpp"

int chop(int n, int * data, int key){
    switch (n){
    case 0:
        return -1;
    case 1:
        return data[0] == key?0:-1;
    }
}

Tester avec deux éléments

Les tests sont ensuite poursuivis sur la même voie avec un tableau à deux éléments
ou l’on trouve l’élément en position 2 (on peut faire un fake et renvoyer 1).
… puis ou on ne trouve pas cet élément du tout.

BOOST_AUTO_TEST_CASE(TestChopTwoItemsFoundPos2)
{
    int data[2] = {10, 20};
    BOOST_CHECK_EQUAL(1, chop(2, data, 20));
}

BOOST_AUTO_TEST_CASE(TestChopTwoItemsNotFound)
{
    int data[2] = {10, 30};
    BOOST_CHECK_EQUAL(-1, chop(2, data, 20));
}

La méthode la plus simple qui me vienne à l’esprit pour faire passer le test
est un simple appel récursif à chop en travaillant sur la seconde moitié du
tableau.

#include "chop.hpp"

int chop(int n, int * data, int key){
    switch (n){
    case 0:
        return -1;
    case 1:
        return data[0] == key?0:-1;
    default:
        int res = chop(n/2+(n&1), data+n/2, key);
        return  (res == -1)?-1:res+n/2;
    }
}

Nouveau test qui échoue, l’élément est là, mais dans la première partie du tableau:

BOOST_AUTO_TEST_CASE(TestChopTwoItemsFoundInFirstPartOfArray)
{
    int data[2] = {20, 30};
    BOOST_CHECK_EQUAL(0, chop(2, data, 20));
}

Pour le faire passer il suffit bien entendu de regarder si l’élément est
dans la première partie du tableau s’il n’est pas trouvé dans la seconde.

#include "chop.hpp"

int chop(int n, int * data, int key){
    switch (n){
    case 0:
        return -1;
    case 1:
        return data[0] == key?0:-1;
    default:
        int res = chop(n/2+(n&1), data+n/2, key);
        if (res == -1){
            return chop(n/2, data, key);
        }
        return  (res == -1)?-1:res+n/2;
    }
}

Fini ?

A cet instant je me rend compte que le problème est entièrement traité et que
je peux essayer de faire passer un test de recette, que je fais un peu exhaustif au cas ou j’aurais oublié des choses.

BOOST_AUTO_TEST_CASE(TestChopRecette)
{
    int data[20] = {1, 2, 3, 3, 3, 5, 5, 5, 7, 8, 8, 8, 8, 9, 10, 14, 20, 20, 20, 20};
    BOOST_CHECK_EQUAL(-1, chop(20, data, 0));
    BOOST_CHECK_EQUAL( 0, chop(20, data, 1));
    BOOST_CHECK_EQUAL( 1, chop(20, data, 2));
    BOOST_CHECK_EQUAL( 4, chop(20, data, 3));
    BOOST_CHECK_EQUAL(-1, chop(20, data, 4));
    BOOST_CHECK_EQUAL( 7, chop(20, data, 5));
    BOOST_CHECK_EQUAL(-1, chop(20, data, 6));
    BOOST_CHECK_EQUAL( 8, chop(20, data, 7));
    BOOST_CHECK_EQUAL(12, chop(20, data, 8));
    BOOST_CHECK_EQUAL(13, chop(20, data, 9));
    BOOST_CHECK_EQUAL(14, chop(20, data, 10));
    BOOST_CHECK_EQUAL(-1, chop(20, data, 11));
    BOOST_CHECK_EQUAL(-1, chop(20, data, 12));
    BOOST_CHECK_EQUAL(-1, chop(20, data, 13));
    BOOST_CHECK_EQUAL(15, chop(20, data, 14));
    BOOST_CHECK_EQUAL(-1, chop(20, data, 15));
    BOOST_CHECK_EQUAL(-1, chop(20, data, 16));
    BOOST_CHECK_EQUAL(-1, chop(20, data, 17));
    BOOST_CHECK_EQUAL(-1, chop(20, data, 18));
    BOOST_CHECK_EQUAL(-1, chop(20, data, 19));
    BOOST_CHECK_EQUAL(19, chop(20, data, 20));
    BOOST_CHECK_EQUAL(-1, chop(20, data, 21));
}

Notons que l’implémentation obtenue n’est pas pour le moment une recherche dichotomique (et fonctionne d’ailleurs parfaitement sur un tableau non trié, comme un test permet de s’en assurer). On touche là à l’un des inconvénients du TDD, rien dans le TDD ne prend en compte l’aspect algorithmique du problème, la fonction est une boite noire et l’algorithme est indifférent. Notons aussi qu’on est parvenu à une solution pour une taille de problème si petite que l’effet d’un algorithme dichotomique est insensible.

Plusieurs pistes pour essayer de remédier à ces inconvénients:

  • – s’imposer des contraintes supplémentaires lors de l’implémentation, dans le cas présent pour obtenir un algorithme dichotomique il faudrait par exemple imposer un seul appel récursif au lieu de deux.
  • – essayer de faire rentrer la complexité en tant que paramètre du problème … pas toujours évident en pratique.
  • – essayer d’améliorer l’algorithme via des techniques de transformation de programme.

Refactorer vers la dichotomie

Dans le cas présent, il n’est pas très compliqué de transformer l’algorithme pour
le rendre récursif, une simple comparaison entre le premier item de la
seconde moitié du tableau et la clé permet de savoir a priori si on doit
chercher un item dans la partie droite ou la partie gauche du tableau.

#include "chop.hpp"
#include 

int chop(int n, int * data, int key){
    switch (n){
    case 0:
        return -1;
    case 1:
        return data[0] == key?0:-1;
    default:
        if (key >= data[n/2]){
            return n/2+chop(n/2+(n&1), data+n/2, key);
        }
        else {
            return chop(n/2, data, key);
        }
    }
}

Sauvé par la recette

La transformation a cependant introduit un bug qui fait échouer le test de recette.
On simplifie le cas de test qui échoue.

BOOST_AUTO_TEST_CASE(TestChop2ItemsNotFoundBigger)
{
    int data[20] = {1, 3};
    BOOST_CHECK_EQUAL(-1, chop(2, data, 4));
}

Une fois isolée la correction est simple.
Si la recherche échoue, calculer une position d’item en ajoutant n/2 est une erreur.
Ce n’est d’ailleurs pas ce qui était fait dans la version avant refactoring.

#include "chop.hpp"

int chop(int n, int * data, int key){
    switch (n){
    case 0:
        return -1;
    case 1:
        return data[0] == key?0:-1;
    default:
        if (key >= data[n/2]){
            int res = chop(n/2+(n&1), data+n/2, key);
            return (res == -1)?-1:res+n/2;
        }
        else {
            return chop(n/2, data, key);
        }
    }
}
Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s