Mark: 9 revision(s)

2008-11-03T05:19:22Z

9 revision(s)

New page

I'm just reading a book call Data Structures Demysitified to get familiar with arrays. I shall begin my lab work only after that.

==1==
int main() {

clock_t t0;
int n;
ArrayList xs;
arraylist_init(&xs);

t0 = clock();
for (n=0; n<100000000000; n++){

arraylist_push(&xs, n);
}

printf("time=%ld\n", clock() - t0 );

return 0;
}

When n=1000, time =0
n=10000, time=3
n=100000,time=16
n=1000000,time=160
n=10000000,time=1512
n=100000000,time=14661

==2==

Changing *2-

with *4, time for n=1000000 was 183
with *25, time for n=1000000 was 175
with *40, time for n=1000000 was 150
with *100, time for n=1000000 was 213
with *1000, time for n=1000000 was 212
with *1500, time for n=1000000 was 338
with *5000, it took very long to display a time of 20606.
*At *6000, it was unable to run it as memory had been exhausted.

==3==

Changing initial array sizes-

When ARRAYLIST_MIN_ALLOC is 16, with n=1000000, time=154
When ARRAYLIST_MIN_ALLOC is 20, with n=1000000, time=171
When ARRAYLIST_MIN_ALLOC is 50, with n=1000000, time=166
When ARRAYLIST_MIN_ALLOC is 100, with n=1000000, time=161
When ARRAYLIST_MIN_ALLOC is 500, with n=1000000, time=164
When ARRAYLIST_MIN_ALLOC is 1000, with n=1000000, time=167
When ARRAYLIST_MIN_ALLOC is 1500, with n=1000000, time=162
When ARRAYLIST_MIN_ALLOC is 3000, with n=1000000, time=170

*The times dont seem to change much when the initial array sizes are varied.

==4==

==5==

Changing the growth strategy to an incremental one by changing arraylist_put from *2 to +1000.

When n<100, t=0
n<1000, t=0
n<10000, t=3
n<100000, t=22
n<1000000, t=3051
At n<10000000 it took really long and it displayed no answer in the end.

==6==

Using arraylist_put instead of arraylist_push-

With n<100, t=0
With n<1000, t=1
With n<10000, t=56
With n<100000, t=4597
With n<1000000 it took really long and did not display any answer in the end.

From this we can see that adding elements to the front of the array takes longer than adding elements to the end of it.

SE250:lab-3:mgha023 - Revision history

Mark: 9 revision(s)