faster implementation of sum ( for Codility test )
- by Oscar Reyes
How can the following simple implementation of sum be faster?
private long sum( int [] a, int begin, int end ) {
if( a == null ) {
return 0;
}
long r = 0;
for( int i = begin ; i < end ; i++ ) {
r+= a[i];
}
return r;
}
EDIT
Background is in order.
Reading latest entry on coding horror, I came to this site: http://codility.com which has this interesting programming test.
Anyway, I got 60 out of 100 in my submission, and basically ( I think ) is because this implementation of sum, because those parts where I failed are the performance parts. I'm getting TIME_OUT_ERROR's
So, I was wondering if an optimization in the algorithm is possible.
So, no built in functions or assembly would be allowed. This my be done in C, C++, C#, Java or pretty much in any other.
EDIT
As usual, mmyers was right. I did profile the code and I saw most of the time was spent on that function, but I didn't understand why. So what I did was to throw away my implementation and start with a new one.
This time I've got an optimal solution [ according to San Jacinto O(n) -see comments to MSN below - ]
This time I've got 81% on Codility which I think is good enough. The problem is that I didn't take the 30 mins. but around 2 hrs. but I guess that leaves me still as a good programmer, for I could work on the problem until I found an optimal solution:
Here's my result.
I never understood what is those "combinations of..." nor how to test "extreme_first"
