swift资源 - Swift性能:对数组进行排序

tl;通过使用默认版本优化级别[-O]的此基准测试，Swift现在与C一样快。

这是Swift中的一个就地快速排序：

func quicksort_swift(inout a:CInt[], start:Int, end:Int) {
    if (end - start < 2){
        return
    }
    var p = a[start + (end - start)/2]
    var l = start
    var r = end - 1
    while (l <= r){
        if (a[l] < p){
            l += 1
            continue
        }
        if (a[r] > p){
            r -= 1
            continue
        }
        var t = a[l]
        a[l] = a[r]
        a[r] = t
        l += 1
        r -= 1
    }
    quicksort_swift(&a, start, r + 1)
    quicksort_swift(&a, r + 1, end)
}

和C中一样：

void quicksort_c(int *a, int n) {
    if (n < 2)
        return;
    int p = a[n / 2];
    int *l = a;
    int *r = a + n - 1;
    while (l <= r) {
        if (*l < p) {
            l++;
            continue;
        }
        if (*r > p) {
            r--;
            continue;
        }
        int t = *l;
        *l++ = *r;
        *r-- = t;
    }
    quicksort_c(a, r - a + 1);
    quicksort_c(l, a + n - l);
}

两者都有效：

var a_swift:CInt[] = [0,5,2,8,1234,-1,2]
var a_c:CInt[] = [0,5,2,8,1234,-1,2]

quicksort_swift(&a_swift, 0, a_swift.count)
quicksort_c(&a_c, CInt(a_c.count))

// [-1, 0, 2, 2, 5, 8, 1234]
// [-1, 0, 2, 2, 5, 8, 1234]

两者都在写入的同一程序中调用。

var x_swift = CInt[](count: n, repeatedValue: 0)
var x_c = CInt[](count: n, repeatedValue: 0)
for var i = 0; i < n; ++i {
    x_swift[i] = CInt(random())
    x_c[i] = CInt(random())
}

let swift_start:UInt64 = mach_absolute_time();
quicksort_swift(&x_swift, 0, x_swift.count)
let swift_stop:UInt64 = mach_absolute_time();

let c_start:UInt64 = mach_absolute_time();
quicksort_c(&x_c, CInt(x_c.count))
let c_stop:UInt64 = mach_absolute_time();

这将绝对时间转换为秒：

static const uint64_t NANOS_PER_USEC = 1000ULL;
static const uint64_t NANOS_PER_MSEC = 1000ULL * NANOS_PER_USEC;
static const uint64_t NANOS_PER_SEC = 1000ULL * NANOS_PER_MSEC;

mach_timebase_info_data_t timebase_info;

uint64_t abs_to_nanos(uint64_t abs) {
    if ( timebase_info.denom == 0 ) {
        (void)mach_timebase_info(&timebase_info);
    }
    return abs * timebase_info.numer  / timebase_info.denom;
}

double abs_to_seconds(uint64_t abs) {
    return abs_to_nanos(abs) / (double)NANOS_PER_SEC;
}

以下是编译器优化级别的总结：

[-Onone] no optimizations, the default for debug.
[-O]     perform optimizations, the default for release.
[-Ofast] perform optimizations and disable runtime overflow checks and runtime type checks.

n = 10_000时用[-Onone] 表示的秒数 ：

Swift:            0.895296452
C:                0.001223848

这里是Swift的内置排序（） n = 10_000 ：

Swift_builtin:    0.77865783

这里是n = 10_000的 [-O] ：

Swift:            0.045478346
C:                0.000784666
Swift_builtin:    0.032513488

正如你所看到的，斯威夫特的表现提高了20倍。

根据mweathers的回答 ，设置[-Ofast]会产生真正的差异，导致n = 10_000的这些时间：

Swift:            0.000706745
C:                0.000742374
Swift_builtin:    0.000603576

而对于n = 1_000_000 ：

Swift:            0.107111846
C:                0.114957179
Swift_sort:       0.092688548

为了比较，这与n = 1_000_000的 [-Onone] ：

Swift:            142.659763258
C:                0.162065333
Swift_sort:       114.095478272

因此，在这个基准测试阶段，没有优化的Swift比C慢1000倍，在这个阶段它的发展。 另一方面，如果两个编译器都设置为[-Ofast]，Swift的实际执行效果至少与C相比稍好一些。

有人指出[-Ofast]会改变语言的语义，使其可能不安全。 这就是Apple在Xcode 5.0发行说明中所说的：

LLVM中提供的新优化级别-Ofast可实现积极的优化。 -Ofast放宽了一些保守的限制，主要用于浮点运算，这对大多数代码都是安全的。 它可以从编译器中获得显着的高性能优势。

