C - Strukturat e të dhënave (Matricat, Listat, Pemët)

[werewolf]

paskan filluar prapde diskutimet ketej......
27000

[josif]

Kam bashkangjitur kodin

[edspace]

E provova në dy kompjutera dhe më nxjerr të njëjtin gabim.

Windows XP me Dev C++ 4.9.9.1
Windows XP me lcc

Që të dyja përdorin gcc 3.3


Skedari që kam bashkëngjitur këtu, me 3000 rekorde, ekzekutohet për 10 (ms) nga programi im në një kompjuter me Windows XP, 2.6 GHz.
Nuk e di nga i ke nxjerrë ato numrat e tjerë por do ti testoj të dy programet me saktësi dhe do ti hedh rezultatet këtu.

Wolf, mqns ti nuk ke problem me programin e Josifit, po nuk te rendet bej nje test me te dy programet, me te njejtin skedar dhe hidh rezultatet ketu qe te kemi sa me shume konfigurime te ndryshme.

[werewolf]

ok, i bera testet,
rezultatet jane me poshte, megjithese duhet nje version i programit te edit me selection sort, pasi me ritjen e dimensionit te inputit, selection sort ben te tijen ...


ah se harrova i kompilova me:
gcc version 3.3.5 (Debian 1:3.3.5-5)
kompjuteri:
mobile amd athlon 2200+
512 mb ram
etj....

[josif]

Deficienca kryesore e implementimit tim eshte sepse gjate leximit te nje stringu si psh:

/***/
while( (c=fgetc(in)), ( (c>='a' && c<='z') || (c>='A' && c<='Z') || c == ' ' )
&& c != '\t){
name_allocated++;
r->name =(char *)realloc(r->name, (length_name + 2)*sizeof(char));
*(r->name+length_name++) = c;
}
/***/


... kodi ben realloc-imin e stringut per cdo char qe lexon. Keshtu qe per 4 char te lexuar ai duhet te beje:
{ realloc(string,1) + realloc(string,2) + realloc(string,3) + realloc(string,4) }


Nje optimizim i kesaj te mete do te ishte realloc-imi i stringut cdo N char-aktere te lexuara. Nese perafrojme nje N te llogjikshme dhe nderkohe char-akteret i ruajme ne nje buffer(depo), atehere eshte e mundur qe realloc-imi dinamik te shpejtohet akoma me shume, duke bere sa me pak realloc-ime.

Algoritmi i optimizimit;


1 Lexo karakterin ch, Nderkohe qe ch != EOF perserit 2- 6
2 Nese ( mod )==0
3 shto permbajtjen e buffer-it tek stringu
4
5 buffer[( mod )] = ch
6 <-- + 1
7
8 Nese ka akoma char ne buffer
/* ( mod )!=0 */
9 shtoi edhe ato ne str


Nese kam kohe mund ta implementoj se shpejti.

[edspace]

I ekzekutova programet në kompjuterin kryesor të universitetit:
Machine hardware: sun4u
OS version: 5.9
Processor type: sparc
Hardware: SUNW,Ultra-4

Programet u testuan me skedarin databaza.txt që bashkëngjita më lart. Skedarët me 10.000 dhe 50.000 rekorde u krijuan duke ngjitur disa herë skedarin me 3.000 rekorde.

Rezultatet më poshtë tregojnë se versioni me matrica dinamike është shumë herë më i ngadaltë.
Ka shumë arsye për këtë diferencë të madhe por gjithësesi mendoj se sado i mirë të jetë kodi për matricat dinamike, asnjëherë nuk mund të jetë më i shpejtë se versioni me matrica statike. Megjithatë, do postoj më vonë versionin me "selection sort" (renditje zgjedhore?) të programit dhe atëherë do kemi një krahasim më të vlefshëm.


500 Rekorde

Statike (Edi)
360.000
390.000
390.000
400.000
390.000

Dinamike (Josifi)
60.000
100.000
90.000
100.000
80.000

3.000 Rekorde

Statike
380.000
430.000
410.000
400.000
420.000

Dinamike
1.670.000
1.710.000
1.690.000
1.700.000
1.690.000


