The Computer Language Benchmarks Game - Swift binary trees

main.swift

import CoreFoundation

func type1(n:Int) {

    /* The Computer Language Benchmarks Game
    http://benchmarksgame.alioth.debian.org/
    contributed by David Turnbull
    */

    struct TreeNodeItem {
        let left:Int
        let right:Int
        let item:Int
    }

    func buildTree(inout t: Array<TreeNodeItem>, _ item: Int, _ depth: Int) -> Int {
        if depth > 0 {
            t.append(
                TreeNodeItem(
                    left: buildTree(&t, 2*item-1, depth-1),
                    right:buildTree(&t, 2*item, depth-1),
                    item: item
                )
            )
            return t.count - 1
        } else {
            t.append(TreeNodeItem(left: -1, right: -1, item: item))
            return t.count - 1
        }
    }

    func checkTree(t: Array<TreeNodeItem>, _ i: Int) -> Int {
        if t[i].left < 0 {
            return 0
        } else {
            return t[i].item + checkTree(t, t[i].left) - checkTree(t, t[i].right)
        }
    }


    let minDepth = 4
    let maxDepth = n
    let stretchDepth = n + 1

    var longLivedPool = Array<TreeNodeItem>()

    var longLivedTree = buildTree(&longLivedPool, 0, stretchDepth)


    let chk = checkTree(longLivedPool, longLivedTree)
    print("stretch tree of depth \(stretchDepth)\t check: \(chk)")

    longLivedPool.removeAll(keepCapacity: true)
    longLivedTree = buildTree(&longLivedPool, 0, maxDepth)

    var shortLivedPool = Array<TreeNodeItem>()
    for var depth=minDepth; depth<=maxDepth; depth+=2 {
        let iterations = 1 << (maxDepth - depth + minDepth)
        var check = 0
        for i in 1...iterations {
            shortLivedPool.removeAll(keepCapacity: true)
            let t1 = buildTree(&shortLivedPool, i, depth)
            check += checkTree(shortLivedPool, t1)
            shortLivedPool.removeAll(keepCapacity: true)
            let t2 = buildTree(&shortLivedPool, -i, depth)
            check += checkTree(shortLivedPool, t2)
        }
        print("\(iterations*2)\t trees of depth \(depth)\t check: \(check)")
    }

    print("long lived tree of depth \(maxDepth)\t check: \(checkTree(longLivedPool, longLivedTree))")

}




func type2(n:Int) {

    /* The Computer Language Benchmarks Game
    http://benchmarksgame.alioth.debian.org/
    contributed by Isaac Gouy
    */

    class TreeNode {
        var left, right : TreeNode?
        var item : Int

        init(_ left: TreeNode?, _ right: TreeNode?, _ item: Int) {
            self.left = left
            self.right = right
            self.item = item
        }

        func check() -> Int {
            guard let left = left, let right = right else {
                return item
            }
            return item + left.check() - right.check()
        }
    }

    func bottomUpTree(item: Int, _ depth: Int) -> TreeNode {
        return
            depth > 0
                ?
                    TreeNode(
                        bottomUpTree(2*item-1, depth-1),
                        bottomUpTree(2*item, depth-1),
                        item
                    )
                :
                TreeNode(nil,nil,item)
    }


    let minDepth = 4
    let maxDepth = n
    let stretchDepth = n + 1

    let check = bottomUpTree(0,stretchDepth).check()
    print("stretch tree of depth \(stretchDepth)\t check: \(check)")

    let longLivedTree = bottomUpTree(0,maxDepth)

    for var depth=minDepth; depth<=maxDepth; depth+=2 {
        let iterations = 1 << (maxDepth - depth + minDepth)
        var check = 0
        for i in 1...iterations {
            check += bottomUpTree(i,depth).check()
            check += bottomUpTree(-i,depth).check()
        }
        print("\(iterations*2)\t trees of depth \(depth)\t check: \(check)")
    }
    print("long lived tree of depth \(maxDepth)\t check: \(longLivedTree.check())")

}

