SE250:lab-3:sdal039

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.