I was attempting some codility mock tests, and you get a report at the end, two scores, one for correctness (your program works), and second for performance (it scales well).
The problem is known as TapeEquilibrium, essentially an array traversal segmenting the array and subtracting values, returning the lowest difference.
It was suggested to use Java 8, which I happily attempted.
Can you guys give me any indications why performance is so bad, but also, how it might be improved?
medium_random1, random medium, numbers from 0 to 100, length = ~10,000 8.993 s TIMEOUT ERROR running time: 8.99 sec., time limit: 4.20 sec.
medium_random2 , random medium, numbers from -1,000 to 50, length = ~10,000 9.057 s TIMEOUT ERROR running time: 9.06 sec., time limit: 4.12 sec.
large_ones, large sequence, numbers from -1 to 1, length = ~100,000 >10.000 s TIMEOUT ERROR running time: >10.00 sec., time limit: 4.66 sec.
large_random, random large, length = ~100,000 >10.000 s TIMEOUT ERROR running time: >10.00 sec., time limit: 4.76 sec.
large_sequence, large sequence, length = ~100,000 >10.000 s TIMEOUT ERROR running time: >10.00 sec., time limit: 4.25 sec.
large_extreme, large test with maximal and minimal values, length = ~100,000 >11.000 s TIMEOUT ERROR running time: >11.00 sec., time limit: 5.03 sec.
at first glance: looking at line 19 of your code, you calculate the sum of the
remaining part of the array. That looks like an expensive operation, although
I have no idea how efficient these stream() methods are.
My suggestion is to calculate the total sum first, outside the loop, with
Then, in your loop, you could do
Well, that's what came up, at first sight.
Joined: Jul 18, 2012
Actually you are right, it works. Apologies for the mispost.
Joined: Jul 18, 2012
And after a quick rerun of your solution, you score:
100 out of 100 points
Excellent work! I guess my solution worked, but performance was poor. Ill bear that in mind going forwards. Thanks for your assistance.
Ben Synes wrote: I guess my solution worked, but performance was poor.
My opinion - unless you have a documented need for performance, don't worry about it. Studies say that 50-70% of the cost of any program is the support/maintenance of it, not the writing of it. So you are almost always better off writing clean, simple code you (and everyone else) can UNDERSTAND six weeks later than you would by writing clever code that saves a few seconds (or microseconds as is more often the case).
I am not saying Piet's suggestion is wrong, or complicated, or anything like that - I'm just saying performance should NOT be a primary concern well over 99% of the time.
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors