sorting - Swift Beta 성능 : 배열 정렬

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)