Le coût de @, mesuré

let rec plage_lente n = if n = 0 then [] else plage_lente (n - 1) @ [n]

let plage_rapide n =
  let rec aux i acc = if i = 0 then acc else aux (i - 1) (i :: acc) in
  aux n []

Le calcul. l1 @ l2 reconstruit toute l1 : son coût est $\Theta (|l_1|)$, et l'annexe demande explicitement de le savoir. Dans plage_lente, l'appel de rang $k$ concatène une liste de $k-1$ éléments : le total vaut

$$\sum _{k=1}^n(k-1)=\frac{n(n-1)}{2}=\Theta (n^2).$$

Dans plage_rapide, chaque tour fait un seul ::, en $\Theta (1)$ : le total est $\Theta (n)$.

La mesure (interpréteur ocaml 5.4, temps processeur) :

n =   5000   lente   0,227 s   rapide  0,0001 s
n =  10000   lente   0,976 s   rapide  0,0002 s
n =  20000   lente   4,702 s   rapide  0,0003 s
n =  40000   lente  25,100 s   rapide  0,0016 s

Chaque doublement de $n$ multiplie le temps de plage_lente par environ quatre — $4,3$, puis $4,8$, puis $5,3$ : c'est la signature d'un coût quadratique. À $n=40000$, l'écart atteint un facteur $15000$.

Pourquoi @ recopie. Une liste est une chaîne de cellules immuables, et l'on ne peut pas modifier la dernière cellule de l1 pour la faire pointer vers l2 : elle est peut-être partagée par une autre liste. Il faut donc refaire toutes les cellules de l1. Celles de l2, en revanche, ne sont pas touchées : elles sont simplement partagées.

La règle qui en découle, et qui vaut pour tout le livre : on accumule en tête et l'on renverse une fois à la fin, jamais en queue dans une boucle. Le chapitre chap:sequentielles y revient avec les files.