SE250:lab-3:dcho040

From Marks Wiki
Revision as of 05:19, 3 November 2008 by Mark (Sọ̀rọ̀ | contribs) (29 revision(s))
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Q1

Codes

#include <stdio.h>
#include "arraylist.h"
#define add_time 10000000
#define add_value 2147483647
#define number_trial 10

int main() {
	ArrayList xs;
	arraylist_init(&xs);
	int i,j;
	int time_total = 0;
	double time_avg;
	for (i = 0; i < number_trial; i++) {
		clock_t t0 = clock();
		for (j = 0; j < add_time; j++) {
			arraylist_push(&xs, add_value);
		}
		clock_t t1 = clock();
		time_total += t1 - t0;
	}
	time_avg = (double)time_total / number_trial;

	printf("put %d, %ld times took average %.2lf s", add_value, add_time, time_avg);
	return 0;

}

Prediction

- (wrong)Both The number of times saving and The value saved affect to the time

Results 1 (Vista in G-Lab)

put 1, 100000    times took average 4.60 s
put 1, 1000000   times took average 45.20 s
put 1, 10000000  times took average 410.30 s
put 1, 100000000 times : error
assertion "alist->arr != (element_t*)0" faild: file "arraylist.c", line 40 
10 [sig] lab3_1 3496 h:\soft250lab\lab3\lab3_1.exe: *** fatal error - called with threadlist_ix -1 Hangup

Results 2 (Vista in G-Lab)

put 2147483647, 100000    times took average 4.70 s
put 2147483647, 1000000   times took average 45.20 s
put 2147483647, 10000000  times took average 427.40 s
put 2147483647, 100000000 times : error
assertion "alist->arr != (element_t*)0" faild: file "arraylist.c", line 40 
10 [sig] lab3_1 3496 h:\soft250lab\lab3\lab3_1.exe: *** fatal error - called with threadlist_ix -1 Hangup

Discussion

- Total time would proportion to the number of times saving the value. - The value saved would not affect to the total time - No idea with the error when input the values 100,000,000 times

Q2

Prediction

- (partly true)The time decreses while (*2) increases because of less memory relocating occured

Results 1 (Vista(AMD) at home)

put 2147483647, 10,000,000 times
*2  : 535.00 s
*4  : 496.00 s
*6  : 461.70 s
*8  : 466.40 s
*10 : 449.20 s
*12 : assertion "alist->arr != (element_t*)0" failed: file "arraylist.c", line 40 
      15 [sig] lab3_1 4032 _cygtls:: handle_exceptions: Error while dumping state (probably corrupted stack)
      Segmentation fault (core dumped)
*14 : 449.20 s
*16 : 449.20 s
*18 : assertion "alist->arr != (element_t*)0" failed: file "arraylist.c", line 40 
      14 [sig] lab3_1 4024 _cygtls:: handle_exceptions: Error while dumping state (probably corrupted stack)
      Segmentation fault (core dumped)
*20 : assertion "alist->arr != (element_t*)0" failed: file "arraylist.c", line 40 
      12 [sig] lab3_1 2968 _cygtls:: handle_exceptions: Error while dumping state (probably corrupted stack)
      Segmentation fault (core dumped)
*22 : assertion "alist->arr != (element_t*)0" failed: file "arraylist.c", line 40 
      12 [sig] lab3_1 876 _cygtls:: handle_exceptions: Error while dumping state (probably corrupted stack)
      Segmentation fault (core dumped)
*24 : 447.60 s

Results 2 (Vista(AMD) at home)

put 2147483647, 1,000,000 times
*2  : 53.00 s
*4  : 48.30 s
*6  : 45.10 s
*8  : 48.30 s
*10 : 43.60 s
*12 : 46.70 s
*14 : 49.80 s
*16 : 46.70 s
*18 : 43.70 s
*20 : 45.10 s
*22 : 43.60 s

Discussion

- The time reduces while (*2) in arraylist_put increases, but is stable from around (*6) - large mount of inputs(10,000,000) shows error in some cases

Q3

Prediction

-(Not quite right)Maybe the results show random times.

Results 1 (Vista(AMD) at home)

Increase ARRAYLIST_MIN_ALLOC
put 2147483647, 10,000,000 times
16       : 538.10 s
160      : 549.00 s
1600     : 508.40 s
16000    : 516.20 s
160000   : 552.20 s
1600000  : 503.80 s
16000000 : 517.80 s

Results 2 (Vista(AMD) at home)

Increase ARRAYLIST_MIN_ALLOC
put 2147483647, 1,000,000 times 
16  : 54.50 s
32  : 53.00 s
48  : 51.50 s
64  : 54.50 s
80  : 49.80 s
96  : 51.40 s
112 : 53.00 s
128 : 54.50 s
144 : 54.50 s
160 : 49.90 s

Results 3 (Vista(AMD) at home)

