Résoudre un algorithme dichotomique
Dans plusieurs projets récents, j'ai été amené à réfléchir à la résolution d'un algorithme constitué d'une succession d'étapes dichotomiques.
Évidemment un enchainement de if / else ... pourrait fonctionner mais il m'a semblé plus intéressant d'essayer de généraliser une façon d'implémenter ce genre d'algorithme.
Le principe général est de représenter cet algorithme sous forme d'un tableau dont les clés sont les méthodes successives utilisées dans la résolution de l'algorithme ou les réponses qui permettent de conclure.
On aura donc une classe qui sera notre resolver, une interface qui impose l'implémentation de méthodes dans notre resolver et une classe représentant l'algorithme et implémentant les méthodes de résolution.
Vous pouvez récupérer les classes Resolver et ResolverInterface avec la commande composer require frvaillant/dichotomic Vous pouvez ensuite créer la classe de votre algorithme
use Dichotomic\Resolver; class BirdAlgo extends Resolver { }
Toutes les explications sont ci-dessous et le dépot github est ici
Passons à la pratique
Imaginons donc l'algorithme suivant qui vise à déterminer une espèce d'oiseau (simplifié, que les ornithologues me pardonnent) :
L'oiseau a t il un bec crochu ?
- Si oui, est il nocturne ?
- Si oui, a t il des aigrettes sur la tête ?
- Si oui, c'est un hibou
- Si non, c'est une chouette
- Si non a t il des ailes pointues ?
- Si oui c'est un faucon
- Si non c'est un aigle
- si non, tant pis ...
Notre algorithme pourrait donc ressembler à ça (je mets le nom des méthodes en français pour plus de compréhension) :
$algo = [
'aUnBecCrochu' => [
true => [
'estNocturne' => [
true => [
'aDesAigrettes' => [
true => 'ended:hibou',
false => 'ended:chouette'
]
],
false => [
'aDesAilesPointues' => [
true => 'ended:faucon',
false => 'ended:aigle'
]
]
]
],
false => 'ended:null'
]
];
Les outils
Une interface
interface ResolverInterface
{
/**
* function to resolve algorithm
*
* @return void
*/
public function execute(): void;
/**
* Parse algotithm and check if necessary methods are written
*
* @throws \Exception
*/
public function checkMethods();
}
Et une classe abstraite
Cette classe possède plusieurs méthodes dont deux sont essentielles :
private function listUnavailableMethods()
Cette méthode liste les éventuelles méthodes nécessaires à la résolution de l'algorithme qui ne seraient pas implantées dans la classe fille. La méthode checkMethods() vérifiera que le retour de cette méthode est nul.
Et la méthode ...
public function execute(): void
... qui exécute de manière itérative toutes les étapes de l'algorithme.
abstract class Resolver implements ResolverInterface
{
const SEPARATOR = ':';
/**
* Have to be described in children
* $algo is an array describing algorithm to resolve
*
* @var array $algo
*/
protected $algo;
public function __construct()
{
$this->checkMethods();
}
/**
* List all methods needed to be used in $algo and check if
* all methods are created in child class
*
* @return array
*/
private function listUnavailableMethods(): array
{
$unavailableMethodsList = [];
foreach( new RecursiveIteratorIterator(
new RecursiveArrayIterator($this->algo),
RecursiveIteratorIterator::SELF_FIRST)
as $algoKey => $value) {
// By default, key is the name of a method
$methodName = $algoKey;
// Check if method needs parameters
if (strstr($algoKey, self::SEPARATOR)) {
list($methodName, $parameter) = explode(self::SEPARATOR, $algoKey);
}
// If algo is a method and if method doesn't exist in child
if (is_string($algoKey) && !method_exists($this, $methodName)) {
$unavailableMethodsList[] = $methodName;
}
}
return $unavailableMethodsList;
}
/**
* Checks if all necessary methods are implemented in child class in terms of $algo
* and if not ...
*
* @throws \Exception
*/
public function checkMethods()
{
if (count($this->listUnavailableMethods()) > 0) {
$message = 'Vous devez implémenter toutes les méthodes nécessaires à résoudre votre algorithme';
$message .= ' Les méthodes ' . implode('(), ', $this->listUnavailableMethods()) . '() sont manquantes';
throw new \Exception($message);
}
return true;
}
/**
* this method iterates array $algo and execute methods whose name are same as array keys
* and then reduce the array in terms of results of the method;
* In the above example, execute colors().
* If result is true, then execute blue();
* if result of blue() is true, then execute light() ...
*
* $a = [
* 'colors' => [
* true => [
* 'blue' => [
* true => 'light',
* false => 'dark'
* ]
* false => 'black'
* ]
* ];
*
* @throws \Exception
*/
public function execute(): void
{
if (!$this->checkMethods()) {
return;
}
$step = $this->algo[array_key_first($this->algo)];
$key = array_key_first($this->algo);
if (!is_array($step[$this->{$key}()])) {
// Function name is the key with sometimes some parameters
$functionName = $this->getFunctionName($step[$this->{$key}()]);
$param = $this->getFunctionParameters($step[$this->{$key}()]);
// Then execute function
$this->{$functionName}($param);
} else {
// We reduce $algo
$this->algo = $step[$this->{$key}()];
// And then restart
$this->execute();
}
}
/**
* @param string $step
* @param string $wanted
* @return string
*
* This methods separate the name of a function and its parameter
* We use ':' as separator
*/
private function getMembers(string $step, string $wanted): string
{
list($functionName, $parameter) = explode(self::SEPARATOR, $step);
return ${$wanted};
}
/**
*
* returns the name of the method to use by removing parameters
*
* @param string $function
* @return string
*/
private function getFunctionName(string $function): string
{
if (!strstr($function, self::SEPARATOR)) {
return $function;
}
return $this->getMembers($function, 'functionName');
}
/**
* Returns parameter of the method by removing method name
*
* @param string $function
* @return string|null
*/
private function getFunctionParameters(string $function): ?string
{
if (!strstr($function, self::SEPARATOR)) {
return null;
}
return $this->getMembers($function, 'parameter');
}
Créer la classe BirdAlgo
J'ai mis des résultats dans chacune des méthodes de telle sorte que si vous utilisez ces quelques lignes de code, vous devriez voir afficher "chouette" à la fin.
class BirdAlgo extends Resolver
{
private $result;
protected $algo = [
'aUnBecCrochu' => [
true => [
'estNocturne' => [
true => [
'aDesAigrettes' => [
true => 'ended:hibou',
false => 'ended:chouette'
]
],
false => [
'aDesAilesPointues' => [
true => 'ended:faucon',
false => 'ended:aigle'
]
]
]
],
false => 'ended:null'
]
];
protected function aUnBecCrochu(): bool
{
// Ce qu'il faut pour tester si l'oiseau a un bec crochu
return true;
}
protected function estNocturne(): bool
{
// Ce qu'il faut pour tester si l'oiseau est nocturne
return true;
}
protected function aDesAigrettes(): bool
{
// Ce qu'il faut pour tester si l'oiseau a des aigrettes
return false;
}
protected function aDesAilesPointues(): bool
{
// Ce qu'il faut pour tester si l'oiseau a des ailes pointues
return true;
}
protected function ended($result)
{
// Retourne le résultat $result de l'algorithme
$this->result = $result;
}
public function getResult(): void
{
return $this->result;
}
}
Et pour utiliser tout cela
$algo = new BirdAlgo(); $algo->execute(); echo $algo->getResult();
Voilà, Cela permet de mettre en place la résolution d'un algorithme dichotomique de manière assez simple. N'hésitez pas à commenter, il y a surement moyen d'améliorer tout cela :-)