faster implementation of sum ( for Codility test )

Question

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"

Solution 1

I don't think your problem is with the function that's summing the array, it's probably that you're summing the array WAY to frequently. If you simply sum the WHOLE array once, and then step through the array until you find the first equilibrium point you should decrease the execution time sufficiently.

int equi ( int[] A ) {
    int equi = -1;

    long lower = 0;
    long upper = 0;
    foreach (int i in A)
        upper += i;

    for (int i = 0; i < A.Length; i++)
    {
        upper -= A[i];
        if (upper == lower)
        {
            equi = i;
            break;
        }
        else
            lower += A[i];
    }

    return equi;
}

Solution 2

Here is my solution and I scored 100%

 public static int solution(int[] A)
    {
        double sum = A.Sum(d => (double)d);
        double leftSum=0;
        for (int i = 0; i < A.Length; i++){
            if (leftSum == (sum-leftSum-A[i])) {
                return i;
            }
            else {
                leftSum = leftSum + A[i];
            }
        }
        return -1;
    }

Solution 3

If this is based on the actual sample problem, your issue isn't the sum. Your issue is how you calculate the equilibrium index. A naive implementation is O(n^2). An optimal solution is much much better.

Solution 4

This code is simple enough that unless a is quite small, it's probably going to be limited primarily by memory bandwidth. As such, you probably can't hope for any significant gain by working on the summing part itself (e.g., unrolling the loop, counting down instead of up, executing sums in parallel -- unless they're on separate CPUs, each with its own access to memory). The biggest gain will probably come from issuing some preload instructions so most of the data will already be in the cache by the time you need it. The rest will just (at best) get the CPU to hurry up more, so it waits longer.

Edit: It appears that most of what's above has little to do with the real question. It's kind of small, so it may be difficult to read, but, I tried just using std::accumulate() for the initial addition, and it seemed to think that was all right:

Solution 5

I don't believe the problem is in the code you provided, but somehow the bigger solution must be suboptimal. This code looks good for calculating the sum of one slice of the array, but maybe it's not what you need to solve the whole problem.

View more solutions