func type3(n:Int) {

    /* The Computer Language Benchmarks Game
    http://benchmarksgame.alioth.debian.org/
    contributed by David Turnbull
    modified by Pascal Urban (parallel creation of binary trees using libdispatch)
    */

    struct TreeNodeItem {
        let left:Int
        let right:Int
        let item:Int
    }

    func buildTree(inout t: Array<TreeNodeItem>, _ item: Int, _ depth: Int) -> Int {
        if depth > 0 {
            t.append(
                TreeNodeItem(
                    left: buildTree(&t, 2*item-1, depth-1),
                    right:buildTree(&t, 2*item, depth-1),
                    item: item
                )
            )
            return t.count - 1
        } else {
            t.append(TreeNodeItem(left: -1, right: -1, item: item))
            return t.count - 1
        }
    }

    func checkTree(t: Array<TreeNodeItem>, _ i: Int) -> Int {
        if t[i].left < 0 {
            return 0
        } else {
            return t[i].item + checkTree(t, t[i].left) - checkTree(t, t[i].right)
        }
    }


    let minDepth = 4
    let maxDepth = n
    let stretchDepth = n + 1

    var longLivedPool = Array<TreeNodeItem>()

    var longLivedTree = buildTree(&longLivedPool, 0, stretchDepth)


    let chk = checkTree(longLivedPool, longLivedTree)
    print("stretch tree of depth \(stretchDepth)\t check: \(chk)")

    longLivedPool.removeAll(keepCapacity: true)
    longLivedTree = buildTree(&longLivedPool, 0, maxDepth)

    let numberOfIterations = (maxDepth - minDepth) / 2 + 1
    var checksumOutput = Array<Int>(count: numberOfIterations, repeatedValue: 0)

    dispatch_apply(numberOfIterations, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0)) { (depthIteration) in
        var shortLivedPool = Array<TreeNodeItem>()
        let depth = minDepth + depthIteration * 2

        let iterations = 1 << (maxDepth - depth + minDepth)
        var check = 0
        for i in 1...iterations {
            shortLivedPool.removeAll(keepCapacity: true)
            let t1 = buildTree(&shortLivedPool, i, depth)
            check += checkTree(shortLivedPool, t1)
            shortLivedPool.removeAll(keepCapacity: true)
            let t2 = buildTree(&shortLivedPool, -i, depth)
            check += checkTree(shortLivedPool, t2)
        }

        checksumOutput[depthIteration] = check
    }

    for depthIteration in (0..<checksumOutput.count) {
        let depth = minDepth + depthIteration * 2
        let iterations = 1 << (maxDepth - depth + minDepth)
        let check = checksumOutput[depthIteration]

        print("\(iterations*2)\t trees of depth \(depth)\t check: \(check)")
    }

    print("long lived tree of depth \(maxDepth)\t check: \(checkTree(longLivedPool, longLivedTree))")

}

func type4(n:Int) {
    
    /* The Computer Language Benchmarks Game
    http://benchmarksgame.alioth.debian.org/
    contributed by David Turnbull
    modified by Pascal Urban (parallel creation of binary trees using libdispatch)
    modified by Maurus Kühne (checkTree uses inout parameters)
    */
    
    struct TreeNodeItem {
        let left:Int
        let right:Int
        let item:Int
    }
    
    func buildTree(inout t: Array<TreeNodeItem>, _ item: Int, _ depth: Int) -> Int {
        if depth > 0 {
            t.append(
                TreeNodeItem(
                    left: buildTree(&t, 2*item-1, depth-1),
                    right:buildTree(&t, 2*item, depth-1),
                    item: item
                )
            )
            return t.count - 1
        } else {
            t.append(TreeNodeItem(left: -1, right: -1, item: item))
            return t.count - 1
        }
    }
    
    func checkTree(inout t: Array<TreeNodeItem>, _ i: Int) -> Int {
        if t[i].left < 0 {
            return 0
        } else {
            return t[i].item + checkTree(&t, t[i].left) - checkTree(&t, t[i].right)
        }
    }
    
    
    let minDepth = 4
    let maxDepth = n
    let stretchDepth = n + 1
    
    var longLivedPool = Array<TreeNodeItem>()
    
    var longLivedTree = buildTree(&longLivedPool, 0, stretchDepth)
    
    
    let chk = checkTree(&longLivedPool, longLivedTree)
    print("stretch tree of depth \(stretchDepth)\t check: \(chk)")
    
    longLivedPool.removeAll(keepCapacity: true)
    longLivedTree = buildTree(&longLivedPool, 0, maxDepth)
    
    let numberOfIterations = (maxDepth - minDepth) / 2 + 1
    var checksumOutput = Array<Int>(count: numberOfIterations, repeatedValue: 0)
    
    dispatch_apply(numberOfIterations, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0)) { (depthIteration) in
        var shortLivedPool = Array<TreeNodeItem>()
        let depth = minDepth + depthIteration * 2
        
        let iterations = 1 << (maxDepth - depth + minDepth)
        var check = 0
        for i in 1...iterations {
            shortLivedPool.removeAll(keepCapacity: true)
            let t1 = buildTree(&shortLivedPool, i, depth)
            check += checkTree(&shortLivedPool, t1)
            shortLivedPool.removeAll(keepCapacity: true)
            let t2 = buildTree(&shortLivedPool, -i, depth)
            check += checkTree(&shortLivedPool, t2)
        }
        
        checksumOutput[depthIteration] = check
    }
    
    for depthIteration in (0..<checksumOutput.count) {
        let depth = minDepth + depthIteration * 2
        let iterations = 1 << (maxDepth - depth + minDepth)
        let check = checksumOutput[depthIteration]
        
        print("\(iterations*2)\t trees of depth \(depth)\t check: \(check)")
    }
    
    print("long lived tree of depth \(maxDepth)\t check: \(checkTree(&longLivedPool, longLivedTree))")
    
}



let n: Int = 20

var startTime = CFAbsoluteTimeGetCurrent()
type1(n)
var timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
print("Time elapsed: \(timeElapsed) s\n")


startTime = CFAbsoluteTimeGetCurrent()
type2(n)
timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
print("Time elapsed: \(timeElapsed) s\n")


startTime = CFAbsoluteTimeGetCurrent()
type3(n)
timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
print("Time elapsed: \(timeElapsed) s\n")

startTime = CFAbsoluteTimeGetCurrent()
type4(n)
timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
print("Time elapsed: \(timeElapsed) s\n")