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.
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.functest1(intArray:[Int])->[Int]{// initalize with all values being multiplicitive indenity so we can just roll all the multiplication togethervarnewArray:[Int]=[Int](repeating:1,count:intArray.count)forindexin0..<intArray.count{forsearchIndexin0..<intArray.count{// make sure the search index isnt the slot we are currently working on calculating, then roll on the multiplication.ifindex!=searchIndex{newArray[index]*=intArray[searchIndex]}}}returnnewArray}// Attempted to use some built in array mutating functions and.... TERRRRRIIIIBLE CPU hog.// ~1.46 MINUTES for 5mil runs on test data.functest2(intArray:[Int])->[Int]{varresult:[Int]=[Int](repeating:1,count:intArray.count)forindexin0..<intArray.count{lettmp=intArray.filter({$0!=intArray[index]})result[index]=tmp.reduce(1,*)}returnresult}// Attempted solution similar to authors, but with only using arrays, then combining the results.// ~10 sec per 5mil runs on test data.... failfunctest3(intArray:[Int])->[Int]{// initalize all working arrays with multiplicative identity 1varforwardPass=[Int](repeating:1,count:intArray.count)varreversePass=[Int](repeating:1,count:intArray.count)varresult=[Int](repeating:1,count:intArray.count)// cumulatively multiply forwardsforindexin1..<intArray.count{forwardPass[index]=forwardPass[index-1]*intArray[index-1]}// cumulatively multiply backwardsforindexin(0..<intArray.count-1).reversed(){reversePass[index]=reversePass[index+1]*intArray[index+1]}// multiply the two accumulation arrays together for the final result.forindexin0..<intArray.count{result[index]=forwardPass[index]*reversePass[index]}returnresult}// Solution posted by author, adapted to Swift. // ~3.15 sec per 5mil runs on test data. Hands down winner.functest4(intArray:[Int])->[Int]{varresult:[Int]=[Int](repeating:1,count:intArray.count)varproduct=1forindexin0..<intArray.count{result[index]=productproduct*=intArray[index]}product=1forindexin(0..<intArray.count).reversed(){result[index]*=productproduct*=intArray[index]}returnresult}
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:
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.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Your solution is O(n2) 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:
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:
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:
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.