Gjeta kohën e lirë për të rindërtuar programin më lart me strukturën e pemës që ka përmëndur edhe Iliri. U mundova të shkruaja kod sa më të shpejtë në mënyrë që të barazohej sa më mirë me kodin e shkruajtur për matricën dhe të mund të bëheshin krahasime domethënëse për të dyja strukturat.
Jepni mendimet tuaja për ndryshimet në kod nqs shikoni mundësi për përmirësime.
Sipas eksperimenteve që bëra, Matrica ngelet metoda më e mirë për këtë program por edhe Pema nuk është larg. Që të dyja strukturat kanë vështirësi me renditjen e rekordeve; matrica me funksionin qsort, ndërsa pema me funksionin hedh_ne_peme. Nxjerrja e rekordeve nga pema është më e ngadaltë, dhe po ashtu edhe lirimi i memorjes. Funksioni për të shtuar një nyje të re në pemë është shkruajtur në menyrën përsëritëse (me while) sepse metoda rekursive ishte shumë e ngadaltë. Nxjerrja nga pema dhe lirimi i memorjes bëhet në mënyrën rekursive për të shmangur kodin e gjatë me mënyrat përsëritëse.
Më poshtë janë rezultatet e të dy versioneve
1. Matrica (array) me përmasë të paracaktuar për 1.500.000 rekorde
2. Pema (tree) (pa kufizim për memorjen)
Sistemi i përdorur: Pentium 4 2.66 GHz, 256 MB memorje
Sistemi Operativ: Windows XP SP1
Përpiluesi: Dev-C++ 4.9.9.1 me GCC/MinGW 3.3.1
Do ishte mirë që programet të testoheshin në disa sisteme para se të nxjerrim konkluzione.
Koha e harxhuar nga programet në bazë të numrit të rekordeve
Kodi:
# Rekordeve Matrica (ms) Pema (ms)
125.000 470 610
250.000 910 1.251
500.000 1.790 2.600
750.000 2.653 4.130
1.000.000 3.500 7.000
1.250.000 5.900 8.800
1.500.000 7.500 11000
Analiza e funksioneve të Matricës Statike (array)
Kodi:
Funksioni % kohes
rekord_krah 80,23
strcmp 9,30
shkruaj_databaze 5,81
lexo_databaze 2,33
fgets 2,33
Analiza e funksioneve të Pemës
Kodi:
Funksioni % kohes
hidh_ne_peme 52,70
shkruaj_databaze 21,96
liro_memorje 19,26
lexo_databaze 3,38
fgets 1,42
strcmp 0,71
shkruaj_databaze dhe liro_memorje jane rekursive.
Skedarët e kodit janë bashkëngjitur më poshtë.
Kodi në C për Matricën
Kodi PHP:
// Autori: Edi, edspace ET comcast PIKE net
// Pershkrimi:
// Lexon dhe shkruan rekorde ne nje skedar sipas renditjes alfabetike
// Rekordi permban 2 kolona te ndara me tab
//
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
typedef struct rekord rekord;
const REK_MAX = 1500000; // numri maksimal per rekordet
struct rekord // struktura e nje rekordi
{
char personi [20]; // emri i personit deri ne 20 shkronja
int num; // numri
};
//********************************************************************
// Hap skedarin db dhe hidh rekordet ne matricen r
// Kthen numrin e rekordeve ne skedar ose -1 nqs nuk hapet skedari
//
int lexo_databaze( const char db [], rekord * r);
//********************************************************************
// Hap skedarin db dhe shkruar nr rekorde nga matrica r
// Kthen 0 nqs ndodh gabim
//
int shkruaj_databaze(const char db [], const rekord * r, const size_t nr);
//********************************************************************
// Krahaso dy rekorde duke u bazuar mbi personin.
// Ky funksion perdoret per renditjen e rekordeve
// emrat 0 konsiderohen si te pavlefshem dhe renditen ne fund
// Kthejme: -1 nqs r1<r2, 0 nqs r1=r2, 1 nqs r1>r1
// A < Z < 0
//
int rekord_krah ( const rekord * r1, const rekord * r2);
//********************************************************************
// MAIN
//
int main (void)
{
clock_t koha1 = clock();
const char db [] = "databaza.txt"; // emri i skedarit ku do ruhet info
const char db1 [] = "databaza2.txt"; // emri i skedarit ku do ruhet info
// tregues per array me rekorde
rekord * r = NULL;
// kerkojme memorjen per REK_MAX rekorde
r = calloc( REK_MAX, sizeof(rekord) );
if( r == NULL ) // nqs nuk ka memorje te mjaftueshme
{
printf("GABIM: Nuk ka memorje te mjaftueshme\n");
return 1;
}
int nr_rekordeve = lexo_databaze( db, r );
if ( nr_rekordeve == -1 )
{
printf("GABIM: Nuk mund te hapej skedari %s\n", db);
}
qsort (r, nr_rekordeve, sizeof (rekord), (const void *)rekord_krah);
if( !shkruaj_databaze( db1, r, nr_rekordeve ) )
{
printf("GABIM: Nuk mund te hapej skedari %s\n", db1);
return 1;
}
free(r);
printf("Koha e ekzekutimit: %ld", clock() - koha1);
return 0; // mbaruam
}
//************************************************************************
// Lexojme rekordet nga databaza
//
int lexo_databaze( const char db [], rekord * r)
{
FILE * inskedari; // tregues per skedarin
if(!(inskedari = fopen(db, "r")))
{
return -1; // nqs nuk hapim dot skedarin kthejme kodin -1 (gabim)
}
int i = 0;
char rresht [100]; // buffer per 1 rresht (maksimumi 100 shkronja)
while(i < REK_MAX ) // marrim REK_MAX rekorde nga skedari
{
fgets( rresht, 100, inskedari); // marrim rreshtin
// nqs eshte rreshti i fundit, dalim jashte
if( feof(inskedari) || strlen(rresht) == 1) break;
// marrim emrin e personit qe ndahet me tab nga numri
strncpy( r[i].personi, strtok (rresht,"\t"), 20 );
r[i].num = atoi( strtok (NULL," \n") ); // marrim numrin
i++;
}
fclose(inskedari); // mbyllim skedarin
return i; // numri i rekordeve qe gjetem ne skedar
}
//************************************************************************
// Shkruajme rekordet ne databaze
//
int shkruaj_databaze( const char db [], const rekord * r, size_t nr )
{
FILE * outskedari; // tregues per skedarin
// nqs nuk hapim dot skedarin per te shkruar
if(!(outskedari = fopen(db, "w+"))) //
{
return 0; // nqs nuk hapim dot skedarin kthejme kodin 0 (gabim)
}
int i;
for (i = 0; i < nr; i++) // shkruajme rekordet
{ // emri dhe numri jane te ndara me tab
fprintf (outskedari, "%s\t%d\n", r[i].personi, r[i].num);
}
fclose (outskedari); // mbyllim skedarin
return 1;
}
//************************************************************************
// Krahasojme rekordet e databazes
//
int rekord_krah (const rekord * r1, const rekord * r2)
{
if( strcmp("\0", r1->personi) == 0 ) return 1; // zeron e vendosim ne fund
if( strcmp("\0", r2->personi) == 0 ) return -1; // zeron e vendosim ne fund
return strcmp (r1->personi, r2->personi); // krahasojme dy fjale
}
// fund
Kodi në C për Pemën
Kodi PHP:
// Autori: Edi, edspace ET comcast PIKE net
// Pershkrimi:
// Lexon dhe shkruan rekorde ne nje skedar sipas renditjes alfabetike
// Rekordi permban 2 kolona te ndara me tab
//
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
typedef struct rekord rekord;
typedef struct nyje nyje;
typedef nyje* peme;
struct rekord // struktura e nje rekordi
{
char personi [20]; // emri i personit deri ne 20 shkronja
int num; // numri
};
struct nyje {
rekord data;
nyje * majtas;
nyje * djathtas;
};
//********************************************************************
// Hap skedarin db dhe kthe pemen me rekorde
//
peme lexo_databaze( const char db []);
//********************************************************************
// Shkruaj rekordet e pemes p ne db
//
void shkruaj_databaze(FILE * db, peme p);
//********************************************************************
// Hidh/ngjit nyjen n ne pemen p sipas rendit alfabetik
//
void hidh_ne_peme( nyje * n, peme p);
//********************************************************************
// liro memorjen e nje peme ne menyren rekursive
// liro degen majtas, liro degen djathtas, liro renjen
//
void liro_memorje(peme p);
//********************************************************************
// MAIN
//
int main (void)
{
clock_t koha1 = clock();
const char db [] = "databaza.txt"; // emri i skedarit ku do ruhet info
const char db1 [] = "databaza2.txt"; // emri i skedarit ku do ruhet info
peme p = NULL;
p = lexo_databaze( db );
if( p == NULL )
{
printf("GABIM: Nuk mund te lexonim databazen\n");
return 1;
}
FILE * outskedari; // tregues per skedarin
if(!(outskedari = fopen(db1, "w+"))) //
{
printf("GABIM: Nuk mund te hapej skedari %s\n", db1);
return 1;
}
shkruaj_databaze(outskedari, p);
fclose(outskedari);
liro_memorje(p);
printf("Koha e ekzekutimit: %ld", clock() - koha1);
return 0; // mbaruam
}
//************************************************************************
// Lexojme rekordet nga databaza
//
peme lexo_databaze( const char db [] )
{
FILE * inskedari; // tregues per skedarin
char rresht [100]; // buffer per 1 rresht (maksimumi 100 shkronja)
if(!(inskedari = fopen(db, "r")))
{
printf("Nuk mund te hapej skedari %s\n", db);
return NULL;
}
// ************* formojme renjen e pemes ***********************
// Ky bllok eshte ndare nga While per te shmangur nje kusht (if) brenda while
//
if( fgets( rresht, 100, inskedari) == NULL )
{
fclose(inskedari);
return NULL;
}
if( strlen(rresht) == 1 )
{
fclose(inskedari);
return NULL;
}
peme p = calloc(1, sizeof(nyje) );
// assert(p!=NULL);
strncpy( p->data.personi, strtok (rresht, "\t"), 20 );
p->data.num = atoi( strtok (NULL, " \n") ); // marrim numrin
p->majtas = NULL;
p->djathtas = NULL;
nyje * n = NULL;
// ************* formojme nyjet e tjera ***********************
//
while( fgets( rresht, 100, inskedari)!= NULL )
{
// nqs eshte rreshti i fundit, dalim jashte
if( strlen(rresht) == 1 ) break;
n = calloc(1, sizeof(nyje) );
if( n == NULL )
{
liro_memorje( p );
fclose(inskedari);
return NULL;
}
// marrim emrin e personit qe ndahet me tab nga numri
strncpy( n->data.personi, strtok (rresht, "\t"), 20 );
n->data.num = atoi( strtok (NULL, " \n") ); // marrim numrin
n->majtas = NULL;
n->djathtas = NULL;
hidh_ne_peme(n, p);
}
fclose(inskedari); // mbyllim skedarin
return p; // kthejme pemen
}
//************************************************************************
// Shkruaj databazen ne db nga pema p sipas renditjes alfabetike
//
void shkruaj_databaze (FILE* db, peme p)
{
if (p != NULL)
{
shkruaj_databaze(db, p->majtas);
fprintf(db, "%s\t%d\n", p->data.personi, p->data.num);
shkruaj_databaze(db, p->djathtas);
}
}
//************************************************************************
// Hidh/Ngjit nyjen n ne pemen p
// Programuar me perseritje sepse menyra rekursive eshte me e ngadalte
//
void hidh_ne_peme( nyje * n, peme p)
{
while(1)
{
if( strcmp( n->data.personi, p->data.personi ) <= 0 )
{
if( p->majtas == NULL )
{
p->majtas = n;
return;
}
else p = p->majtas;
}
else
{
if( p->djathtas == NULL )
{
p->djathtas = n;
return;
}
else p = p->djathtas;
}
}
}
//************************************************************************
// Liro memorjen e pemes p
//
void liro_memorje(peme p)
{
if( p == NULL ) return; // fakultative sepse edhe free(null) ben return
if(p->majtas != NULL) liro_memorje(p->majtas);
if(p->djathtas != NULL) liro_memorje(p->djathtas);
free(p);
p = NULL; // fakultative
}
// fund
Krijoni Kontakt