INF411 · TD6
Exprimez-vous
L’objectif de ce TD est d’implémenter une nouvelle structure de données, les arbres de Fenwick, et de voir comment ils peuvent être utilisés pour calculer rapidement le nombre d’inversions dans un tableau.
Pour commencer:
Créer un nouveau projet “TD6” (menu File → New → Java project…).
Télécharger TD6.zip et extraire les fichiers dans le dossier du projet.
Dans cet exercice, on va construire une structure de données, appelée arbre de Fenwick, qui représente un tableau d’entiers avec des indices dans [L, H[ et qui permet d’exécuter les deux opération suivantes en temps O(log(H−L)) :
void inc(int i)
i
du tableau représenté par
this
; ne fait rien si i
n’est pas dans [L, H[.
int cumulative(i)
this
avec des indices dans ] − ∞, i[ ∩ [L, H[.
On peut penser à deux implémentations naïves :
a[i]
d’un tableau
int[] a
à chaque appel de inc(i)
(temps
constant) ; cumulative(i)
renvoie la somme des
a[j]
pour 0 ≤ j < i (temps
linéaire en H − L).cumulative(i)
, de sorte que cumulative(i)
est
calculé en temps constant mais c’est inc
qui s’exécute en
temps linéaire.class Fenwick {
private final Fenwick left;
private final Fenwick right;
private final int lo;
private final int hi;
private int acc;
}
Un arbre de Fenwick sur l’intervalle [L, H[ est défini comme
suit. C’est un arbre binaire équilibré où chaque nœud a 0 ou 2
sous-arbres. Chaque nœud représente un intervalle. La racine correspond
à l’intervalle [L,H[
. Puis, pour tout nœud correspondant à
l’intervalle [lo,hi[
:
hi-lo > 1
, alors le nœud a 2 sous-arbres qui
correspondent respectivement aux deux intervalles disjoints
[lo, mid[
et [mid, hi[
pour mid = ⌊(lo+hi)/2⌋.hi-lo = 1
, alors le nœud est une feuille et
correspond à l’élément d’indice lo
du tableau.Chaque nœud d’un arbre de Fenwick stocke une valeur (représentée par
le champ acc
). Celle-ci est égale à la somme des valeurs
des cases du tableau dont les indices sont dans [lo,hi[
. En
particulier, les feuilles contiennent juste la valeur de la case du
tableau correspondante.
Le schéma ci-dessous illustre un arbre de Fenwick sur l’intervalle [0, 19[ représentant le tableau [2,2,3,1,0,0,1,1,2,0,1,3,4,2,0,0,2,1,3].
Toutes les méthodes de cette partie seront implémentées dans la
classe Fenwick
du fichier TD6.java
.
class Fenwick {
...
Fenwick(int lo, int hi) {
/* TODO */
}
}
Compléter le constructeur Fenwick(int lo, int hi)
qui
construit l’arbre de Fenwick associé au tableau dont les indices sont
dans [lo, hi[
et où toutes les cases ont pour valeur 0 (on
supposera toujours que lo
< hi
).
Il contiendra des appels récursifs pour construire les sous-arbres, le cas échéant.
Le champ acc
dans la classe Fenwick
permet
de stocker la valeur associée au nœud.
Tester le code en exécutant Test21.java puis déposer TD6.java.
get
Pour se familiariser avec la structure de l’arbre, on peut, par exemple, chercher les feuilles de l’arbre comme dans un arbre binaire de recherche (voir les diapos de l’amphi 5). On peut le faire itérativement ou récursivement.
class Fenwick {
...
get(int i) {
Fenwick /* TODO */
}
}
inc
On veut maintenant implémenter la méthode inc
. Un appel
inc(i)
incrémente les accumulateurs de tous les nœuds de
l’arbre associés à un intervalle contenant i
. L’appel ne
fait rien si i
n’est pas dans [lo, hi[
. On
implémentera cette méthode avec des appels récursifs.
Le schéma ci-dessous illustre l’appel inc(12)
. Les
flèches jaunes représentent les appels récursifs. Les nœuds jaunes ont
reçu un appel inc(12)
, incrémenté leurs compteurs et
transmis l’appel à leurs sous-arbres. Les nœuds beiges ont reçu un appel
inc(12)
mais n’ont rien fait.
class Fenwick {
...
void inc(int i) {
/* TODO */
}
}
cumulative
La méthode cumulative(i)
renvoie la somme des éléments
aux indices strictement inférieurs à i
du tableau
représenté par l’arbre. On remarque que si le nœud courant a des
sous-arbres, alors cumulative(i)
est égal à
left.cumulative(i) + right.cumulative(i)
. Mais selon la
valeur de i
un calcul sans récursion est parfois
possible.
Le schéma ci-dessous illustre l’appel cumulative(13)
. Il
renvoie 21, la somme des nœuds jaunes (12+1+3+5), qui est aussi la somme
des feuilles numérotées de 0 à 12. Les flèches jaunes représentent les
appels récursifs. Les nœuds jaunes et beiges n’ont pas eu besoin de
récursion pour renvoyer le résultat.
class Fenwick {
...
int cumulative(int i) {
/* TODO */
}
}
On va maintenant utiliser les arbres de Fenwick pour dénombrer
efficacement les inversions dans un tableau. Étant donné un
tableau tab
dont les indices sont compris dans
[0,n[
, on dit que la paire d’indices {i,j}
forme une inversion si i<j
et
tab[i]>tab[j]
.
Par exemple dans le tableau [5,-2,10,3]
, il y a 3
inversions qui correspondent aux paires d’indices {0,1}
,
{0,3}
et {2,3}
(qui correspondent
respectivement aux paires de valeurs {5,-2}
,
{5,3}
et {10,3}
).
Toutes les méthodes de cette partie seront implémentées dans la
classe CountInversions
du fichier
TD6.java
.
class CountInversions {
...
static int countInversionsNaive(int[] a) {
/* TODO */
}
}
On va maintenant utiliser les arbres de Fenwick pour compter plus
efficacement le nombre d’inversions dans un tableau a
. On
procède de la manière suivante.
Commencer par créer un arbre de Fenwick fen
sur
l’intervalle [min,max+1[
où min
et
max
sont respectivement le min et le max des valeurs
stockées dans les cases de a
.
Parcourir ensuite a
de droite à gauche et quand la
case i
est explorée, incrémenter la valeur de la case
d’index a[i]
dans fen
. On peut remarquer
qu’au moment où on explore la case i
, le nombre
fen.cumulative(a[i])
est égal au nombre d’éléments
a[j]
, tels que j>i
et
a[j]<a[i]
, convainquez-vous en!
class CountInversions {
...
static int countInversionsFen(int[] a) {
/* TODO */
}
}
En utilisant les remarques ci-dessus, compléter la méthode
countInversionsFen(int[] a)
qui prend un tableau d’entiers
en argument et renvoie son nombre d’inversions.
Si on note N = a.length
et
span = max(a)-min(a)
, alors la complexité de cette méthode
devra être en O(span+N⋅ log(span)).
Tester le code en exécutant Test32.java puis déposer TD6.java.
L’algorithme utilisé dans la partie précédente n’est pas efficace si
la valeur de span
pour a
est grande par
rapport à la taille de a
, par exemple si
a=[-10000,9999,2,350654,10]
. Pour améliorer sa complexité,
on va utiliser la remarque suivante : le nombre d’inversions d’un
tableau ne dépend que de l’ordre relatif de ses éléments et pas de leur
valeur.
Par exemple a=[-10000,9999,2,350654,10]
et
b=[0,3,1,4,2]
ont le même nombre d’inversions,
convainquez-vous en!
Étant donné un tableau a
, on va donc d’abord créer
un tableau b
de même longueur que a
, dont les
valeurs des cases seront comprises entre 0
et
a.length-1
et tels que l’ordre relatif des cases dans
a
et dans b
soit le même.
Ensuite on appliquera la méthode countInversionsFen
au tableau b
.
class CountInversions {
...
static int countInversionsBest(int[] a) {
/* TODO */
}
}
En utilisant les remarques ci-dessus, compléter la méthode
countInversionsBest(int[] a)
qui prend un tableau d’entiers
en argument et renvoie son nombre d’inversions.
On pourra utiliser les méthodes suivantes de la classe
Arrays
:
int[] copyOf(int[] a, int n)
: qui renvoie un
tableau de longueur n
, rempli avec les valeurs
a[0]
,…,a[n-1]
.
void sort(int [] a)
: qui trie le tableau
a
. Attention, cette méthode modifie a
! (Si on note N la longueur de
a
, la complexité de cette méthode est en O(NlogN). Plus
d’infos sur les tris la semaine prochaine !)
int binarySearch(int[] a, val)
: qui prend en
argument un tableau trié et qui renvoie un entier
i
tel que a[i]=val
. (Si on note N la longueur de a
, la
complexité de cette méthode est en O(logN).)
Si on note N la longueur de
a
, la complexité de
countInversionsBest(int[] a)
devra être en O(NlogN).
Tester le code en exécutant Test33.java puis déposer TD6.java.