Mark: 13 revision(s)

2008-11-03T05:19:21Z

13 revision(s)

New page

== Lab 2 ==

=== Task 1 ===
Here is my code:
<pre>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include "arraylist.h"

int main (){
ArrayList AL;
double start, end, diff;
int ntimes = 10000000;
int pushed = 1;
int i;

arraylist_init(&AL);

start = clock();

for(i = 0; i < ntimes; i++){
arraylist_push(&AL, pushed);
}

end = clock();

diff = (end - start) / CLOCKS_PER_SEC;

printf("Difference in time for %d elements is: %f \n", ntimes, diff );

return 0;
}
</pre>

In my code ntimes being n (10000000) and i was pushing the value pushed which was an int of value 1.

My result was:
<pre>Difference in time for 1000000 elements is: 0.198000
Difference in time for 2000000 elements is: 0.293000
Difference in time for 3000000 elements is: 0.448000
Difference in time for 4000000 elements is: 0.614000
Difference in time for 5000000 elements is: 0.767000
Difference in time for 6000000 elements is: 0.892000
Difference in time for 7000000 elements is: 1.133000
Difference in time for 8000000 elements is: 1.173000
Difference in time for 9000000 elements is: 1.392000
Difference in time for 10000000 elements is: 1.802000
</pre>

Seemed alright but it didn't quite take into account the for loop.

=== Task 2 ===
I modified my ocde further to automate the task of changing values for a set value in arraylist_put
<pre>int main (){
ArrayList AL;
double start, end, diff;
int ntimes = 10000000;
int pushed = 1;
int i;

for(ntimes = 1000000; ntimes <= 10000000; ntimes += 1000000){
arraylist_init(&AL);

start = clock();

for(i = 0; i < ntimes; i++){
arraylist_push(&AL, pushed);
}

end = clock();

diff = (end - start) / CLOCKS_PER_SEC;

printf("Difference in time for %d elements is: %f \n", ntimes, diff );

arraylist_clear(&AL);
}

return 0;
}</pre>
My result now is for * 3 factor
<pre>Difference in time for 1000000 elements is: 0.172000
Difference in time for 2000000 elements is: 0.276000
Difference in time for 3000000 elements is: 0.447000
Difference in time for 4000000 elements is: 0.592000
Difference in time for 5000000 elements is: 0.738000
Difference in time for 6000000 elements is: 0.950000
Difference in time for 7000000 elements is: 0.975000
Difference in time for 8000000 elements is: 1.106000
Difference in time for 9000000 elements is: 1.348000
Difference in time for 10000000 elements is: 1.478000</pre>

My result now is for the * 4 factor
<pre> Difference in time for 1000000 elements is: 0.222000
Difference in time for 2000000 elements is: 0.313000
Difference in time for 3000000 elements is: 0.409000
Difference in time for 4000000 elements is: 0.674000
Difference in time for 5000000 elements is: 0.872000
Difference in time for 6000000 elements is: 0.924000
Difference in time for 7000000 elements is: 1.012000
Difference in time for 8000000 elements is: 1.142000
Difference in time for 9000000 elements is: 1.244000
Difference in time for 10000000 elements is: 1.393000</pre>

My result now is for the * 5 factor
<pre>Difference in time for 1000000 elements is: 0.154000
Difference in time for 2000000 elements is: 0.290000
Difference in time for 3000000 elements is: 0.420000
Difference in time for 4000000 elements is: 0.578000
Difference in time for 5000000 elements is: 0.759000
Difference in time for 6000000 elements is: 0.880000
Difference in time for 7000000 elements is: 1.135000
Difference in time for 8000000 elements is: 1.336000
Difference in time for 9000000 elements is: 1.500000
Difference in time for 10000000 elements is: 1.708000</pre>

Performance seems to change as you greatly increase the amount of memory to copy accross ie a factor of 10 or 20 crashes it for 9 million values.

