(* ===================================================== *)
(* Apprentissage de la programmation avec OCaml *)
(* Catherine Dubois & Valérie Ménissier-Morain *)
(* Éditions Hermès Sciences *)
(* Mars 2004 *)
(* ===================================================== *)
(* Fichier MLSRC/Tris_listes/test_tri_liste.ml *)
(* ===================================================== *)
open Unix;;
open Insertion_liste;;
open Selection_liste;;
open Fusion_liste;;
open Tri_liste_vecteur;;
let f n =
let rec f_rec n iter max =
if n = 0 then [] else
if iter=0 then f_rec (n-1) 1000 max
else (Random.int max)::(f_rec n (iter-1) max) in
f_rec n 1000 n;;
(* ------------------------- Résultats à l'écran --------------------------- *)
(* Mesure du temps de l'algorithme algo sur la liste l, moyenné sur nb itérations, affichage à l'écran *)
let test_algorithm nb l algo nom =
let t1 = Unix.times () in
for i = 1 to nb do
algo l;
done;
let t2 = Unix.times () in
Printf.printf
"Tri par %s : %g secondes\n"
nom ((t2.tms_utime -. t1.tms_utime)/.(float_of_int nb));;
(* Mesure brute pour déterminer ensuite le nombre d'itérations à effectuer *)
let test_temps_algorithm nb l algo =
let t1 = Unix.times () in
for i = 1 to nb do
algo l;
done;
let t2 = Unix.times () in
(t2.tms_utime -. t1.tms_utime);;
(* Nombre d'itérations à effectuer pour obtenir un temps de mesure raisonnable *)
let échelle algorithme =
let iter = ref 1 in
let taille = ref 1 in (* 1000 *)
let échelle = ref [] in
let l = ref (f !taille) in
let temps = ref (test_temps_algorithm !iter !l algorithme) in
while !temps < 150.0 && !taille < 512
(* max_list_length=2^19 = 524288 > 512*1000 apparemment,
mais avec 512 tri_fusion fait stack_overflow *)
do
while !temps < 3.0 && !iter > 0 && !taille < 512 do
iter := 10 * !iter;
temps := test_temps_algorithm !iter !l algorithme
done;
temps:=!temps/.(float_of_int !iter);
échelle := !iter::!échelle;
iter := 1;
taille := 2 * !taille;
if !taille < 512 then l := f !taille;
done;
List.rev !échelle;;
print_string "Calcul des échelles"; print_newline();;
let échelle_insertion = échelle tri_insertion;;
let échelle_vinsertion = échelle tri_insertion_vect;;
let échelle_sélection = échelle tri_sélection;;
let échelle_vsélection = échelle tri_sélection_vect;;
let échelle_fusion = échelle tri_fusion;;
let échelle_vfusion = échelle tri_fusion_vect;;
let échelle_sort = échelle ((List.sort compare));;
let échelle_vstable_sort = échelle tri_stable_sort_vect;;
print_string "Échelles calculées"; print_newline();;
let rec log2 n =
if n > 1 then 1+(log2 (n/2)) else 0;;
let try_algo n algo échelle_algo nom t =
let ordre = log2 n in
if ordre >= List.length échelle_algo
then (print_string nom; print_string "non mesuré"; print_newline())
else test_algorithm (List.nth échelle_algo ordre) t algo nom;;
let try_algos n =
let t = f n in
try_algo n tri_insertion échelle_insertion "insertion " t;
try_algo n tri_insertion_vect échelle_vinsertion "insertion vect " t;
try_algo n tri_sélection échelle_sélection "sélection " t;
try_algo n tri_sélection_vect échelle_vsélection "sélection vect " t;
try_algo n tri_fusion échelle_fusion "fusion " t;
try_algo n tri_fusion_vect échelle_vfusion "fusion vect " t;
try_algo n (List.sort compare) échelle_sort "List.sort " t;
try_algo n tri_stable_sort_vect échelle_vstable_sort "stable_sort vect " t;;
let i = ref 1 in
while 1000 * !i <= Sys.max_array_length do
print_string "Pour "; print_int !i; print_string "000"; print_newline();
try_algos !i; print_newline();
i := !i lsl 1;
done;;
(* --------- Résultats dans un fichier pour traitement par xgraphic -------- *)
(* Mesure du temps de l'algorithme algo sur la liste l, moyenné sur nb itérations, stockage des résultats dans un fichier *)
let test_algorithm_fichier nb n algo fichier =
let l = f n in
let t1 = Unix.times () in
for i = 1 to nb do
algo l;
done;
let t2 = Unix.times () in
Printf.fprintf fichier "%d %f\n"
n ((t2.tms_utime -. t1.tms_utime)/.(float_of_int nb));
flush fichier;;
(* Estimation du nombre d'itérations à la louche, moins fin que la détermination des échelles ci-dessus *)
let t1000 algo =
let nb = ref 1 in
let t = ref (test_temps_algorithm !nb (f 1000) algo) in
while !t < 2.0 do
nb := !nb * 10;
t:= test_temps_algorithm !nb (f 1000) algo;
done;
!t/.(float_of_int !nb);;
let données_sélection nb nom_fichier =
let fichier = open_out nom_fichier in
let t1000 = t1000 tri_sélection in
let t = Array.init (nb+1)
(function i -> max 1 (if i = 0 then 0 else
(int_of_float (5.0/.t1000)/(i*i)))) in
for i = 1 to nb do
let n = i*1000 in
test_algorithm_fichier t.(i) n tri_sélection fichier
done;
close_out fichier;;
let données_insertion nb nom_fichier =
let fichier = open_out nom_fichier in
let t1000 = t1000 tri_insertion in
let t = Array.init (nb+1)
(function i -> max 1 (if i = 0 then 0 else
(int_of_float (5.0/.t1000)/(i*i)))) in
for i = 1 to nb do
let n = i*1000 in
test_algorithm_fichier t.(i) n tri_insertion fichier
done;
close_out fichier;;
let données_fusion nb nom_fichier =
let fichier = open_out nom_fichier in
let t1000 = t1000 tri_fusion in
let t = Array.init (nb+1)
(function i -> max 1 (if i = 0 then 0 else
(int_of_float (2.0/.t1000)/i))) in
for i = 1 to nb do
let n = i*1000 in
test_algorithm_fichier t.(i) n tri_fusion fichier
done;
close_out fichier;;
let données_sort nb nom_fichier =
let fichier = open_out nom_fichier in
let t1000 = t1000 (List.sort compare) in
let t = Array.init (nb+1)
(function i -> max 1 (if i = 0 then 0 else
(int_of_float (2.0/.t1000)/i))) in
for i = 1 to nb do
let n = i*1000 in
test_algorithm_fichier t.(i) n (List.sort compare) fichier
done;
close_out fichier;;
(* Pour les 3 courbes *)
données_sélection 40 "points_selection_liste" ;;
données_insertion 40 "points_insertion_liste" ;;
données_fusion 40 "points_fusion_liste";;
(* Pour comparaison avec le tri fusion du système *)
données_sort 40 "points_List.sort";;
(* Pour le tri fusion seul *)
données_fusion 100 "points_fusion_liste_finale";;
Ce document a été traduit de LATEX par
HEVEA.