SE250:lab-3:jpar277

After reading the code and reasonably understanding what was going on, I realised we had to type up the main function which performs the time taken to add elements into the array.

Task 1

I had to go back to our first lab so that I could refresh my mind on the clock function and code.

I ended up with this code ::::

int main(void) {
	ArrayList testarr;
	int i=0;
	double  duration;

	clock_t start, finish;

	arraylist_init(&testarr);
	start = clock();
	while (i<1000000) {
		arraylist_push(&testarr, 1);
		i++;
	}
	finish = clock();

	duration = (double)(finish - start) / CLOCKS_PER_SEC;

	printf("Time taken to add %d elements is %f seconds\n", i, duration);

	return 0;
}

The results I got for the time taken varied everytime I ran it as they had to be moved to different sections in memory and also, the size of the array itself affected the speed.

The results listed below are the averages, the actual results varied by roughly 0-30ms on either side of these.

• 100000 elements took 24ms
• 200000 elements took 32ms
• 300000 elements took 47ms
• 400000 elements took 59ms
• 500000 elements took 72ms
• 600000 elements took 97ms
• 700000 elements took 108ms
• 800000 elements took 117ms
• 900000 elements took 136ms
• 1000000 elements took 147ms

Task 2

I wasn't quite sure how high we were supposed to go, I went up in intervals of 0.5 up to 10.0. I kept the number of elements being added into the array constant at 1000000 (1million) and just changed the growth factor.

Results ::::

• Growth factor of 2.0 took 147ms
• Growth factor of 2.5 took 155ms
• Growth factor of 3.0 took 162ms
• Growth factor of 3.5 took 145ms
• Growth factor of 4.0 took 145ms
• Growth factor of 4.5 took 151ms
• Growth factor of 5.0 took 147ms
• Growth factor of 5.5 took 150ms
• Growth factor of 6.0 took 166ms
• Growth factor of 6.5 took 150ms
• Growth factor of 7.0 took 145ms
• Growth factor of 7.5 took 146ms
• Growth factor of 8.0 took 159ms
• Growth factor of 8.5 took 167ms
• Growth factor of 9.0 took 193ms
• Growth factor of 9.5 took 146ms
• Growth factor of 10.0 took 150ms

The growth factor of 9.0 was consistantly high, which was surprising. With that one exception, the rest of the results seem pretty close together. So to answer the question, When does increasing the growth factor make little difference to the runtime? I'd say it doesn't really matter. However, maybe if I went up to say a growth factor of 100, it might make a big difference.

Infact, I actually tried the growth factor of 100 and got 205ms, so possibly my growth factors just weren't big enough to see any big differences.

Task 3

So, this time we had to change ARRAYLIST_MIN_ALLOC, again I kept the number of elements being added constant at 1million and the growth factor back to 2.0

Results ::::

• ARRAYLIST_MIN_ALLOC of 16 took 147ms
• ARRAYLIST_MIN_ALLOC of 50 took 156ms
• ARRAYLIST_MIN_ALLOC of 100 took 157ms
• ARRAYLIST_MIN_ALLOC of 150 took 153ms
• ARRAYLIST_MIN_ALLOC of 200 took 156ms
• ARRAYLIST_MIN_ALLOC of 250 took 147ms
• ARRAYLIST_MIN_ALLOC of 300 took 152ms
• ARRAYLIST_MIN_ALLOC of 350 took 151ms
• ARRAYLIST_MIN_ALLOC of 400 took 152ms
• ARRAYLIST_MIN_ALLOC of 450 took 158ms
• ARRAYLIST_MIN_ALLOC of 500 took 147ms

Theres barely any change in speed between the different values.

Task 4

I changed everything back to their original values and added in the function call to ensure_capacity.

My code then looked like ::::

int main(void) {
	ArrayList testarr;
	int i=0;
	double  duration;

	clock_t start, finish;
 
	arraylist_init(&testarr);
	ensure_capacity(&testarr, 1000000);

	start = clock();
	while (i<1000000) {
		arraylist_push(&testarr, 1);
		i++;
 	}
	finish = clock();

	duration = (double)(finish - start) / CLOCKS_PER_SEC;

	printf("Time taken to add %d elements is %f seconds\n", i, duration);

	return 0;
}

Just like the first task, I had some change in the results when repeated with the same values to get an average.

Results ::::

• 100000 elements took 14ms
• 200000 elements took 27ms
• 300000 elements took 38ms
• 400000 elements took 54ms
• 500000 elements took 68ms
• 600000 elements took 84ms
• 700000 elements took 96ms
• 800000 elements took 107ms
• 900000 elements took 121ms
• 1000000 elements took 135ms

As you can see, compared to the results from task 1, these values are lower but not by a significant amount. Perhaps if we added in elements in the millions instead of the 100thousands, then we'd see a huge difference.