Chaînes d'addition en C
Voici un essai de solution du devoir maison numéro 2.
Le code est en C, ce qui est sensiblement normal quand on recherche la
vitesse et que l'algorithme est simple.
Comprendre le C n'est pas bien difficile, quand on connaît Java.
Les deux programmes add et ext2 se compilent à
l'aide de ce fichier Makefile, par les
commandes :
# make add
# make ext2
Jusqu'à vingt
Le programme suit l'énoncé, avec les décisions
d'implémentation suivantes :
-
Les ensembles de (petits) entiers sont codés par des entiers
non-signés. Ici j'utilise une extension de gcc :
long
long
qui correspond aux entiers sur 64 bits
(long
en Java).
On considère donc les ensembles regroupant des entiers compris entre
0 et 63.
Le code contient la définition de type suivante.
typedef unsigned int elem ; // type des éléments (entiers non signés)
typedef unsigned long long set ; // type des ensembles.
/* Exemple d'utlisation, cette fonction renvoie l'ensemble singleton {i} */
set singleton(elem i) {
return ((set)1) << i ;
} |
- Les collections (ensembles d'ensembles) sont donc des ensembles
d'entiers machines. Les Patricia trees sont une structure de
donnée commode et efficace pour représenter de tels ensembles en
machine.
Le principe de ces arbres est que tous les entiers contenus dans un
sous-arbre donné ont des représentations en base deux possédant le
même préfixe spécifique associé au sous-arbre.
J'ai juste traduit en C la réalisation des Patricia trees
de
Jean-Christophe Filliâtre (en Caml), elle même inspirée de
celle de
Chris Okasaki et Andy Gill (en SML).
On peut trouver des descriptions des ces arbres dans les livres
d'algorithmique.
Voici la déclaration du type des noeuds :
typedef struct node {
unsigned int count ;
set p,m ;
struct node *l,*r ;
} node ; |
Le préfixe est p, tandis que m est 2b, où b est
le nombre de bits du préfixe.
Les champs l et r sont respectivement les fils
gauche et droit.
Les feuilles (singletons) sont répérées par un champ m égal à zéro, le
champ p est alors la valeur de l'élément.
Le champ count est utilisé pour la gestion de la mémoire,
c'est le nombre de pointeurs sur une cellule donnée.
Il n'a rien à voir avec la structure de donnée elle-même.
Bref, voici le code add.c.
Il faut bien noter que ce code n'a rien de particulièrement subtil, à
part l'usage des Patricia trees et la gestion mémoire par
comptage de référence qui peut être ignorée en première lecture.
Au delà
L'extension proposée est également réalisée en C, source
ext2.c.
L'idée est ici encore celle de l'énoncé.
Une fonction explore parcours l'arbre « virtuel » de
l'énoncé. Rapellons que les noeuds de cet arbre sont étiquetés par
des entiers qui sont la somme des étiquettes de deux ancêtre.
En outre, les étiquettes croissent quand on descend dans l'arbre.
Ainsi, le sommet de l'arbre étant étiqueté par 1, il n'a qu'un fils
étiqueté par 2, qui a deux fils étiquetés par 3 = 1+2 et 4 =
2+2.
Le type des éléments des chaînes est entier non-signé, comme c'est un
peu long à écrire on le définit comme le type base.
typedef unsigned int base ; |
Voici la signature de explore.
static unsigned int
explore(base d, base n, base *q, stack *st, base *vert, base* slant) |
La fonction explore renvoie un compte des chaînes d'addition.
L'entier d est la profondeur d'exploration ou plutôt la
distance avant d'atteindre les feuilles de l'arbre.
L'entier n est la cible, c'est-à-dire que l'on recherche les
chaînes se terminant par n.
L'argument q est un pointeur vers une case mémoire où ranger
l'étiquette que nous allons trouver.
Les étiquettes des ancêtres sont rangées en mémoire avant notre case,
ainsi *(q-1) (qui veut dire q[-1] !) est l'étiquette du père, *(q-2) est
celle du grand-père, etc. jusqu'au sommet d'étiquette 1.
Les autres arguments correspondent à la gestion d'une pile
(st) et aux diverses optimisations que je n'expliquerais
pas (le premier article cité en référence dans l'énoncé les décrit
largement).
Donc voici une version simplifiée de explore :
static unsigned int explore(base d, base n, base *q, stack *st) { |
Cette version simplifiée est invoquée initialement par une fonction
chain, chargée de trouver les chaine de taille k
aboutissant en n.
static unsigned int chain(base k, base n) {
base t[k+1] ; /* Allocation (en pile) du tableau des étiquettes */
t[0] = 0 ; /* sentinelle */
t[1] = 1 ; /* étiquette du sommet */
return explore(k-1, n, t+2, ...) ;
} |
L'idée, conforme à l'énoncé est d'appeler chain, sur tous les
entiers k successifs à partir des bornes inférieures fonction
de n, et ceci jusqu'à trouver des chaînes.
En gros on aura :
base k = borne(n)+1 ;
unsigned int r = 0 ;
do {
r = chain(k,n) ;
k++ ;
} while (r == 0) ; |
En sortie de boucle, k-2 vaut la taille des plus petites
chaînes d'addition aboutissant en n
(il faut soustraire 1 à cause de l'incrément supplémentaire
k++ et encore 1 parceque le paramètre k de explore
est en fait la taille de chaîne plus 1).
Mais venons-en au code de la fonction explore.
On s'interesse d'abord au cas de base de la récursion :
nous allons construire une chaîne de la taille voulue et dont le
dernier élément est n.
if (d <= 1) { /* Nous sommes arrivés */
base *t, *tt ;
for (t = q-1 ; ; t--) { /* parcourir les ancêtres jeune -> vieux */
base x = *t ; /* x est l'étiquette d'un ancêtre */
if (2*x < n) /* fini car x est trop petit */
break ;
for (tt = t ; ; tt--) { /* *tt est un autre ancêtre (+ vieux que x) */
base s = x + *tt ; /* nouvelle étiquette potentielle */
if (s < n) break ; /* *tt trop vieux, fini */
if (s == n) { /* trouvé ! */
return 1 ;
}
}
}
return 0 ; /* pas trouvé */ |
À part quelques astuces de contrôle (break
,
return
), le code n'est pas trop compliqué.
Un point notable est l'utilisation de la décroissance des étiquettes
pour abréger la recherche d'une somme valant n.
Cela fonctionne totalement grâce à une sentinelle, la case
mémoire qui précède l'étiquette du sommet contient zéro.
Et donc on finira toujours par avoir 2 x < n (si n > 0),
ou s = x + *tt ≤ n (par construction x < n comme on va le voir).
Reste le cas n=1, d=1 traité un peu bizarrement (chaîne {0, 1,
1}), mais bon.
Voici maintenant l'étape inductive.
On va d'abord calculer toutes les sommes de deux étiquettes d'ancêtres
et les ranger à la queue-leu-leu dans une zone de mémoire ad-hoc.
La gestion de cette zone de mémoire st ne sera pas décrite,
on peut y ajouter un nouvel entier par st = insert(st, s) ;
On saura ensuite la parcourir de st->fp à st->sp-1.
On limite les sommes à un intervalle
pertinent compris entre la limite basse low et la limite
haute high.
Soit prev l'étiquette du père.
Sans optimisation on peut poser low = prev+1 et high
égal au minimun de 2*prev et n-1.
Donc nous pouvous calculer et insérer toutes les sommes de deux
ancêtres, le code est en fait très similaire à celui du cas de base.
for (t = q-1 ; ; t--) {
base x = *t ;
base s ;
if (2*x < low) break ;
for (tt = t ; ; tt--) {
s = x + *tt ;
if (s <= high) break ;
}
while (s >= low) {
st = insert(st, s) ;
s = x + *--tt ;
}
} |
Un fois de plus on utilise la présentation décroissante des ancêtres,
mais le principal attrait de cette présentation est de faciliter
l'utilisation des optimisations qui conduisent à un low plus
grand.
Il peut sembler un peu inutile de calculer l'ensemble des sommes, puis
de parcourir cet ensemble, mais cela permet de ne pas procéder à
plusieurs appels récursifs quand un entier donné correspond à
plusieurs sommes d'ancêtres.
Reste à parcourir les étiquettes possibles :
r = 0 ;
tt = st->sp ;
for (t = st->fp ; t < tt ; t++) {
*q = *t ; /* Ranger l'étiquette courante à sa place */
r += explore(d-1, n, q+1, st) ; /* notez d-1, q+1 */
} |
Ainsi, en sortie de boucle, r vaut le nombre de chaînes
trouvées. Si on ne cherche qu'une chaîne. On peut aussi écrire
tt = st->sp ;
for (t = st->fp ; t < tt ; t++) {
*q = *t ;
if (explore(d-1, n, q+1, st))
return 1 ;
} |
Voilà ces quelques explications devraient permettre d'aborder le
programme complet ext2.c.
Le code le plus tordu est celui de la gestion mémoire, un tel code
n'aurait pas de raison d'apparaître en Java.
Le programme est en fait assez polyvalent, il prend les options
suivantes.
usage: ./ext2 [-vVcla] [n]
-v, donne des diagnostics
-V, encore plus de diagnostics
-c, optimisations de type c (type a par défaut)
-l, affiche les chaînes d'additions
-a, affiche les tableaux c et d de l'énoncé
Ce document a été traduit de LATEX par
HEVEA.