questions questions - 4 months ago 47
Swift Question

Swift - speed and efficiency of higher order functions (reduce)

Quick question please about the efficiency of higher order swift functions with large input data. During a recent test I had a question about finding 'equlibirum indexes' in arrays- i.e. the index of an array where the sum of all elements below the index equals the sum of all elements above the index


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].



The challenge was to write a short function which computed the first (or any) index which was considered 'equilibirum'.
I put together a simple snippet which scored highly but failed some of the 'performance' tests which used large input data (array sizes around 100,000).

Here's the code

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


Would anyone please be able to explain why the built in functions perform so poorly, or any recommended alternatives?

Here, for example is a description of a failing perfomance test:


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

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

Answer

It looks like the challenge is failing because your solution is O(n^2).

Your for loop, along with 2 sequential reduces inside, make your solution ~ O(2*n^2) since reduce goes through all the elements again.

A simpler solution is to first compute the whole sum, and then iterate through the elements once, subtracting each value from the whole sum, one by one, thus having access to the left and right sums, for comparison.

Using 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)
Comments