SE250:lab-3:dols008

Task 1/2

Times for appending 10000000 elements with various growth factors:

Factor  Time (s)
*1.5:	0.452 0.453 0.452 0.452
*2:	0.452 0.437 0.452 0.437
*4:	0.405 0.374 0.374 0.405
*8:	0.374 0.374 0.374 0.389

Higher growth factors do result in lower times, but it's a trade-of because they waste large amounts of memory. In practice, I would probably use something int the 1.5 to 2.0 range.

Task 3

Still appending 10000000 elements, with various values of MIN_ALLOC:

MIN_ALLOC Time(s)
16:       0.452 0.437
16384:    0.436 0.437
65536:    0.467 0.436

MIN_ALLOC makes very little difference to the run time. This is because it only saves reallocating the array when the array is small anyway (and therefore inexpensive to realloc).

Task 4

Times for appending 10000000 elements, with the space pre-allocated:

Time (s)
0.327
0.343
0.343
0.342

This did result in a noticeable decrease in the times. The lesson to be learned from this is, if you know how many elements you need to append you should ensure the final capacity before you append them.

Task 5

Times for appending 10000000 elements, with incremental reallocation:

Increment Time(s)
+100:     19.04 19.12
+1000:    19.11 19.078
+10000:   18.95 19.00

Note the extremely large times. Reallocating the array every thousand elements become extremely expensive when the array is large, because the entire contents has to be copied between the old and new array. As the array size increases, the average time taken to append an element increases sharply. With the factor of 2 the average time remains fairly constant, because the bigger the array becomes, the less often it's reallocated, to offset the cost of reallocating it.

Task 6

Prepending elements (with a factor of 2 reallocation scheme):

n      Time(s)
100000 3.775 3.712
150000 8.330 8.330

I could not use such large values of n when pre-pending elements to the array because it takes such a long time. Note that increasing n by 50% resulted in a disproportionately large increase in time. This is because pre-pending requires that all the elements currently in the array be shifted one position, so the new element fits at the start. As the array becomes larger, shifting the entire array every time you add an element becomes more and more horribly expensive.