261 lines
6.9 KiB
Ada
261 lines
6.9 KiB
Ada
with Ada.Text_Io; use Ada.Text_Io;
|
|
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
|
|
with Ada.Calendar; use Ada.Calendar;
|
|
with Tas_Gen;
|
|
with Arbre_Bin_Recherche_Cle_G;
|
|
|
|
procedure Performance is
|
|
|
|
---------------------------------------------------------------
|
|
-- Instanciation
|
|
-- Tas
|
|
procedure Liberer_Entier(N : in out Integer) is begin null;
|
|
end Liberer_Entier;
|
|
|
|
function Cle(N : in Integer) return Integer is begin return N;
|
|
end Cle;
|
|
|
|
package Tas_Entiers is new Tas_Gen(Integer, Integer, Cle, "<", Liberer_Entier, Integer'Image);
|
|
use Tas_Entiers;
|
|
|
|
-- Arbre binaire
|
|
package Arbre_Entiers is new Arbre_Bin_Recherche_Cle_G(Integer, Integer, Cle, "<", "=", Liberer_Entier, Integer'Image);
|
|
use Arbre_Entiers;
|
|
|
|
---------------------------------------------------------------
|
|
|
|
|
|
---------------------------------------------------------------
|
|
-- Constante de taille des tas
|
|
C_TAS : constant Natural := 200000;
|
|
|
|
-- Tableau
|
|
type Resultat is array (Natural range <> ) of integer;
|
|
|
|
-- Pointeurs sur procedure
|
|
type P_procedure is access procedure (F : in String);
|
|
---------------------------------------------------------------
|
|
|
|
|
|
---------------------------------------------------------------
|
|
-- Procedure de tri par tas
|
|
procedure Tri_Par_Tas(F : in string) is
|
|
File : File_Type;
|
|
Ligne : String(1..80);
|
|
I, Len : Integer := 1;
|
|
T : Un_Tas(C_TAS);
|
|
Res : Resultat(1..C_TAS) := (others => -1);
|
|
begin
|
|
Open(File, In_File, F);
|
|
|
|
-- Lecture du fichier dans un tas
|
|
while not End_Of_File(File) loop
|
|
Get_line(File, Ligne, Len);
|
|
I := Integer'value(Ligne(1..Len));
|
|
Ajouter(I, T);
|
|
end loop;
|
|
--Put_Line(Tas_To_String(T));
|
|
Close(File);
|
|
|
|
-- Tri
|
|
I := 1;
|
|
declare begin loop
|
|
Enlever_Racine(T, Len);
|
|
while Res(I) /= -1 loop I := I+1; end loop;
|
|
Res(I) := Len;
|
|
end loop; exception when Tas_Vide => goto pass;
|
|
end;
|
|
<<Pass>>
|
|
|
|
-- Sauvegarde du tri
|
|
create(File, Out_File, "./output/tas.out.txt");
|
|
|
|
for Len in 1..I-1 loop
|
|
Put(File, Integer'image(Res(Len)));
|
|
New_Line(File);
|
|
end loop;
|
|
|
|
Close(File);
|
|
end Tri_Par_Tas;
|
|
---------------------------------------------------------------
|
|
-- * *
|
|
-- * * *
|
|
-- * * * * *
|
|
-- * * * * *
|
|
-- * * * * * * *
|
|
-- * * * * * .# * *
|
|
-- * * * #. .# * *
|
|
-- * "#. #: #" * * *
|
|
-- * * * "#. ##" *
|
|
-- * "###
|
|
-- "##
|
|
-- ##.
|
|
-- .##:
|
|
-- :###
|
|
-- ;###
|
|
-- ,####.
|
|
--/\/\/\/\/\/.######.\/\/\/\/\
|
|
---------------------------------------------------------------
|
|
-- Procedure tri par arbre
|
|
procedure Tri_Par_arbre(F : in string) is
|
|
File : File_Type;
|
|
Ligne : String(1..80);
|
|
I, Len, Max : Integer := 1;
|
|
A : Arbre;
|
|
Res : Resultat(1..C_TAS) := (others => -1);
|
|
begin
|
|
Open(File, In_File, F);
|
|
|
|
-- Lecture du fichier dans un arbre
|
|
while not End_Of_File(File) loop
|
|
Get_line(File, Ligne, Len);
|
|
I := Integer'value(Ligne(1..Len));
|
|
Inserer(I, A);
|
|
end loop;
|
|
--Put_Line(Arbre_To_String(A));
|
|
Close(File);
|
|
|
|
-- Tri
|
|
I := 1;
|
|
while not Est_Vide(A) loop
|
|
Max := MaxA(A);
|
|
Res(I) := Max;
|
|
Supprimer(Max, A);
|
|
I := I + 1;
|
|
end loop;
|
|
|
|
-- Sauvegarde du tri
|
|
create(File, Out_File, "./output/arbre.out.txt");
|
|
|
|
for Len in 1..I-1 loop
|
|
Put(File, Integer'image(Res(Len)));
|
|
New_Line(File);
|
|
end loop;
|
|
|
|
Close(File);
|
|
end Tri_Par_Arbre;
|
|
---------------------------------------------------------------
|
|
|
|
|
|
---------------------------------------------------------------
|
|
-- Quicksort
|
|
procedure Quicksort (A : in out Resultat) is
|
|
procedure Swap(Left, Right : Natural) is
|
|
Temp : Integer := A (Left);
|
|
begin
|
|
A (Left) := A (Right);
|
|
A (Right) := Temp;
|
|
end Swap;
|
|
|
|
begin
|
|
if A'Length > 1 then
|
|
declare
|
|
Pivot_Value : Integer := A (A'First);
|
|
Right : Natural := A'Last;
|
|
Left : Natural := A'First;
|
|
begin
|
|
loop
|
|
while Left < Right and not (Pivot_Value < A (Left)) loop
|
|
Left := Natural'Succ (Left);
|
|
end loop;
|
|
while Pivot_Value < A (Right) loop
|
|
Right := Natural'Pred (Right);
|
|
end loop;
|
|
exit when Right <= Left;
|
|
Swap (Left, Right);
|
|
Left := Natural'Succ (Left);
|
|
Right := Natural'Pred (Right);
|
|
end loop;
|
|
if Right = A'Last then
|
|
Right := Natural'Pred (Right);
|
|
Swap (A'First, A'Last);
|
|
end if;
|
|
if Left = A'First then
|
|
Left := Natural'Succ (Left);
|
|
end if;
|
|
Quicksort (A (A'First .. Right));
|
|
Quicksort (A (Left .. A'Last));
|
|
end;
|
|
end if;
|
|
end Quicksort;
|
|
|
|
|
|
-- Procedure de tri de tableau
|
|
procedure Tri_simple(F : in string) is
|
|
File : File_Type;
|
|
Ligne : String(1..80);
|
|
I, Len, Fin : Integer := 1;
|
|
Res : Resultat(1..C_TAS) := (others => -1);
|
|
begin
|
|
Open(File, In_File, F);
|
|
Fin := 0;
|
|
|
|
-- Lecture du fichier dans un arbre
|
|
while not End_Of_File(File) loop
|
|
Get_line(File, Ligne, Len);
|
|
I := Integer'value(Ligne(1..Len));
|
|
Fin := Fin + 1;
|
|
Res(Fin) := I;
|
|
end loop;
|
|
Close(File);
|
|
|
|
-- Tri
|
|
declare
|
|
A, B : Resultat(1..Fin) := Res(1..Fin);
|
|
begin
|
|
Quicksort(A);
|
|
|
|
for I in A'Range loop
|
|
B(B'Last - I + 1) := A(I);
|
|
end loop;
|
|
|
|
-- Sauvegarde du tri
|
|
create(File, Out_File, "./output/QS.out.txt");
|
|
|
|
for Len in 1..Fin loop
|
|
Put(File, Integer'image(B(Len)));
|
|
New_Line(File);
|
|
end loop;
|
|
|
|
end;
|
|
Close(File);
|
|
end Tri_simple;
|
|
---------------------------------------------------------------
|
|
|
|
|
|
---------------------------------------------------------------
|
|
procedure Chrono(P : in P_Procedure; Arg : in String) is
|
|
-- Varaibles temps
|
|
T1, T2 : Time;
|
|
begin
|
|
T1 := Clock;
|
|
P(Arg);
|
|
T2 := Clock;
|
|
|
|
Put_Line("Temps d'éxécution : " & Duration'Image(T2 - T1));
|
|
New_Line;
|
|
end Chrono;
|
|
---------------------------------------------------------------
|
|
|
|
|
|
|
|
---------------------------------------------------------------
|
|
-- Begin
|
|
DataSet : Unbounded_String := To_Unbounded_String("data_150000.txt.dbn");
|
|
P1, P2, P3 : P_Procedure;
|
|
begin
|
|
-- Pointeurs sur procedures
|
|
P1 := Tri_Par_Tas'Access;
|
|
P2 := Tri_Par_Arbre'Access;
|
|
P3 := Tri_Simple'Access;
|
|
|
|
-- Tests de performances
|
|
Put_Line("Test de performance sur tas : ");
|
|
Chrono(P1, "./data/" & To_String(DataSet));
|
|
|
|
Put_Line("Test de performance sur arbre : ");
|
|
Chrono(P2, "./data/" & To_String(DataSet));
|
|
|
|
Put_Line("Test de performance sur liste : ");
|
|
Chrono(P3, "./data/" & To_String(DataSet));
|
|
end Performance;
|