Mark: 5 revision(s)

2008-11-03T05:19:27Z

5 revision(s)

New page

==Lab 3==

Here is the code that I used to complete the tasks:

#include "arraylist.c"
#include <time.h>

int main() {
clock_t t0;
ArrayList arr;
int limit = 10000;
int n;

arraylist_init( &arr );

t0 = clock();
for ( n = 0 ; n < limit ; n++ ) {
arraylist_put(&arr, 1, 0 );
}
printf("Time taken \t: %ld\n", (clock() - t0));

return 0;
}

==Question 1==

Number of inserts Time Taken Memory Used (mb)
10^9 crash 440+
10^8 6313 360
10^7 640 < 10
10^6 62 < 10
10^5 0 < 10

These results show that the amount memory used is minimal when the number of inserts is well below the crash threshold.

==Question 2==

Growth Factor Number of Inserts Time Taken Memory Used (mb)
2 10^9 crash 440+
10^8 6313 360
10^7 640 < 10
10^6 62 < 10
10^5 0 < 10

4 10^8 crash 21+
10^7 500 < 10
10^6 47 < 10
10^5 0 < 10

16 10^8 crash 20+
10^7 452 10
10^6 46 10
10^5 0 10

64 10^8 crash 20+
10^7 crash 10+
10^6 46 10
10^5 0 10

1.125 10^8 12015 590
10^7 1109 70
10^6 109 10
10^5 0 10

The results from this show that as the growth factor increases, the less inserts are needed to cause the program to run out of memory. If the number of inserts is not near this threshold however, it will take the same amount of time no matter the growth factor.

As the growth factor approaches 1 the times taken increase rapidly, increasing by about 100%.

==Question 3==
Initial Size Number of Inserts Time Taken Memory Used (mb)
2^4 10^9 crash 440+
10^8 6313 360
10^7 640 < 10
10^6 62 < 10
10^5 0 < 10

2^8 10^8 6296 460
10^7 626 20
10^6 61 < 10
10^5 0 < 10

2^16 10^8 6093 410
10^7 609 10
10^6 46 < 10
10^5 0 10

2^20 10^8 6343 500
10^7 562 10
10^6 46 10
10^5 15 10

2^24 10^8 6265 410
10^7 499 10
10^6 46 < 10
10^5 15 < 10

The results here show that the minimum array size has no noticeable effect on insertion time. This is probably because the time taken to fill up the first array of the initial size is insignificant when compared to the time taken to reallocate memory for each time the array fills up.

==Question 4==
Normal
Number of inserts Time Taken
10^9 crash
10^8 6187
10^7 562
10^6 62
10^5 15

With ‘ensure_capacity’
Number of inserts Time Taken
10^9 crash
10^8 4860
10^7 485
10^6 47
10^5 0

Using ensure_capacity when you know the size of the array reduces the time taken by roughly 30%.

==Question 5==
Increment Number of Inserts Time Taken Memory Used (mb)
1000 10^9 Too long
10^8 Too long
10^7 21781 30
10^6 281 10
10^5 0 10

10000 10^8 Too long
10^7 22234 600
10^6 265 10
10^5 0 < 10

1000000 10^8 44734 560
10^7 781 10
10^6 46 < 10
10^5 0 10

Lesson learned: incremental growth factor takes a long time. Small inserts are still pretty quick, but the time taken increases exponentially as the number of inserts increases passed a specific point.

Varying the amount to increase each time doesn't seem to have too much effect on the time taken except for very large increments.

==Question 6==
Number of inserts Time Taken Memory Used (mb)
10^6 Too long 90+
10^5 4641 40
10^4 46 40
10^3 0 10

arraylist_put takes a long time. This is because it has to shift the entire array contents along for every insert, as we are inserting into the first element (arr[0]).

The magnitude of the number of inserts had to be lowered here as anything above 10^5 took too long.

SE250:lab-3:sdal039 - Revision history

Mark: 5 revision(s)