SE250:lab-3:aomr001
task1
code:
int main(){
ArrayList mylist;
int i,x;
arraylist_init(&mylist);
x= clock();
for( i=0; i < 1000000; i++){
arraylist_push(&mylist,4);
}
x = clock() - x;
printf("the operation took %d ms to push 1 million elements into the array.",x);
return 0;
}
output:
the operation took 46 ms to push 1 million elements into the array
i changed the number i was adding to 400:
the operation took 47 ms to push 1 million elements into the array.
task2
i changed the growth factor inside the push function to :
(int)(alist->capacity *90000000 ) (int)(alist->capacity * 4.0) (int)(alist->capacity * 3.0) (int)(alist->capacity * 1.8) (int)(alist->capacity * 1.5) (int)(alist->capacity * 1.2) (int)(alist->capacity * 1.1) (int)(alist->capacity * 1.05)
output:
ERROR: assertion "alist->arr != (element_t*)0" failed: file "arraylist-2.c", line 39 /usr/bin/bash: line 1: 3024 Hangup ./arraylist-2.exe the operation took 46 ms to push 1 million elements into the array. the operation took 47 ms to push 1 million elements into the array. the operation took 46 ms to push 1 million elements into the array. the operation took 61 ms to push 1 million elements into the array. the operation took 93 ms to push 1 million elements into the array. the operation took 156 ms to push 1 million elements into the array. ERROR: /usr/bin/bash: line 1: 4960 Segmentation fault (core dumped) ./arraylist-2.exe
comment: It's clear that as the factor is decreased the time taken is increased. This is mainly because of the way reallocations work, if all of the space availabe is used a new BIGGER array is created and all of the values are copied into it, new data will be copied until there is no enough space for new data to be copied .. another array is created. The smaller the array created the more we are going to need to create arry, move data , which obviously takes more time.
Very large factors would exhaust all of the memory available and cause the program to crash. Very small factors would mean that there is no enough space to add new element which also crashed the program.
task3
#define ARRAYLIST_MIN_ALLOC 10000000 #define ARRAYLIST_MIN_ALLOC 1000000 #define ARRAYLIST_MIN_ALLOC 1000 #define ARRAYLIST_MIN_ALLOC 90 #define ARRAYLIST_MIN_ALLOC 60 #define ARRAYLIST_MIN_ALLOC 9 #define ARRAYLIST_MIN_ALLOC 2 #define ARRAYLIST_MIN_ALLOC 1 #define ARRAYLIST_MIN_ALLOC 0
output:
the operation took 47 ms to push 1 million elements into the array. the operation took 46 ms to push 1 million elements into the array. the operation took 47 ms to push 1 million elements into the array. the operation took 46 ms to push 1 million elements into the array. the operation took 62 ms to push 1 million elements into the array. the operation took 62 ms to push 1 million elements into the array. the operation took 78 ms to push 1 million elements into the array. the operation took 63 ms to push 1 million elements into the array. /usr/bin/bash: line 1: 4860 Segmentation fault (core dumped) ./arraylist-2.exe
comment:
Starting with a small array would mean that it will take shorter time until the it's forced to created a bigger array,
while starting with a large array would save time .. as the array doesn't have to go through the proccess
of creating and move elements to a new array.
task 4
int main(){
ArrayList mylist;
int i,x;
arraylist_init(&mylist);
ensure_capacity(&mylist,1000000);
x= clock();
for( i=0; i < 1000000; i++){
arraylist_push(&mylist,4);
}
x = clock() - x;
printf("the operation took %d ms to push 1 million elements into the array.",x);
return 0;
}
output:
the operation took 31 ms to push 1 million elements into the array.
comment: the program doesnt have to creat a new bigger array every time .. as it already knows how much it needs and was created with the exact number of elements as it needs.
task5
(int)(alist->capacity + 10000) (int)(alist->capacity + 1000) (int)(alist->capacity + 300) (int)(alist->capacity + 100)
the operation took 47 ms to push 1 million elements into the array. the operation took 46 ms to push 1 million elements into the array. the operation took 46 ms to push 1 million elements into the array. the operation took 46 ms to push 1 million elements into the array.
task6
int main(){
ArrayList mylist;
int i,x;
arraylist_init(&mylist);
x= clock();
for( i=0; i < 10000; i++){
arraylist_put(&mylist,4,0);
}
x = clock() - x;
printf("the operation took %d ms to push 1 million elements into the array.",x);
return 0;
}
output:
the operation took 47 ms to push 1 million elements into the array.