(* ===================================================== *)
(* Apprentissage de la programmation avec OCaml *)
(* Catherine Dubois & Valérie Ménissier-Morain *)
(* Éditions Hermès Sciences *)
(* Mars 2004 *)
(* ===================================================== *)
(* Fichier MLSRC/Tris_vecteurs/test_tri_vecteur.ml *)
(* ===================================================== *)
open Unix;;
open Selection_vecteur;;
open Insertion_vecteur;;
open Fusion_vecteur;;
open Tri_tas;;
(* Création du tableau aléatoire *)
let f n = Array.init n (function i -> Random.int (n*1000));;
(* ------------------------- Résultats à l'écran --------------------------- *)
(* Mesure du temps de l'algorithme algo sur le vecteur t, moyenné sur nb itérations, affichage à l'écran *)
let test_algorithm nb t algo nom =
let t1 = Unix.times () in
for i = 1 to nb do
let t' = Array.copy t in algo t';
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 t algo =
let t1 = Unix.times () in
for i = 1 to nb do
let t' = Array.copy t in algo t';
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 t = ref (f !taille) in
let temps = ref (test_temps_algorithm !iter !t algorithme) in
begin try
while !temps < 50.0 && 1000 * !taille <= Sys.max_array_length do
while !temps < 3.0 && !iter > 0 && 1000 * !taille <= Sys.max_array_length do
iter := 10 * !iter;
temps := test_temps_algorithm !iter !t algorithme
done;
temps:=!temps/.(float_of_int !iter);
échelle := !iter::!échelle;
iter := 1;
taille := 2 * !taille;
t := f !taille;
done
with Invalid_argument("Random.int") -> () end;
List.rev !échelle;;
print_string "Calcul des échelles"; print_newline();;
let échelle_sélection = échelle tri_sélection;;
let échelle_insertion = échelle tri_insertion;;
let échelle_fusion = échelle tri_fusion;;
let échelle_stable_sort = échelle (Array.stable_sort compare);;
let échelle_sort = échelle (Array.sort compare);;
let échelle_tas = échelle tri_tas;;
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_algo2 n =
let t = f n in
try_algo n tri_tas échelle_tas "tas " 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_algo2 !i; print_newline();
i := !i lsl 1;
done;;
let try_algos n =
let t = f n in
try_algo n tri_sélection échelle_sélection "sélection " t;
try_algo n tri_insertion échelle_insertion "insertion " t;
try_algo n tri_fusion échelle_fusion "fusion " t;
try_algo n (Array.stable_sort compare) échelle_stable_sort "Array.stable_sort" t;
try_algo n tri_tas échelle_tas "tas " t;
try_algo n (Array.sort compare) échelle_sort "Array.sort " 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 --------- *)
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 test_algorithm_fichier nb n algo fichier =
let t1 = Unix.times () in
for i = 1 to nb do
algo (f n);
done;
let t2 = Unix.times () in
Printf.fprintf fichier "%d000 %e\n"
n ((t2.tms_utime -. t1.tms_utime)/.(float_of_int nb));
flush fichier;;
let données_sélection () =
let fichier = open_out "points_selection_tableau" in
let t1000 = t1000 tri_sélection in
let t = Array.init 161
(function i -> max 100000 (if i = 0 then 0 else
(int_of_float (5.0/.t1000)/(i*i)))) in
for i = 1 to 40 do
test_algorithm_fichier t.(4*i) (4*i) tri_sélection fichier
done;
close_out fichier;;
let données_insertion () =
let fichier = open_out "points_insertion_tableau" in
let t1000 = t1000 tri_insertion in
let t = Array.init 161
(function i -> max 100000 (if i = 0 then 0 else
(int_of_float (5.0/.t1000)/(i*i)))) in
for i = 1 to 40 do
test_algorithm_fichier t.(4*i) (4*i) tri_insertion fichier
done;
close_out fichier;;
let données_fusion () =
let fichier = open_out "points_fusion_tableau" in
let t1000 = t1000 tri_fusion in
let t = Array.init 161
(function i -> max 100000 (if i = 0 then 0 else
(int_of_float (2.0/.t1000)/(10*i)))) in
for i = 1 to 40 do
test_algorithm_fichier t.(4*i) (4*i) tri_fusion fichier
done;
close_out fichier;;
données_sélection ();;
données_insertion ();;
données_fusion ();;
Ce document a été traduit de LATEX par
HEVEA.