Aller au contenu

Tableaux dynamiques

On va se servir d'un champ mutable pour définir un type 'a dynarray de tableaux dynamiques, c'est-à-dire de tableaux dont la taille pourra changer en ajoutant des éléments dedans à la manière des list de Python.

Pour cela, on va d'abord commencer par définir des fonctions sur les array (qui existent pour beaucoup dans la bibliothèque standard mais c'est surtout l'occasion de s'entraîner).

Préliminaires : fonctions de manipulation de tableaux

Question 1. Écrire une fonction array_blit telle que array_blit tab1 debut1 tab2 debut2 nb copie les nb éléments de tab1 à partir de l'indice debut1 dans le tableau tab2 à partir de l'indice debut2.

On appellera toujours cette fonction en faisant en sorte qu'il n'y ait pas d'accès erronés en mémoire.

Tests 
let t1 = Array.init 5 (fun i -> i) in
let t2 = Array.init 6 (fun i -> i+1) in
array_blit t1 3 t2 1 2;
assert(t2 = [|1;3;4;4;5;6|]);
let t1 = [| 'a';'b';'c' |] in
let t2 = [| 'd'; 'e' |] in
array_blit t1 1 t2 0 2;
assert(t2 = [|'b';'c'|]);
"Valide";;
Corrigé 
let array_blit (tab1:'a array) (debut1:int) 
               (tab2:'a array) (debut2:int) (nb:int) : unit =
    for i = 0 to nb-1 do
        tab2.(debut2 + i) <- tab1.(debut1 + i)
    done

Question 2. Écrire une fonction array_extend telle que l'appel array_extend tab debut nb renvoie un nouveau tableau contenant le même contenu que tab sauf que l'on a rajouté nb éléments à partir de l'indice debut. La valeur des éléments rajoutés n'est pas signifiante.

On suppose que tab est non vide.

Si debut vaut la longueur de tab, les nouveaux éléments sont rajoutés après la recopie de tab.

On utilisera array_blit.

Tests 
let t = Array.init 5 (fun i -> i) in
let t2 = array_extend t 3 5 in
assert(Array.length t2 = 10 
    && Array.sub t2 0 3 = [|0;1;2|] 
    && Array.sub t2 8 2 = [|3;4|]);
let t = Array.init 5 (fun i -> char_of_int (i+97) ) in
let t2 = array_extend t 0 3 in
assert(Array.length t2 = 8 && Array.sub t2 3 5 = t);
let t2 = array_extend t 5 3 in
assert(Array.length t2 = 8 && Array.sub t2 0 5 = t);
"Valide";;
Corrigé 
let array_extend (tab:'a array) (debut:int) (nb:int) : 'a array =
    let n = Array.length tab in
    let tabn = Array.make (n + nb) tab.(0) in
    array_blit tab 0 tabn 0 debut;
    array_blit tab debut tabn (debut + nb) (n - debut);
    tabn

En exécutant le code suivant, vous devriez obtenir [|0; 1; 2; 0; 0; 0; 0; 0; 3; 4|] si vous avez rempli les nouvelles cases avec tab.(0) comme dans le corrigé (seules les trois premières et les deux dernières valeurs sont imposées).

let t = Array.init 5 (fun i -> i)
in array_extend t 3 5

Question 3. Écrire une fonction array_concat telle que l'appel array_concat tab1 tab2 renvoie le nouveau tableau obtenu en plaçant les éléments de tab2 à la suite de ceux de tab1.

Tests 
assert(array_concat [|1;2|] [|3|] = [|1;2;3|]);
assert(array_concat [||] [||] = [||]);
assert(array_concat [||] [|1|] = [|1|]);
assert(array_concat [|1|] [||] = [|1|]);
"Valide";;
Corrigé 
let array_concat (tab1:'a array) (tab2:'a array) : 'a array =
    let n1 = Array.length tab1 in
    let n2 = Array.length tab2 in
    if n1 = 0 then tab2
    else if n2 = 0 then tab1
    else
        let tab = Array.make (n1+n2) tab1.(0) in
        array_blit tab1 0 tab 0 n1;
        array_blit tab2 0 tab n1 n2;
        tab

Attention, quand l'un des deux tableaux est vide, ce corrigé renvoie l'autre tableau lui-même et non une copie.

Question 4. Écrire une fonction array_delete telle que l'appel array_delete tab debut nb renvoie un nouveau tableau obtenu en supprimant nb éléments de tab à partir de l'indice debut.

On suppose que nb > 0 et donc que tab est non vide.

Tests 
assert(array_delete [|1;2;3;4;5;6|] 2 2 = [|1;2;5;6|]);
assert(array_delete [|1;2;3;4;5;6|] 0 3 = [|4;5;6|]);
"Valide";;
Corrigé 
let array_delete (tab : 'a array) (debut : int) 
                 (nb : int) : 'a array =
    let n = Array.length tab in
    let t = Array.make (n - nb) tab.(0) in
    array_blit tab 0 t 0 debut;
    array_blit tab (debut + nb) t debut (n - nb - debut);
    t

Premier type de tableaux dynamiques

On définit le type suivant pour contenir un tableau dynamique. On va devoir réallouer les éléments, donc on aura besoin d'accéder en écriture au tableau qui les contient, le plus simple dans un premier temps est de faire une référence sur un tableau.

Note le type est un type synonyme, par défaut, OCaml va afficher 'a array ref dans ses résultats mais on peut forcer l'affichage de 'a dynarray en spécifiant les types dans les fonctions comme on va le faire en dessous.

type 'a dynarray = 'a array ref

Comme on va définir des tableaux en partant du tableau vide, comme en Python avec [], on peut se permettre de ne pas donner le type des éléments. En fait, contrairement à ce qu'il semble, la valeur v ci-dessous n'a pas un type magique : le 'a sera instancié le plus vite possible, ce qu'on peut voir avec le '_weak1 dans son type.

Attention : vraiment comprendre ces notions de paramètres génériques faibles est trop complexe et dépasse le cadre du cours de CPGE.

let dynarray_init () = ref [||]

let v = dynarray_init ()

v := [|1; 2|]

(* Maintenant v est un int dynarray *)
v

On va maintenant définir des fonctions d'ajout et de suppression d'éléments dans le tableau. Pour cela, on va réallouer le tableau grâce aux fonctions de la partie précédente. Attention : on rappelle que dans array_extend on a supposé le tableau non vide, il faudra donc sûrement traiter ce cas à part.

Question 5. Écrire une fonction dynarray_append telle que l'appel dynarray_append tab x ajoute x à la fin du tableau tab.

Tests 
let t = dynarray_init () in
dynarray_append t 1;
dynarray_append t 2;
dynarray_append t 3;
dynarray_append t 4;
assert(!t = [|1;2;3;4|]);
"Valide";;
Corrigé 
let dynarray_append (tab : 'a dynarray) (x : 'a) : unit =
    let n = Array.length !tab in
    if n = 0 then tab := [|x|]
    else begin
        let t = array_extend !tab n 1 in
        t.(n) <- x;
        tab := t
    end

Question 6. Écrire une fonction dynarray_pop telle que l'appel à dynarray_pop tab supprime le dernier élément de tab et le renvoie.

Tests 
let t = ref [|1;2;3;4|] in
let x = dynarray_pop t in
assert(x = 4 && !t = [|1;2;3|]);
"Valide";;
Corrigé 
let dynarray_pop (tab : 'a dynarray) : 'a =
    let n = Array.length !tab in
    let x = !tab.(n-1) in
    let t = array_delete !tab (n-1) 1 in
    tab := t;
    x

Chaque ajout et chaque suppression recopie tout le tableau : une suite de \(n\) ajouts à partir du tableau vide coûte \(\sum_{k=1}^{n} O(k) = O(n^2)\).

Type efficace pour les tableaux dynamiques

Afin de résoudre les problèmes de complexité observés précédemment, on va définir un nouveau type pour les tableaux en permettant d'avoir un tableau contenant plus de cases que ce qui est vraiment utilisé. Ainsi, si on a un tableau de taille 10 mais qui ne contient que 9 éléments réels, on pourra en temps constant rajouter un élément. Pour cela, on va avoir besoin non seulement de gérer les éléments du tableau, mais aussi un paramètre length donnant la longueur logique, c'est-à-dire le nombre d'éléments signifiants du tableau.

type 'a dynarray = {
    mutable elements : 'a array;
    mutable length : int
}

let dynarray_init () = { elements = [||]; length = 0 }

Question 7. Écrire une fonction dynarray_of_array telle que l'appel dynarray_of_array tab où tab est un array renvoie le dynarray le contenant : on initialisera sa longueur à la longueur de tab.

Tests 
assert(dynarray_of_array [|1;2|] = { elements = [|1;2|]; length = 2 });
"Valide";;
Corrigé 
let dynarray_of_array (tab : 'a array) : 'a dynarray =
    { elements = tab; length = Array.length tab }

Question 8. Écrire des fonctions get et set telles que l'appel get tab i renvoie le \(i\)-ème élément du tableau contenu par tab et l'appel set tab i x place la valeur x dans le tableau tab à l'indice i. On vérifiera que i est un indice valide, c'est-à-dire strictement inférieur à la longueur logique.

Tests 
let d = dynarray_of_array [|1;2|] in
assert(get d 1 = 2);
set d 1 3;
assert(d.elements = [|1;3|]);
"Valide";;
Corrigé 
let get (tab : 'a dynarray) (i : int) : 'a =
    if i < 0 || i >= tab.length then invalid_arg "get";
    tab.elements.(i)

let set (tab : 'a dynarray) (i : int) (x : 'a) : unit =
    if i < 0 || i >= tab.length then invalid_arg "set";
    tab.elements.(i) <- x

Pour ajouter des éléments au tableau, on va regarder s'il y a de la place (t.length < Array.length t.elements) et sinon on va doubler sa taille. Si le tableau contenait 3 éléments, on va en allouer 6 donc 3 de plus, ce qui va permettre de faire 3 ajouts sans réallocation (dont celui en cours).

Attention : quand le tableau est vide, on ne pourra pas doubler sa longueur, on se contente de faire un tableau de taille 1 dans ce cas.

Question 9. Écrire une fonction dynarray_append telle que l'appel dynarray_append tab x ajoute x à la fin du tableau tab avec la stratégie exposée.

Tests 
let t = dynarray_init () in
dynarray_append t 1;
dynarray_append t 2;
dynarray_append t 3;
dynarray_append t 4;
dynarray_append t 5;
assert(Array.sub t.elements 0 5 = [|1; 2; 3; 4; 5|] 
    && t.length = 5);
"Valide";;
Corrigé 
let dynarray_append (tab : 'a dynarray) (x : 'a) : unit =
    let n = Array.length tab.elements in
    if n = 0 then begin
        tab.elements <- [|x|];
        tab.length <- 1
    end
    else begin
        if tab.length = Array.length tab.elements
        then tab.elements <- 
            array_extend tab.elements tab.length tab.length;
        tab.elements.(tab.length) <- x;
        tab.length <- 1 + tab.length
    end

Question 10. Écrire une fonction dynarray_pop telle que l'appel dynarray_pop tab supprime le dernier élément de tab et le renvoie.

On ne supprime rien physiquement, on se contente de changer la valeur length.

Tests 
let t = { elements = [|1;2;3;4;5|]; length = 4 } in
let x = dynarray_pop t in
assert(x = 4 && t.elements = [|1;2;3;4;5|] && t.length = 3);
"Valide";;
Corrigé 
let dynarray_pop (tab : 'a dynarray) : 'a =
    if tab.length = 0 then failwith "tableau vide";
    let x = tab.elements.(tab.length-1) in
    tab.length <- tab.length - 1;
    x

Question 11. Prouver que si on effectue une suite de \(n\) append sur un tableau vide on fait \(O(n)\) opérations élémentaires.

Même question avec des append et des pop.

Corrigé

Un append sans réallocation coûte \(O(1)\). Une réallocation a lieu quand la capacité \(c\) est atteinte, et coûte \(O(c)\) (recopie de \(c\) éléments). Lors de \(n\) ajouts à partir du tableau vide, les capacités successives sont \(1, 2, 4, \dots, 2^k\) avec \(2^k < n\) pour celles qui sont recopiées : le coût total des recopies est \(O(1 + 2 + \dots + 2^k) = O(2^{k+1}) = O(n)\), et le coût total est donc \(O(n)\).

Avec des append et des pop, un pop coûte \(O(1)\) et ne diminue jamais la capacité. Si on effectue \(n\) opérations, la longueur reste inférieure à \(n\), donc la capacité aussi (elle vaut au plus le double d'une longueur atteinte). Les réallocations se font pour des capacités deux à deux distinctes, puissances de 2 et inférieures à \(n\) : leur coût total est encore \(O(n)\).

Si on effectue 1 milliard d'append suivis d'1 milliard de pop, la taille physique sera toujours d'1 milliard d'éléments. Cela semble peu efficace et on aimerait que la taille physique soit toujours proche du nombre réel d'éléments.

Question 12. Comment peut-on modifier dynarray_pop pour s'assurer que le nombre d'éléments réels est toujours proportionnel à la taille physique tout en conservant un temps constant en moyenne ?

Faites la modification et faites une preuve assurant que cela fonctionne.

Corrigé

Diviser la capacité par 2 dès que le tableau est à moitié vide ne convient pas : en alternant append et pop autour de cette limite, on réalloue à chaque opération. On divise donc la capacité par 2 quand le tableau n'est plus rempli qu'au quart :

let dynarray_pop (tab : 'a dynarray) : 'a =
    if tab.length = 0 then failwith "tableau vide";
    let x = tab.elements.(tab.length-1) in
    tab.length <- tab.length - 1;
    let cap = Array.length tab.elements in
    (* on divise la capacité par 2 quand le tableau est rempli au quart *)
    if 4 * tab.length <= cap && cap > 1
    then tab.elements <- Array.sub tab.elements 0 (cap / 2);
    x

En notant \(\ell\) la longueur et \(c\) la capacité, on vérifie que \(c \le 4\ell\) reste vrai après chaque opération dès que \(\ell \ge 1\) (après une division, \(c = 2\ell\)) : la taille physique reste proportionnelle au nombre d'éléments.

Pour la complexité, on utilise la méthode du potentiel (voir le chapitre sur la complexité amortie) avec \(\Phi = |2\ell - c|\), qui est positif et nul pour le tableau vide initial (\(\ell = c = 0\)). Une opération sans réallocation modifie \(\ell\) de 1 donc \(\Phi\) d'au plus 2 : coût amorti \(O(1)\). Juste avant un doublement, \(\ell = c\) donc \(\Phi = c\), et juste après \(\Phi = 2(c+1) - 2c = 2\) : la baisse de \(\Phi\) paie la recopie de \(c\) éléments. Juste avant une division par 2, \(\ell = \frac{c}{4}\) donc \(\Phi = \frac{c}{2}\), et juste après \(\Phi = |\frac{c}{2} - \frac{c}{2}| = 0\) : la baisse de \(\Phi\) paie la recopie des \(\frac{c}{2}\) cases. Le coût amorti de chaque opération est donc \(O(1)\), et une suite de \(n\) opérations coûte \(O(n)\).