[swift-users] problems with simple binary-trees program

[Maurus Kühne]

> On 20.12.2015, at 19:08, Isaac Gouy via swift-users <swift-users at swift.org> wrote:
> 
>> On Sunday, December 20, 2015 9:58 AM, Pascal Urban <mail at pscl.de> wrote:
> 
> ...
>> Both of these implementations are slow because they always create binary trees 
> 
>> with a depth of maxDepth instead of, well, the correct depth.
> 
> Thank you!
> 
> As always, I suspected I'd made a dumb mistake - but just wasn't seeing it.
> _______________________________________________
> swift-users mailing list
> swift-users at swift.org
> https://lists.swift.org/mailman/listinfo/swift-users


I was able to speed up David’s solution by almost 50% by changing the method checkTree from this:

func checkTree(t: Array<TreeNodeItem>, _ i: Int) -> Int

to this:

func checkTree(inout t: Array<TreeNodeItem>, _ i: Int) -> Int

It completes in about ~10s instead of ~20s on my 2.66GHz i5 iMac for n=20. 
This also works together with Pascal’s libdispatch solution. In this case it completes in ~5s.
Here is the modified version: https://gist.github.com/mauruskuehne/633789417c2357a6bb93 <https://gist.github.com/mauruskuehne/633789417c2357a6bb93>

Could somebody explain to me why this is the case? I know what the inout keyword does, but I don’t understand why it makes the code faster in this case?

Maurus
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-users/attachments/20151220/8231cb67/attachment.html>