faster implementation of sum ( for Codility test )

Asked 2010-02-25T23:23:04.133

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"

Edit Report

2 Answers

In C# 3.0, my computer and my OS this is faster as long as you can guarantee that 4 consecutive numbers won't overflow the range of an int, probably because most additions are done using 32-bit math. However using a better algorithm usually provides higher speed up than any micro-optimization.

Time for a 100 millon elements array:

4999912596452418 -> 233ms (sum)

4999912596452418 -> 126ms (sum2)

    private static long sum2(int[] a, int begin, int end)
    {
        if (a == null) { return 0; }
        long r = 0;
        int i = begin;
        for (; i < end - 3; i+=4)
        {
            //int t = ;
            r += a[i] + a[i + 1] + a[i + 2] + a[i + 3];
        }
        for (; i < end; i++) { r += a[i]; }
        return r;
    }

answered 2010-02-26T00:20:28.793

If you are using C or C++ and develop for modern desktop systems and are willing to learn some assembler or learn about GCC intrinsics, you could use SIMD instructions.

This library is an example of what is possible for float and double arrays, similar results should be possible for integer arithmetic since SSE has integer instructions as well.

answered 2010-02-25T23:36:22.137

faster implementation of sum ( for Codility test )

2 Answers

Your Answer