=== Task 3 ===
With ARRAYLIST_MIN_ALLOC set to 32:
<pre>Difference in time for 1000000 elements is: 0.177000
Difference in time for 2000000 elements is: 0.342000
Difference in time for 3000000 elements is: 0.432000
Difference in time for 4000000 elements is: 0.690000
Difference in time for 5000000 elements is: 0.760000
Difference in time for 6000000 elements is: 0.955000
Difference in time for 7000000 elements is: 1.055000
Difference in time for 8000000 elements is: 1.251000
Difference in time for 9000000 elements is: 1.385000
Difference in time for 10000000 elements is: 1.462000</pre>

With ARRAYLIST_MIN_ALLOC set to 64:
<pre>Difference in time for 1000000 elements is: 0.164000
Difference in time for 2000000 elements is: 0.302000
Difference in time for 3000000 elements is: 0.560000
Difference in time for 4000000 elements is: 0.657000
Difference in time for 5000000 elements is: 0.817000
Difference in time for 6000000 elements is: 0.944000
Difference in time for 7000000 elements is: 0.987000
Difference in time for 8000000 elements is: 1.201000
Difference in time for 9000000 elements is: 1.316000
Difference in time for 10000000 elements is: 1.487000</pre>

With ARRAYLIST_MIN_ALLOC set to 128:
<pre>Difference in time for 1000000 elements is: 0.165000
Difference in time for 2000000 elements is: 0.289000
Difference in time for 3000000 elements is: 0.519000
Difference in time for 4000000 elements is: 0.673000
Difference in time for 5000000 elements is: 0.909000
Difference in time for 6000000 elements is: 1.065000
Difference in time for 7000000 elements is: 1.125000
Difference in time for 8000000 elements is: 1.172000
Difference in time for 9000000 elements is: 1.344000
Difference in time for 10000000 elements is: 1.451000</pre>

Well doing it in relatively small values seemed useless so I went for a million default and was quicker
<pre>Difference in time for 1000000 elements is: 0.156000
Difference in time for 2000000 elements is: 0.273000
Difference in time for 3000000 elements is: 0.412000
Difference in time for 4000000 elements is: 0.659000
Difference in time for 5000000 elements is: 0.816000
Difference in time for 6000000 elements is: 0.875000
Difference in time for 7000000 elements is: 0.986000
Difference in time for 8000000 elements is: 1.118000
Difference in time for 9000000 elements is: 1.323000
Difference in time for 10000000 elements is: 1.454000</pre>

Increasing min alloc insanely made it far faster for the early values as it didn't have allocate any more memory.

=== Task 4 ===
Using required capacity I passed ntimes + 1
Getting:
<pre>Difference in time for 1000000 elements is: 0.147000
Difference in time for 2000000 elements is: 0.281000
Difference in time for 3000000 elements is: 0.387000
Difference in time for 4000000 elements is: 0.594000
Difference in time for 5000000 elements is: 0.713000
Difference in time for 6000000 elements is: 0.865000
Difference in time for 7000000 elements is: 0.947000
Difference in time for 8000000 elements is: 1.097000
Difference in time for 9000000 elements is: 1.151000
Difference in time for 10000000 elements is: 1.278000</pre>

Which is significantly faster as it won't take the time to allocate memory.

=== Task 5 ===
Started off with n being 10000 and going up in 10000 as it was too quick either wise

<pre>Difference in time for 10000 elements is: 0.002000
Difference in time for 20000 elements is: 0.004000
Difference in time for 30000 elements is: 0.004000
Difference in time for 40000 elements is: 0.006000
Difference in time for 50000 elements is: 0.008000
Difference in time for 60000 elements is: 0.008000
Difference in time for 70000 elements is: 0.008000
Difference in time for 80000 elements is: 0.011000
Difference in time for 90000 elements is: 0.012000
Difference in time for 100000 elements is: 0.022000</pre>

SE250:lab-3:jhor053 - Revision history

Mark: 13 revision(s)