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

以下简单的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”

我认为你的问题不在于对数组进行求和的函数,可能是你经常将数组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; } 

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

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

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

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

Codility结果

我不相信问题出在您提供的代码中,但不知何故,更大的解决方案必须是次优的。 这段代码看起来很适合计算一个数组的总和,但也许并不是解决整个问题所需要的。

一些技巧:

  • 使用分析器确定您花费大量时间的位置。

  • 编写出色的性能测试,以便您可以确定每次更改的确切效果。 记下小心的笔记。

  • 如果事实certificate瓶颈是确保您在arrays中取消引用合法地址的检查,并且您可以保证开始和结束实际上都在数组内,那么考虑修复数组,制作指针数组,并在指针而不是数组中执行算法。 指针不安全; 他们不会花任何时间检查以确保你仍然在arrays中,所以他们可以更快一些。 但是要承担责任,以确保你不会破坏地址空间中的每个内存字节。

您可能获得的最快速度可能是将int数组对齐16个字节,将32个字节流式传输到两个__m128i变量(VC ++)中,并在块上调用_mm_add_epi32 (同样是VC ++内部函数)。 重复使用其中一个块继续添加到它中,并在最后一个块上提取你的四个整数并以旧式方式添加它们。

更大的问题是为什么简单的加法是一个值得优化的候选者。

编辑:我认为这主要是学术练习。 也许我明天会试一试并发布一些结果……

在C#3.0中, 我的计算机和我的操作系统更快,只要你可以保证4个连续数字不会溢出int的范围,可能是因为大多数添加是使用32位数学运算完成的。 然而,使用更好的算法通常比任何微优化提供更高的速度。

100毫安元素arrays的时间:

4999912596452418 – > 233ms(总和)

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

我做了同样天真的实现,这是我的O(n)解决方案。 我没有使用IEnumerable Sum方法,因为它在Codility上不可用。 我的解决方案仍然没有检查溢出,如果输入有大数字,所以它没有在Codility上的特定测试失败。

 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ConsoleApplication2 { class Program { static void Main(string[] args) { var list = new[] {-7, 1, 5, 2, -4, 3, 0}; Console.WriteLine(equi(list)); Console.ReadLine(); } static int equi(int[] A) { if (A == null || A.Length == 0) return -1; if (A.Length == 1) return 0; var upperBoundSum = GetTotal(A); var lowerBoundSum = 0; for (var i = 0; i < A.Length; i++) { lowerBoundSum += (i - 1) >= 0 ? A[i - 1] : 0; upperBoundSum -= A[i]; if (lowerBoundSum == upperBoundSum) return i; } return -1; } private static int GetTotal(int[] ints) { var sum = 0; for(var i=0; i < ints.Length; i++) sum += ints[i]; return sum; } } } 

Codility结果

这是一个想法:

 private static ArrayList equi(int[] A) { ArrayList answer = new ArrayList(); //if(A == null) return -1; if ((answer.Count == null)) { answer.Add(-1); return answer; } long sum0 = 0, sum1 = 0; for (int i = 0; i < A.Length; i++) sum0 += A[i]; for (int i = 0; i < A.Length; i++) { sum0 -= A[i]; if (i > 0) { sum1 += A[i - 1]; } if (sum1 == sum0) answer.Add(i); //return i; } //return -1; return answer; } 

如果您正在使用C或C ++并为现代桌面系统开发并且愿意学习一些汇编程序或了解GCC内在函数,那么您可以使用SIMD指令 。

这个库是floatdouble数组可能的一个例子,因为SSE也有整数指令,所以整数算术也应该有类似的结果。

在C ++中,以下内容:

 int* a1 = a + begin; for( int i = end - begin - 1; i >= 0 ; i-- ) { r+= a1[i]; } 

可能会更快。 优点是我们在循环中与零进行比较。

当然,有一个非常好的优化器,应该没有任何区别。

另一种可能性是

 int* a2 = a + end - 1; for( int i = -(end - begin - 1); i <= 0 ; i++ ) { r+= a2[i]; } 

在这里,我们以相同的顺序遍历项目,而不是与end进行比较。

只是一些想法,不确定是否直接访问指针更快

  int* pStart = a + begin; int* pEnd = a + end; while (pStart != pEnd) { r += *pStart++; } 

这对O(n ^ 2)算法没有帮助,但您可以优化您的总和。

在之前的公司,我们让英特尔过来并给我们优化提示。 他们有一个非显而易见的,有点酷的伎俩。 更换:

 long r = 0; for( int i = begin ; i < end ; i++ ) { r+= a[i]; } 

 long r1 = 0, r2 = 0, r3 = 0, r4 = 0; for( int i = begin ; i < end ; i+=4 ) { r1+= a[i]; r2+= a[i + 1]; r3+= a[i + 2]; r4+= a[i + 3]; } long r = r1 + r2 + r3 + r4; // Note: need to be clever if array isn't divisible by 4 

为什么这样更快:在原始实现中,变量r是一个瓶颈。 每次循环时,你必须从存储器arraysa中抽取数据(这需要几个周期),但你不能并行执行多次拉动,因为循环的下一次迭代中r的值取决于值在这个迭代循环中的r。 在第二个版本中,r1,r2,r3和r4是独立的,因此处理器可以超线程执行它们。 只有在最后他们才能走到一起。

 {In Pascal + Assembly} {$ASMMODE INTEL} function equi (A : Array of longint; n : longint ) : longint; var c:Longint; label noOverflow1; label noOverflow2; label ciclo; label fine; label Over; label tot; Begin Asm DEC n JS over XOR ECX, ECX {Somma1} XOR EDI, EDI {Somma2} XOR EAX, EAX MOV c, EDI MOV ESI, n tot: MOV EDX, A MOV EDX, [EDX+ESI*4] PUSH EDX ADD ECX, EDX JNO nooverflow1 ADD c, ECX nooverflow1: DEC ESI JNS tot; SUB ECX, c SUB EDI, c ciclo: POP EDX SUB ECX, EDX CMP ECX, EDI JE fine ADD EDI, EDX JNO nooverflow2 DEC EDI nooverflow2: CMP EAX, n JA over INC EAX JMP ciclo over: MOV EAX, -1 fine: end; End; 

C中的100%O(n)溶液

 int equi ( int A[], int n ) { long long sumLeft = 0; long long sumRight = 0; int i; if (n <= 0) return -1; for (i = 1; i < n; i++) sumRight += A[i]; i = 0; do { if (sumLeft == sumRight) return i; sumLeft += A[i]; if ((i+1) < n) sumRight -= A[i+1]; i++; } while (i < n); return -1; } 

可能不完美,但无论如何它都通过了他们的测试:)