Increase ARRAYLIST_MIN_ALLOC
put 2147483647, 1,000,000 times 
16 : 52.90 s  26 : 49.90 s  36 : 54.50 s  46 : 49.90 s  56 : 59.90 s  66 : 54.50 s  47 : 48.20 s
17 : 54.60 s  27 : 51.40 s  37 : 56.10 s  47 : 51.50 s  57 : 51.40 s  67 : 54.10 s  48 : 48.40 s
18 : 57.60 s  28 : 53.00 s  38 : 56.10 s  48 : 49.90 s  58 : 49.90 s  68 : 56.10 s  49 : 49.90 s
19 : 57.60 s  29 : 53.00 s  39 : 49.90 s  49 : 49.80 s  59 : 51.50 s  69 : 54.60 s
20 : 49.90 s  30 : 52.90 s  40 : 49.80 s  50 : 51.40 s  60 : 53.00 s  70 : 54.60 s
21 : 48.40 s  31 : 54.50 s  41 : 49.90 s  51 : 51.50 s  61 : 53.00 s  71 : 56.10 s
22 : 49.90 s  32 : 54.50 s  42 : 51.40 s  52 : 48.30 s  62 : 51.40 s  72 : 56.10 s
23 : 51.50 s  33 : 56.10 s  43 : 49.90 s  53 : 53.00 s  63 : 53.10 s  73 : 53.00 s
24 : 51.40 s  34 : 54.50 s  44 : 49.90 s  54 : 52.90 s  64 : 51.50 s  74 : 54.50 s
25 : 51.40 s  35 : 54.50 s  45 : 48.30 s  55 : 52.90 s  65 : 54.50 s  75 : 48.20 s

Discussion

- Generally times increases while ARRAYLIST_MIN_ALLOC increases, but some points the time drops.

Q4

Codes

#include <stdio.h>
#include "arraylist.h"
#define add_time 10000000
#define add_value 2147483647
#define number_trial 10

int main() {
	ArrayList xs;
	arraylist_init(&xs);
	int i,j;
	int time_total = 0;
	double time_avg;
	ensure_capacity(&xs, add_time); // pre-allocate the meximum expected size of the array
	for (i = 0; i < number_trial; i++) {
		clock_t t0 = clock();
		for (j = 0; j < add_time; j++) {
			arraylist_push(&xs, add_value);
		}
		clock_t t1 = clock();
		time_total += t1 - t0;
	}
	time_avg = (double)time_total / number_trial;

	printf("put %d, %ld times took average %.2lf s", add_value, add_time, time_avg);
	return 0;

}

Prediction

- (right)pre-allocate the meximum expected size of the array saves the time.

Results 1 (Vista(AMD) at home)

experiment1
put 2147483647, 100,000    times took average     32.80 s
put 2147483647, 1,000,000  times took average   2194.90 s
put 2147483647, 10,000,000 times took average 202227.10 s

Results 2 (Vista(AMD) at home)

pre-allocate the meximum expected size of the array
put 2147483647, 100,000    times took average     29.70 s
put 2147483647, 1,000,000  times took average   2148.10 s
put 2147483647, 10,000,000 times took average 203534.40 s

Discussion

- There is time saving from pre-allocating the meximum expected size of the array

Q5

Prediction

- (+1000) took more time than (*2) because (+1000) does more replacing than (* 2)

Results 1 (Vista(AMD) at home)

(*2) in arrylist_put
put 2147483647, 100,000    times took average       4.60 s
put 2147483647, 200,000    times took average       9.30 s
put 2147483647, 300,000    times took average      15.60 s
put 2147483647, 400,000    times took average      20.20 s
put 2147483647, 500,000    times took average      26.40 s
put 2147483647, 600,000    times took average      31.20 s
put 2147483647, 700,000    times took average      35.80 s
put 2147483647, 800,000    times took average      38.90 s
put 2147483647, 900,000    times took average      50.00 s
put 2147483647, 1000,000   times took average      53.00 s

Results 2 (Vista(AMD) at home)

(+2000) in arrylist_put
put 2147483647, 100,000    times took average      23.50 s
put 2147483647, 200,000    times took average      87.30 s
put 2147483647, 300,000    times took average     193.40 s
put 2147483647, 400,000    times took average     352.40 s
put 2147483647, 500,000    times took average     542.90 s
put 2147483647, 600,000    times took average     773.70 s
put 2147483647, 700,000    times took average    1040.50 s
put 2147483647, 800,000    times took average    1358.70 s
put 2147483647, 900,000    times took average    1733.10 s
put 2147483647, 1000,000   times took average    2157.40 s

Discussion

- As put values more, (+1000) needs huge mount of times to precess

Q6

codes

#include <stdio.h>
#include "arraylist.h"
#define add_time 10000
#define add_value 2147483647
#define number_trial 10

int main() {
	ArrayList xs;
	arraylist_init(&xs);
	int i,j;
	int time_total = 0;
	double time_avg;
	for (i = 0; i < number_trial; i++) {
		clock_t t0 = clock();
		for (j = 0; j < add_time; j++) {
			arraylist_put(&xs, add_value, 0);
		}
		clock_t t1 = clock();
		time_total += t1 - t0;
	}
	time_avg = (double)time_total / number_trial;

	printf("put %d, %ld times took average %.2lf s", add_value, add_time, time_avg);
	return 0;

}

Prediction

- (true) Arraylist_put with index 0 is much slower than experiment 1

Results 1 (Vista(AMD) at home)

Arraylist_put with index 0
put 2147483647, 1,000    times took average       1.50 s
put 2147483647, 2,000    times took average      14.00 s
put 2147483647, 3,000    times took average      45.20 s
put 2147483647, 4,000    times took average      93.60 s
put 2147483647, 5,000    times took average     154.40 s
put 2147483647, 6,000    times took average     229.30 s
put 2147483647, 7,000    times took average     312.00 s
put 2147483647, 8,000    times took average     414.90 s
put 2147483647, 9,000    times took average     517.80 s
put 2147483647, 10,000   times took average     655.20 s

Results 2 (Vista(AMD) at home)

experiment 1
put 2147483647, 10,000   times took average     1.50 s

Discussion

As expected, Arraylist_put with index 0 is much slower than experiment 1
Retrieved from ‘https://wiki.kram.nz/index.php?title=SE250:lab-3:dcho040&oldid=5497’