sorting - swift vs objective-c performance - Swift测试版性能:对数组进行排序

swift array sort algorithm / swift / performance / xcode6 / compiler-optimization

我在Swift Beta中实现了一个算法,发现性能非常差。深入研究后,我意识到其中一个瓶颈是排序数组这样简单的事情。相关部分在这里。

let n = 1000000
var x =  [Int](repeating: 0, count: n)
for i in 0..<n {
    x[i] = random()
}
// 从这里开始时钟
let y = sort(x)
// 这里停止时钟

在 Swift 中,如果我使用以下命令编译它需要6 秒

xcrun swift -O3 -sdk `xcrun --show-sdk-path --sdk macosx`

如果我使用以下命令编译它,则需要多达88 秒

xcrun swift -O0 -sdk `xcrun --show-sdk-path --sdk macosx`
let n = 10000000
print(n*n*n*n*n)
let x =  [Int](repeating: 10, count: n)
print(x[n])

编辑 2:我做了一些更多的基准测试,沿着非常简单的循环

for i in 0..<n {
    x[i] = x[i] ^ 12345678
}

编辑 3:在评论中,Ferruccio 要求提供公平的基准,因为它们不依赖于内置函数(例如排序)。我认为以下程序是一个很好的例子:

let n = 10000
var x = [Int](repeating: 1, count: n)
for i in 0..<n {
    for j in 0..<n {
        x[i] = x[j]
    }
}

Nilesh R Patel



Answer #1
func partition(inout list : [Int], low: Int, high : Int) -> Int {
    let pivot = list[high]
    var j = low
    var i = j - 1
    while j < high {
        if list[j] <= pivot{
            i += 1
            (list[i], list[j]) = (list[j], list[i])
        }
        j += 1
    }
    (list[i+1], list[high]) = (list[high], list[i+1])
    return i+1
}

func quikcSort(inout list : [Int] , low : Int , high : Int) {

    if low < high {
        let pIndex = partition(&list, low: low, high: high)
        quikcSort(&list, low: low, high: pIndex-1)
        quikcSort(&list, low: pIndex + 1, high: high)
    }
}

var list = [7,3,15,10,0,8,2,4]
quikcSort(&list, low: 0, high: list.count-1)

var list2 = [ 10, 0, 3, 9, 2, 14, 26, 27, 1, 5, 8, -1, 8 ]
quikcSort(&list2, low: 0, high: list2.count-1)

var list3 = [1,3,9,8,2,7,5]
quikcSort(&list3, low: 0, high: list3.count-1)