SE250:lab-3:hbar055

Number1

The code I typed was transferred to the 'arraylist.c' the lecturer wrote for us, since compiling in my own *.c file gave some mysterious error.

This was the code used to perform task 1:

int main (){
   ArrayList ar;
   clock_t x, y;
   element_t elt = 1;
   int i;

   arraylist_init (&ar);
   x = clock();
   for (i = 0; i < 5000000; i++){

arraylist_push (&ar, elt);

   }

   y = clock() - x;

   printf("time taken = %d", y);

   return 0;
}

The result returned when 5 million repeats were used was:

time taken = 249 The result returned when 10 million repeats were used was:

time taken = 452 The result returned when 20 million repeats were used was:

time taken = 827 As the loop number increased, the time taken also increased as expected. Also, the increase in time is roughly proportional to the number of loops - each doubling of repeats accompanies an almost doubling of time taken.

Number2

When the factor was changed to 1.1,

time taken = 467 When the factor was changed to 1.5,

time taken = 249 When the factor was changed to 3.0,

time taken = 187 When the factor was changed to 3.0 up to 20.0,

time taken = 187 When the factor was changed to 70.0,

time taken = 156 I tried with values up to 2000.0, and still time taken hovered around 156ms for 5 million repeats. I think this is because as soon as the capacity is expanded, the array already has enough memory for 5 million values, which doesn't require another increase in array capcity, which may then deplete available memory and return an error.

Number3

when ARRAYLIST_MIN_ALLOC is 1,

time taken = 203 when ARRAYLIST_MIN_ALLOC is 2,

time taken = 218 when ARRAYLIST_MIN_ALLOC is 4,

time taken = 202 when ARRAYLIST_MIN_ALLOC is 8,

time taken = 218 when ARRAYLIST_MIN_ALLOC is 32,

time taken = 218 As shown, changing ARRAYLIST_MIN_ALLOC size does not seem to significantly affect the time taken. I think this is because the function arraylist_put doubles the array size each time, which means that to increase the array size to 16, the ensure_capacity function needs only run 8 times, which presumably takes very little time compared to running the entire for loop which has the preset array size of 16.

Number4

when I made the size of the array 5 million before running the for loop,

time taken = 156 This prevents having to increase capacity of the array during running of the for loop, which slightly decreases the run time required by about 20ms.

Number5

The number of loops remains at 5 million with array capacity growing at 1,000 each time:

time taken = 4772 This is expected, because with the array growing at a constant value, the array capacity must be used many many more times (~ no. of repeats / incremental value) which involves reallocating memory, can calling the ensure_capacity function and increases time required to run the program.

Number6

In order for the program to complete in a reasonable time, the number of repeats had to be reduced to 100,000 (by a factor of 50). The new values were inserted at the beginning of the array, at index 0 as instructed.

time taken = 3744 Despite the reduction in loop number, the program still took seconds to run. This is most likely due to the repeated memmove required in order to insert the new member into the beginning of the array.