questions - 1 year ago 125

Swift Question

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 Source

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

.

Your `for`

loop, along with 2 sequential `reduce`

s 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)
```