他们都提倡它。 无论这是否明智，我都不能说，但从我可以告诉的是，如果您没有进行高精度浮点运算，并且您确信没有整数或数组溢出可能在你的程序中。 如果您确实需要高性能和溢出检查/精确算术，那么现在就选择另一种语言。

BETA 3更新：

n = 10_000与[-O] ：

Swift:            0.019697268
C:                0.000718064
Swift_sort:       0.002094721

总的来说Swift速度更快，看起来Swift的内置排序已经发生了很大的变化。

最终更新：

[-Onone] ：

Swift:   0.678056695
C:       0.000973914

[-O] ：

Swift:   0.001158492
C:       0.001192406

[-Ounchecked] ：

Swift:   0.000827764
C:       0.001078914

从Xcode 7开始，您可以打开Fast, Whole Module Optimization 。 这应该立即提高你的表现。

其他人提到的主要问题是， -O3在Swift中根本就没有做任何事情（所以从来没有），所以编译时它实际上是非优化的（ -Onone ）。

选项名称随时间而改变，所以其他一些答案对于构建选项具有过时的标志。 正确的当前选项（Swift 2.2）是：

-Onone // Debug - slow
-O     // Optimised
-O -whole-module-optimization //Optimised across files

整个模块优化的编译速度较慢，但​​可以跨模块内的文件进行优化，即在每个框架内和实际应用程序代码内但不在它们之间。 你应该使用它来表现任何关键性能）

您还可以停用安全检查，以获得更快的速度，但所有断言和前提条件不仅仅是禁用，而是基于它们是正确的进行了优化。 如果你打了一个断言，这意味着你陷入了未定义的行为。 只有在确定速度提升对您有价值时（通过测试），才能非常谨慎地使用。 如果您确实发现它对于某些代码很有价值，我建议将该代码分离到单独的框架中，并且仅对该模块禁用安全检查。

来自The Swift Programming Language ：

Sort函数Swift的标准库提供了一个称为sort的函数，它根据您提供的排序闭包的输出对已知类型的值的数组进行排序。 一旦完成排序过程，排序函数将返回一个与旧排序相同类型和大小的新数组，其元素按正确的排序顺序排列。

sort函数有两个声明。

默认声明允许您指定比较闭包：

func sort<T>(array: T[], pred: (T, T) -> Bool) -> T[]

而第二个声明只需要一个参数（数组），并且“硬编码为使用小于比较器”。

func sort<T : Comparable>(array: T[]) -> T[]

Example:
sort( _arrayToSort_ ) { $0 > $1 }

我在一个操场上测试了代码的修改版本，添加了闭包，所以我可以更密切地监视函数，并且我发现在n设置为1000时，闭包被称为约11,000次。

let n = 1000
let x = Int[](count: n, repeatedValue: 0)
for i in 0..n {
    x[i] = random()
}
let y = sort(x) { $0 > $1 }

这不是一个有效的函数，我会建议使用更好的排序功能实现。

编辑：

我看了一下Quicksort维基百科页面，并为它写了一个Swift实现。 这里是我使用的完整程序（在游乐场）

import Foundation

func quickSort(inout array: Int[], begin: Int, end: Int) {
    if (begin < end) {
        let p = partition(&array, begin, end)
        quickSort(&array, begin, p - 1)
        quickSort(&array, p + 1, end)
    }
}

func partition(inout array: Int[], left: Int, right: Int) -> Int {
    let numElements = right - left + 1
    let pivotIndex = left + numElements / 2
    let pivotValue = array[pivotIndex]
    swap(&array[pivotIndex], &array[right])
    var storeIndex = left
    for i in left..right {
        let a = 1 // <- Used to see how many comparisons are made
        if array[i] <= pivotValue {
            swap(&array[i], &array[storeIndex])
            storeIndex++
        }
    }
    swap(&array[storeIndex], &array[right]) // Move pivot to its final place
    return storeIndex
}

let n = 1000
var x = Int[](count: n, repeatedValue: 0)
for i in 0..n {
    x[i] = Int(arc4random())
}

quickSort(&x, 0, x.count - 1) // <- Does the sorting

for i in 0..n {
    x[i] // <- Used by the playground to display the results
}

使用n = 1000，我发现

1. quickSort（）被调用约650次，
2. 进行了大约6000次掉期交易，
3. 并有大约10000个比较

看起来内置的排序方法是（或接近）快速排序，而且非常慢...

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) 

这是我的关于快速排序的博客 - Github示例快速排序

您可以在分区列表中查看Lomuto的分区算法。 写在Swift中