更快实现sum（用于编译测试）

问题描述

sum 的下列简单实现如何更快？

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

背景是有序的。

读取编码恐怖的最新条目，我来到这个网站：，它有这个有趣的编程测试。

Reading latest entry on coding horror, I came to this site: http://codility.com which has this interesting programming test.

无论如何，我在我提交的100中有60个，基本上（我认为）是因为这个实现的sum，因为那些我失败的部分是性能部分。我得到TIME_OUT_ERROR的

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.

因此，不允许内置函数或程序集。这我可以在C，C ++，C＃，Java或几乎任何其他。

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.

编辑

像往常一样，mmyers是对的。我做了配置文件的代码，我看到大部分时间花在那个功能，但我不明白为什么。所以我做的是丢弃我的实现，并从一个新的开始。

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.

这次我有一个最佳解决方案[根据 O（n） - 见MSN下面的评论 - ]

This time I've got an optimal solution [ according to San Jacinto O(n) -see comments to MSN below - ]

这次我有81％的Codability，我认为足够好。问题是，我没有采取30分钟。但约2小时。但我想，让我仍然是一个好的程序员，因为我可以解决这个问题，直到我找到一个最佳解决方案：

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:

这里是我的结果。

我从来没有理解什么是组合...，也没有如何测试extreme_first

I never understood what is those "combinations of..." nor how to test "extreme_first"

推荐答案

我不认为你的问题是与数组求和的函数，可能是你经常将数组WAY求和。如果你只是简单的总和一个数组，然后遍历数组，直到你找到第一个均衡点，你应该减少执行时间充分。

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;
}

这篇关于更快实现sum（用于编译测试）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！