SE250:lab-3:mspe044
Lab 3 (ArrayList Testing)
Task One: When running an exp to find how long it takes to insert 'n' elements into an ArrayList using arraylist_push I used a 100 million for loop
clk1 = clock();
for (count = 0; count < 100000000; count++) {
arraylist_push( &test_array, 5 );
}
clk2 = clock();
This took 15292 microseconds to complete... I then removed the arraylist_push( &test_array, 5 ) code...
clk1 = clock();
for (count = 0; count < 100000000; count++) {
}
clk2 = clock();
This took 288 microseconds to complete... therefore 100 million arraylist_push comands take ~15000 microseconds on the CS computer I used according to my testing.
Task Two: Test how changign the '* 2' in arraylist put effects the program. I initially tested with the origional code on a '* 4' and a '* 10' value to get a feel for how it was effecting speeds and got this back.
- 2 = 15004
- 4 = 15959
- 10 = 14452...?!?
Neadless to say I was a little confused so decided to re test and check my numbers between 2-10 this time...
2nd Test batch:
- 2 = 15291, 14975, 15835 (avrage = 15367)
- 4 = 15795, 15581, 16279 (avrage = 15885)
- 10 = 14372, 13901, 14105 (avrage = 14126)
My results were reasionably consistant... to be honist I have no idea what it means besides the fact that it shows that the efficency / growth facor has elements of an inverted prabola or some similer effect.
Task Three: Significantly increase the value of ARRAYLIST MIN ALLOC... There is only one way to take this taks... it says significantly so thats what I did, 10* and 100* arraylist min alloc...
(16) Origional ARRAYLIST MIN ALLOC = 15367 (160) 10 * ARRAYLIST MIN ALLOC = 16516, 15787, 15843 (avrage = 16048) (1600) 100 * ARRAYLIST MIN ALLOC = 14985, 15843, 14897 (avrage = 15242)
Any difrences so far were insignificant... so I decided to REALY test wether it made a differece... enter * 5,000
(80000) 5,000 * ARRAYLIST MIN ALLOC = 16276 (single value) (80000) 5,000,000 * ARRAYLIST MIN ALLOC = 15378 (single value)
I gave in... guess it was a trick question.
Task Four: Call ensure capacity to pre-allocate the maximum expected size of the array arr, easy enough, just gave the exact copacity 100000000, sat back and loged the result...
12848, 12716, 12669 (avrage = 12744)
Not bad if you ask me, a good 20% speed boos just from adding this
ensure_capacity(&test_array, capacity);
Task Five: Replace ARRAYLIST MIN ALLOC's *2 value with a +1000 one. This made a HUGE difference to speed, with a large value (my 100 million loop) it took a LONG time, after 5-6 minutes I gave in, with lower values i.e. 100 thousand the speeds compared like this...
+ 1000 = 23, 17, 15 (avrage = 18)
- 2 = 20, 15, 15 (avrage = 17)
So + 1000 is alot less painful at lower array values that when making arrays of around 10 million cells or more. Still, even though its closer to reachign the * 2 methods speed at no truly recordable value is it better (speed wise).
The moral of the story is for large arrays going + 1000 will absolutly hammer the speed it can have cells added on at.
Task Six: Use put rather than push function... with my 100 million cell array this took SO long I gave in, so I tryed 100 thousand cells (established avrage time for push at 100 thou is 17)
Put times were... 4721, 4896, 4756 (avrage = 4791)
The conclusion is im dam lucky I didnt wait long for my 100 million cell test... ANYHOW it would seem adding memory onto the end is alot more plesent on the poor computer than shifting every value in the array along one every single loop... no big suprise there though lol
Armed with a few good questions on why incrasing *2 to *10 made no real difference when changing *2 to +1000 made such a HUGE one at large array sizes (shouldnt it make SOME difference...?) and why ARAYLIST MIN ALLOC size changes made no difference to speed I think ive learned alot in this one, one can hope anyhow...