arrays - Swift - 高阶函数的速度和效率(减少)

Question

请快速提问关于大输入数据的高阶 swift 函数的效率。在最近的一次测试中，我有一个关于在数组中查找“平衡索引”的问题 - 即数组的索引，其中索引下方所有元素的总和等于索引上方所有元素的总和

An equilibrium index of this array is any integer P such that 0 ≤ P < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e.

          A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].

挑战在于编写一个短函数来计算第一个(或任何)被认为是“平衡”的索引。 我整理了一个简单的片段，它得分很高，但未能通过一些使用大输入数据(数组大小约为 100,000)的“性能”测试。

这是代码

public func solution(inout A : [Int]) -> Int {
   var index = 0;
        for _ in A {
            let sumBefore = A[0...index].reduce(0) { $0 + $1 }
            let sumAfter = A[index...A.count-1].reduce(0) { $0 + $1 }
            if (sumBefore == sumAfter) { return index; }
            index += 1;
        }
        return -1;
}

谁能解释为什么代码在处理大量数据时表现如此糟糕，或者任何推荐的替代方案？

例如，这是对失败的性能测试的描述:

Large performance test, O(n^2) solutions should fail.

✘ TIMEOUT ERROR running time: >6.00 sec., time limit: 0.22 sec.

Answer 1

看起来挑战失败了，因为您的解决方案是 O(n^2)。

您的 for 循环以及内部的 2 个顺序 reduce 使您的解决方案成为 ~ O(2*n^2) 因为 reduce 再次遍历所有元素。

一个更简单的解决方案是先计算总和，然后遍历一次元素，从总和中逐个减去每个值，从而获得左右总和，以进行比较。

使用 Swift 3.0、Xcode 8:

func findEquilibriumIndex(in array: [Int]) -> Int? {
  var leftSum = 0
  var rightSum = array.reduce(0, combine: +)


  for (index, value) in array.enumerated() {
    rightSum -= value

    if leftSum == rightSum {
        return index
    }

    leftSum += value
  }

  return nil
}

let sampleArray = [-7, 1, 5, 2, -4, 3, 0]

findEquilibriumIndex(in: sampleArray)