10.000 Rekorde

Statike
490.000
520.000
510.000
510.000
510.000

Dinamike
17.510.000
17.560.000
17.550.000
17.550.000
17.550.000


50.000 Rekorde

Statike
1.090.000
1.150.000
1.110.000
1.100.000
1.140.000

Dinamike
438.950.000 (rreth 15 minuta kohë)
...
...
...
... s'kisha kohë për 4 ekzekutime të tjera


Josif, thjesht duke parë gjatësinë e kodit, duket qartë se ka shumë gjëra të tepërta në programin tënd. Ndalesa kryesore besoj se vjen nga problemi që përmënde por ka dhe shumë gjëra të tjera. Do ishte më mirë të modifikoje programin tim me qëllim që të ndryshohej vetëm një faktor (nga statike në dinamike) dhe pastaj të bëhej përsëri eksperimenti.

[josif]

Ja nje implementim relativisht me i shpejte se i pari.

*)Perdor in-place quick-sort,
*)Eliminon funksionet ndihmese te teperta duke evituar humbjen e kohes ne "run-time stack"

**) per fat te keq nuk kam patur kohe te implementoj edhe algoritmin e optimizimit si me lart!!!




Testimet e bera me versionin e ri:



1500 rekorde

Implementimi dinamik:
0
0
0
0

Implementimi statik:
70000
80000
80000
70000


3000 rekorde

Implementimi dinamik:
0
0
10000
0

Implementimi statik:
70000
70000
70000
70000


6000 rekorde

Implementimi dinamik:
10000
10000
10000
10000

Implementimi statik:
80000
70000
80000
80000


12000 rekorde

Implementimi dinamik:
40000
30000
30000
40000

Implementimi statik:
100000
90000
90000
90000


24000 rekorde

Implementimi dinamik:
90000
80000
90000
80000

Implementimi statik:
120000
130000
120000
130000



***me poshte eshte kodi qe mund te perdoret per verifikim.

[josif]

Sic e sheh edi po te permiresohet edhe deficienca e realloc-imit te shpejte implementimi dinamik eshte i pandalshem.

Per statistikat me lart ke te drejte. Dihet qe quick-sort eshte shume me i shpejte.

P.S: Mos harro qe une jam vetem ne vit te dyte universitet dhe kam vetem 1 vit praktike ne C, edhe pse e zoteroj mire deri diku.

[josif]

Ndersa per sa i perket perdorimi i hapesires implementimi statik eshte skandaloz!!

1) RAm-it i merren '1500000*size(struct record) bits' gjate cdo exekutimi, pavaresisht nga madhesia e inputit.
1.1) size(struct record) >= 20*sizeof(char) + sizeof(int)

=>Keshtu qe gjate cdo egzekutimi programi i Edit harxhon
hapesire >= 1500000*24 bits
hapesire >= 4500000 bytes

Pra afro 4.3 MB RAM !!!

Nese imputi eshte 100 rekorde, atehere
*) Implementimi dinamik harxhon 350 byte
*) Implementimi statik i Edit harxhon 4.3 Mbyte.

Pra ne nje imput me 100 rekorde programi i Edit harxhon 12857 here me shume RAM. Dhe me e keqja eshte edhe me i ngadalte.


P.S: Sqarim: Ne te dyja rastet RAM-i i harxhuar lirohet me te mbaruar egzekutimi.

[josif]

Josif, thjesht duke parë gjatësinë e kodit, duket qartë se ka shumë gjëra të tepërta në programin tënd. Ndalesa kryesore besoj se vjen nga problemi që përmënde por ka dhe shumë gjëra të tjera. Do ishte më mirë të modifikoje programin tim me qëllim që të ndryshohej vetëm një faktor (nga statike në dinamike) dhe pastaj të bëhej përsëri eksperimenti.

Kodi im eshte me i gjate thjesht ngaqe nuk perdor "librari te gatshme"
si ti!!! Te vetmet funksione qe kam perdorur jane te doemosdoshmet :feof, fscanf, fprintf, fopen, fclose, clock ,malloc, realloc, free + strcmp. I vetmi funksion qe mund ta beja vete eshte strcmp.