更快实现总和(用于Codility测试)

Question

以下简单实现如何才能sum更快？

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

编辑

背景是有序的.

阅读关于编码恐怖的最新条目,我来到这个网站:http://codility.com,它有这个有趣的编程测试.

无论如何,我在提交中得到了60分中的60分,而且基本上(我认为)是因为这个实现总和,因为那些我失败的部分是性能部分.我得到TIME_OUT_ERROR了

所以,我想知道算法中的优化是否可行.

因此,不允许内置函数或汇编.我可以用C,C++,C#,Java或其他任何方式完成.

编辑

像往常一样,mmyers是对的.我确实对代码进行了分析,我看到大部分时间花在了这个函数上,但我不明白为什么.所以我所做的就是抛弃我的实现并从一个新实现开始.

这次我得到了一个最佳解决方案[根据San Jacinto O(n) - 请参阅下面的MSN评论 - ]

这次我在Codility上获得了81%,我认为这已经足够了.问题是我没有花30分钟.但大约2小时.但我想这让我仍然是一个优秀的程序员,因为我可以解决这个问题,直到找到最佳解决方案:

这是我的结果.

我对codility的结果http://img534.imageshack.us/img534/6804/codility.png

我从来不明白那些"......的组合"是什么,也不知道如何测试"extreme_first"

Answer 1

我不认为你的问题在于对数组进行求和的函数,可能是你经常将数组WAY求和.如果您只是将WHOLE数组求和一次,然后逐步遍历数组直到找到第一个平衡点,则应该充分减少执行时间.

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

Answer 2

这是我的解决方案,我得分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;
    }

Answer 3

这段代码是很简单的,除非a是相当小的,它可能会被内存带宽主要限于.因此,你可能不希望通过处理求和部分本身来获得任何显着的收益(例如,展开循环,倒数而不是向上,并行执行求和 - 除非它们在单独的CPU上,每个都有它的自己访问内存).最大的收益可能来自发布一些预加载指令,因此大多数数据在您需要时已经在缓存中.剩下的就是(充其量)让CPU快点起来,所以等待的时间更长.

编辑:看来上面的大部分内容与真正的问题没什么关系.它有点小,所以可能难以阅读,但是,我尝试使用std::accumulate()初始添加,它似乎认为这是正常的:

Answer 4

如果这是基于实际的样本问题,那么您的问题不是总和.您的问题是如何计算均衡指数.天真的实现是O(n ^ 2).最佳解决方案要好得多.