Mark: 2 revision(s)

2008-11-03T05:19:21Z

2 revision(s)

New page

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

#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

#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.

SE250:lab-3:jsmi233 - Revision history

Mark: 2 revision(s)