不能说我是Codility的忠实粉丝 - 这是一个有趣的想法,但我发现这些要求有点过于模糊。 我想如果他们给你的要求+一套测试这些要求的unit testing, 然后要求你编写代码,我会更感动。 无论如何,这就是大多数TDD的发生方式。 我不认为盲目地做任何事情除了允许他们抛出一些角落案件之外。

 private static int equi ( int[] A ) { if (A == null || A.length == 0) return -1; long tot = 0; int len = A.length; for(int i=0;i 

}

我认为arrays是双性的,所以如果存在均衡指数,那么一半的权重在左边。 所以我只将partTot(部分总数)x 2与数组的总重量进行比较。 Alg取O(n)+ O(n)

测试此代码的100%正确性和性能

 Private Function equi(ByVal A() As Integer) As Integer Dim index As Integer = -1 If A.Length > 0 And Not IsDBNull(A) Then Dim sumLeft As Long = 0 Dim sumRight As Long = ArraySum(A) For i As Integer = 0 To A.Length - 1 Dim val As Integer = A(i) sumRight -= val If sumLeft = sumRight Then index = i End If sumLeft += val Next End If Return index End Function 

这让我100%使用Javascript:

 function solution(A) { if (!(A) || !(Array.isArray(A)) || A.length < 1) { return -1; } if (A.length === 1) { return 0; } var sum = A.reduce(function (a, b) { return a + b; }), lower = 0, i, val; for (i = 0; i < A.length; i++) { val = A[i]; if (((sum - lower) - val) === (lower)) { return i; } lower += val; } return -1; } 

平衡测试结果截图(Javascript)

这是我的回答以及如何解决它的解释。 它会让你100%

 class Solution { public int solution(int[] A) { long sumLeft = 0; //Variable to hold sum of elements to the left of the current index long sumRight = 0; //Variable to hold sum of elements to the right of the current index long sum = 0; //Variable to hold sum of all elements in the array long leftHolder = 0; //Variable that holds the sum of all elements to the left of the current index, including the element accessed by the current index //Calculate the total sum of all elements in the array and store it in the sum variable for (int i = 0; i < A.Length; i++) { //sum = A.Sum(); sum += A[i]; } for (int i = 0; i < A.Length; i++) { //Calculate the sum of all elements before the current element plus the current element leftHolder += A[i]; //Get the sum of all elements to the right of the current element sumRight = sum - leftHolder; //Get the sum of all elements of elements to the left of the current element.We don't include the current element in this sum sumLeft = sum - sumRight - A[i]; //if the sum of the left elements is equal to the sum of the right elements. Return the index of the current element if (sumLeft == sumRight) return i; } //Otherwise return -1 return -1; } } 

我为这一个得分100%:

 int equi (int[] A) { if (A == null) return -1; long sum0 = 0, sum1 = 0; for (int i = 0; i < A.Length; i++) sum0 += A[i]; for (int i = 0; i < A.Length; i++) { sum0 -= A[i]; if (i > 0) { sum1 += A[i - 1]; } if (sum1 == sum0) return i; } return -1; } 

这可能是旧的,但这里是Golang的解决方案,通过率为100%:

 package solution func Solution(A []int) int { // write your code in Go 1.4 var left int64 var right int64 var equi int equi = -1 if len(A) == 0 { return equi } left = 0 for _, el := range A { right += int64(el) } for i, el := range A { right -= int64(el) if left == right { equi = i } left += int64(el) } return equi }