SE250:lab-3:jsmi233

Task 1:

 int main() {
 
     int n[4] = {100, 10000, 1000000, 100000000};  
 
     double results[4];
 
   long timeStart, timeTaken;
 
   int i;
 
   long long j;
 
   ArrayList list;
 
   arraylist_init(&list);
 
   for (i = 0; i < 4; i++) {
 
 	timeStart = clock();
 
 	for (j = 0; j < n[i]; j++) {
 
 	    arraylist_push(&list, 4);
 
 	}
 
 	timeTaken = clock() - timeStart;
 
 	results[i] = timeTaken / CLOCKS_PER_SEC;
 
 	printf("For n = %d, the time taken is %f\n", n[i], results[i]);
 
     }
 
     return 0;
 
 }

My initial output reported that for n <= 1000000, the time taken is zero. So I chose some different n values:

For n = 40000000, the time taken is 2.797000

For n = 80000000, the time taken is 5.343000

For n = 120000000, the time taken is 7.719000

For n = 160000000, the excecution failed. As someone else pointed out, this is probably the program has run out of memory.  

Task 2:

Using policy: new capacity = alist->capacity + ARRAYLIST_MIN_ALLOC

This doesn’t work for the same values in that it takes an insanely!!!!!! Long time (more time than I’m going to bothered waiting).

So get some new n values again.

For n = 1000000, the time taken is 0.297000

For n = 2000000, the time taken is 1.046000

For n = 4000000, the time taken is 3.656000

For n = 8000000, the time taken is 13.781000

Using policy: new capacity = alist->capacity * alist->capacity

For n = 90000, the program crashes with a rather strange looking error:

     6 [main] lab3 5724 _cygtls::handle_exceptions: Exception: STATUS_ACCESS_VIOLATION

  2507 [main] lab3 5724 open_stackdumpfile: Dumping stack trace to lab3.exe.stackdump

For n < 90000, the time taken is close to zero.

Task 3:

ARRAYLIST_MIN_ALLOC 64

For n = 10000000, the time taken is 0.656000

For n = 20000000, the time taken is 1.376000

For n = 30000000, the time taken is 2.000000

For n = 40000000, the time taken is 2.563000

1. define ARRAYLIST_MIN_ALLOC 512

For n = 10000000, the time taken is 0.641000

For n = 20000000, the time taken is 1.313000

For n = 30000000, the time taken is 1.812000

For n = 40000000, the time taken is 2.875000

 

1. define ARRAYLIST_MIN_ALLOC 4096

For n = 10000000, the time taken is 0.594000

For n = 20000000, the time taken is 1.328000

For n = 30000000, the time taken is 2.016000

For n = 40000000, the time taken is 2.640000

Changing this initial value seems to have no effect.

Task 4:

For n = 40000000, the time taken is 2.235000

For n = 80000000, the time taken is 4.500000

For n = 120000000, the time taken is 6.327000

For n = 160000000, the time taken is 8.422000

The values are pretty similar to task 1, however n = 160000000 actually works, whereas in task 1 it failed. I think it is very surprising that the values are similar to task 1, I had expected this method to be much faster.

Task 5:

I pretty much already tried this in task 2, and I found that this is slower than multiplying the capacity each time.

Task 6:

Using the same n values, this is taking too long!

For n = 40000, the time taken is 0.765000

For n = 80000, the time taken is 2.953000

For n = 120000, the time taken is 6.141000

For n = 160000, the time taken is 10.906000

It is not surprising that this takes a lot longer, since on each put operation, it must move every other value that has already been inserted.