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.
On peut penser à deux implémentations naïves. La première incrémente la case
a[i]
d’un tableauint[] a
à chaque appel deinc(i)
(temps constant) ;cumulative(i)
renvoie la somme desa[j]
pour 0 ≤ j < i (temps linéaire en H − L).La seconde stocke directement les valeurs de tous les
cumulative(i)
, de sorte quecumulative(i)
est calculé en temps constant mais c’estinc
qui s’exécute en temps linéaire.
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[.
Dans la marge de gauche, deux implémentations naïves sont suggérées qui garantissent un temps linéaire pour ces deux opérations.
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, A[
et [A, hi[
pour A = ⌊(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 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(Nlog N). 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(log N).)
Si on note N la longueur de a
, la complexité de countInversionsBest(int[] a)
devra être en O(Nlog N).
Tester le code en exécutant Test33.java puis déposer TD6.java.