Discussion on: 6-10PM challenge problem #002

View post

Replies for: Swift Solution: import Foundation /* 6-10PM Challenge part 2 @param intArray is a list of Ints which are to be multiplied together ...

Your solution is O(n²⁾ time complexity. You should try for more optimized solution.

After posting my first solution, I took a look at yours, and now I can't unsee it. So I took some time trying to come up with another creative solution, but in the end, I couldn't figure out anything that was more efficient than what you had posted.

I ran everything I tried through a little repetitive test to see how different approaches stacked up, so here's a quick rundown.

Basic test setup:

let testData1 = [8, 10, 2]
let testData2 = [2, 7, 3, 4]
let testData3 = [2, 7, 3, 4, 6, 5, 9, 11, 14, 25, 12, 13, 15, 18, 34, 27]
var result1:[Int] = []
var result2:[Int] = []
var result3:[Int] = []


for _ in 0...5000000 {
    result1 = test1(intArray: testData1)
    result2 = test1(intArray: testData2)
    result3 = test1(intArray: testData3)
}
print(result1, "\n", result2, "\n", result3)

There is definitely a little overhead, but since they all ran through the same setup, I figured at least relatively speaking, the results should still be informative.

And here are the different functions tested:

//  Baseline test.  First attempt at coding this challenge, 
//   ~5.9sec per 5mil runs on test data.
func test1(intArray:[Int]) -> [Int] {
     //  initalize with all values being multiplicitive indenity so we can just roll all the multiplication together
    var newArray:[Int] = [Int](repeating: 1, count: intArray.count)

    for index in 0..<intArray.count {
        for searchIndex in 0..<intArray.count {
            //  make sure the search index isnt the slot we are currently working on calculating, then roll on the multiplication.
            if index != searchIndex {
                newArray[index] *= intArray[searchIndex]
            }
        }
    }

    return newArray
}

// Attempted to use some built in array mutating functions and.... TERRRRRIIIIBLE CPU hog.
// ~1.46 MINUTES for 5mil runs on test data.
func test2(intArray:[Int]) -> [Int] {
    var result:[Int] = [Int](repeating: 1, count: intArray.count)

    for index in 0..<intArray.count {
        let tmp = intArray.filter({ $0 != intArray[index] })
        result[index] = tmp.reduce(1, *)
    }

    return result
}

//  Attempted solution similar to authors, but with only using arrays, then combining the results.
//  ~10 sec per 5mil runs on test data.... fail
func test3(intArray:[Int]) -> [Int] {
    // initalize all working arrays with multiplicative identity 1
    var forwardPass = [Int](repeating: 1, count: intArray.count)
    var reversePass = [Int](repeating: 1, count: intArray.count)
    var result      = [Int](repeating: 1, count: intArray.count)

    // cumulatively multiply forwards
    for index in 1..<intArray.count {
        forwardPass[index] = forwardPass[index-1]*intArray[index-1]
    }
    // cumulatively multiply backwards
    for index in (0..<intArray.count-1).reversed() {
        reversePass[index] = reversePass[index+1]*intArray[index+1]
    }
    // multiply the two accumulation arrays together for the final result.
    for index in 0..<intArray.count {
        result[index] = forwardPass[index]*reversePass[index]
    }

    return result
}


//  Solution posted by author, adapted to Swift.    
//  ~3.15 sec per 5mil runs on test data.  Hands down winner.
func test4(intArray:[Int]) -> [Int] {
    var result:[Int] = [Int](repeating: 1, count: intArray.count)
    var product = 1

    for index in 0..<intArray.count {
        result[index] = product
        product *= intArray[index]
    }

    product = 1
    for index in (0..<intArray.count).reversed() {
        result[index] *= product
        product *= intArray[index]
    }

    return result
}

I also noticed that over the course of 5mil(*3) runs, the overhead difference of creating an empty array and filling it vs initializing an array already of the full size you're going to use is pretty huge. ie:

var array1:[Int] = []

for _ 1...50 {
    array1.append(1)
}
//  vs
var array2:[Int] = [Int](repeating: 1, count: 50)

test1() dropped from 8.5 sec to about 5.9 sec once I made that small change.

So between that and the revelation about how slow .filter() and .reduce() are in swift, Id say if you're serious about performance, it's going to be super important to really understand what's going on behind the scenes of all these standard libraries we take for granted.