Swift Source Code Analysis - Sort

Posted on | Edited on | Comments:

Swift源码分析-Sort排序

Swift源码分析 - Sort

当我们在Swift中使用排序的时候,我们通常会这样使用:

1
2
let array = [1, 3, 5, 7, 9, 0, 8]
array.sort(>)

或者这样使用:

1
2
var array = [1, 3, 5, 7, 9, 0, 8]
array.sorted(>)

速度非常的快,比快速排序,插入排序,堆排序等,都快很多.

当我看到Swift的源码的时候才知道为什么排序速度这么快.

IntroSort(内省算法)

将sort.swift.gyb文件转换成sort.swift文件

源码中很多文件不是用Swift写的,而是用Python写的,这个时候我们就要用工具进行转换了,转换的方法很简单.(源码中已经自带转换工具)，当然,如果你已经了解Python,那么你直接去源码路径查看就可以。

转换方法：

/swift/stdlib/public/core/Sort.swift.gyb

终端切换到工具目录下：

cd /swift/utils

./gyb --line-directive '' -o sort.swift sort.swift.gyb

更多信息: Blog or SwiftGG.

Analysis

我看到了很熟悉的排序算法:

1
2
3
func _heapSort
func _insertionSort
func _partition

应该是堆排序,插入排序,快速排序.

  • 堆排序的优点:在任何情况下时间复杂度都是一样,稳定性高
  • 插入排序优点:在数量很少的情况下可以很快的完成
  • 快速排序优点:在数量很大的时候速度是最快的,但是不稳定

这样可以推断出IntroSort算法其实是三者排序算法的综合应用.

但是这个文件中并没有sort函数,根据推断,我们在使用函数的时候都是在一个Collection中,也就是数组中,于是在源码中成功找到文件:

CollectionAlgorithms.swift.gyb

sort - CollectionAlgorithms.swift

而下面这个两个扩展中的sort函数, 都是创建新数组,然后修改返回,所以不会修改原数组,也就是我们经常使用的函数(默认MutableCollection和Sequence都实现了一样的方法):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
extension Sequence where Self.Iterator.Element : Comparable {
  public func sorted() -> [Iterator.Element] {
    var result = ContiguousArray(self)
    result.sort()
    return Array(result)
  }
}

extension Sequence {
  public func sorted(
    by areInIncreasingOrder:
      (Iterator.Element, Iterator.Element) -> Bool
  ) -> [Iterator.Element] {
    var result = ContiguousArray(self)
    result.sort(by: areInIncreasingOrder)
    return Array(result)
  }
}

Note: 由于sorted默认是从小到大排序，所以需要在第一个扩展中加上限定，使得元素可比较，但是第二个采用自定义比较方法，所以不需要加上扩展条件

让我们回到核心代码上:

第一个:

1
2
3
4
5
6
7
8
9
10
11
12
13
public mutating func sort() {
   let didSortUnsafeBuffer: Void? =
     _withUnsafeMutableBufferPointerIfSupported {
     (baseAddress, count) -> Void in
     var bufferPointer =
       UnsafeMutableBufferPointer(start: baseAddress, count: count)
     bufferPointer.sort()
     return ()
   }
   if didSortUnsafeBuffer == nil {
     _introSort(&self, subRange: startIndex..<endIndex)
   }
 }

第二个:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public mutating func sort(
   by areInIncreasingOrder:
     (Iterator.Element, Iterator.Element) -> Bool
 ) {
   typealias EscapingBinaryPredicate =
     (Iterator.Element, Iterator.Element) -> Bool
   let escapableIsOrderedBefore =
     unsafeBitCast(areInIncreasingOrder, to: EscapingBinaryPredicate.self)

   let didSortUnsafeBuffer: Void? =
     _withUnsafeMutableBufferPointerIfSupported {
     (baseAddress, count) -> Void in
     var bufferPointer =
       UnsafeMutableBufferPointer(start: baseAddress, count: count)
     bufferPointer.sort(by: escapableIsOrderedBefore)
     return ()
   }
   if didSortUnsafeBuffer == nil {
     _introSort(
       &self,
       subRange: startIndex..<endIndex,
       by: escapableIsOrderedBefore)
   }
 }

分析:

  • 相同点:两个函数前面都加了一个关键字mutating表示是需要修改内容的因为这个扩展的不是Collection,而是MutableCollection.

  • 不同点:

    1. 第一个函数也就是不给定参数,默认排序为从小到大.
    2. 给定参数,按参数(其实就是闭包)进行排序.

_introSort(&self, subRange: startIndex..<endIndex)开始调用introSort算法了

那这个闭包是干嘛的?

1
(Iterator.Element, Iterator.Element) -> Bool

得到两个泛型的值,返回一个Bool值?很熟悉?在Swift中,<号和>号等都是函数,都是通过判断两个数,之后返回Bool类型,这就是为什么我们可以使用<号或者>号来进行简写sort函数了,这个在之后会详解

_introSort - Sort.swift

在源码中有这样一个函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
	public // @testable
func _introSort<C>(
  _ elements: inout C,
  subRange range: Range<C.Index>
  
) where
  C : MutableCollection & RandomAccessCollection
  , C.Iterator.Element : Comparable {

  let count =
    elements.distance(from: range.lowerBound, to: range.upperBound).toIntMax()
  if count < 2 {
    return
  }
  // Set max recursion depth to 2*floor(log(N)), as suggested in the introsort
  // paper: http://www.cs.rpi.edu/~musser/gp/introsort.ps
  let depthLimit = 2 * _floorLog2(Int64(count))
  _introSortImpl(
    &elements,
    subRange: range,
    
    depthLimit: depthLimit)
}

泛型符号是C,支持MutableCollection, RandomAccessCollection协议(A collection that supports efficient random-access index traversal.Random-access collections can measure move indices any distance and can measure the distance between indices in O(1) time)

let depthLimit = 2 * _floorLog2(Int64(count))一个计算深度限制的方法,具体的意思在下面会说

下面是解释:

大致意思是这样的:快速排序很快,但是最坏的情况下时间复杂度却很不好,这取决于partition的位置,当partition的位置小于限制深度的时候就采用堆排序来维持一个Nlog(N)的时间复杂度.

之后将参数传递给:

1
2
3
4
5
6
7
8
func _introSortImpl<C>(
  _ elements: inout C,
  subRange range: Range<C.Index>
  ,
  depthLimit: Int
)where
  C : MutableCollection & RandomAccessCollection
  , C.Iterator.Element : Comparable

这才是整个算法最核心的部分,也就是算法选择的部分.自动选择最优算法来进行排序,根据不同的场景来切换排序算法,达到最优的效果.

1
2
3
4
5
6
7
8
// Insertion sort is better at handling smaller regions.
  if elements.distance(from: range.lowerBound, to: range.upperBound) < 20 {
    _insertionSort(
      &elements,
      subRange: range
      )
    return
  }

从这句话我们可以看到限制深度保持在20,这正是插入排序的优点.

1
2
3
4
5
6
7
if depthLimit == 0 {
   _heapSort(
     &elements,
     subRange: range
     )
   return
 }

当深度等于0的时候采用堆排序.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Partition and sort.
 // We don't check the depthLimit variable for underflow because this variable
 // is always greater than zero (see check above).
 let partIdx: C.Index = _partition(
   &elements,
   subRange: range
   )
 _introSortImpl(
   &elements,
   subRange: range.lowerBound..<partIdx,
   
   depthLimit: depthLimit &- 1)
 _introSortImpl(
   &elements,
   subRange: (elements.index(after: partIdx))..<range.upperBound,
   
   depthLimit: depthLimit &- 1)

现在就是开始快速排序了,并且每趟快速排序完成之后都会重新将两个子序列进行_introSort,这样就达到了不同情况选择不同的排序算法:

1
2
3
4
5
6
7
8
func _partition<C>(
  _ elements: inout C,
  subRange range: Range<C.Index>
  
) -> C.Index
  where
  C : MutableCollection & RandomAccessCollection
  , C.Iterator.Element : Comparable

看看如何将一个数组分成两半的.

1
2
// The first element is the pivot.
 let pivot = elements[range.lowerBound]

这是偷懒么?优化不够啊!就不使用三点取中?,直接用第一个元素作为中轴?这也许有原因的:要么偷懒.要么就是没必要(多一个判断就多一次消耗时间,我认为这没有必要)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
  // Loop invariants:
  // * lo < hi
  // * elements[i] < pivot, for i in range.lowerBound+1..lo
  // * pivot <= elements[i] for i in hi..range.upperBound

Loop: while true {
  FindLo: repeat {
      elements.formIndex(after: &lo)
      while lo != hi {
        if !(elements[lo] < pivot) { break FindLo }
        elements.formIndex(after: &lo)
      }
      break Loop
    } while false

  FindHi: repeat {
      elements.formIndex(before: &hi)
      while hi != lo {
        if (elements[hi] < pivot) { break FindHi }
        elements.formIndex(before: &hi)
      }
      break Loop
    } while false

    swap(&elements[lo], &elements[hi])
  }

  elements.formIndex(before: &lo)
  if lo != range.lowerBound {
    // swap the pivot into place
    swap(&elements[lo], &elements[range.lowerBound])
  }

  return lo
}

正常的快速排序.

默认的排序说完了,该说说这个了:

1
(Iterator.Element, Iterator.Element) -> Bool

这个闭包的执行是在快速排序,插入排序,堆排序中进行使用的,目的就是判断是升序,还是降序的.

我们就拿快速排序讲解吧(其实很简单):

1
if !areInIncreasingOrder(elements[lo], pivot) { break FindLo }

在之前的判断中是这样的:

1
if !(elements[lo] < pivot) { break FindLo }

直接就是小于,而这个闭包其实也就是判断两个数大小的然后返回Bool值,这样就可以控制升序降序了.

补充:

在Swift源码中我发现这样几句话:

The sorting algorithm is not stable. A nonstable sort may change the relative order of elements for whichareInIncreasingOrderdoes not establish an order.(排序算法是一个不稳定的算法,不稳定是相对于提供的areInIncreasingOrder闭包)

我们在使用sort函数的时候都是sort(<) 或者 sort(>) ,而不是用 sort(<=) 和 sort(>=)
原因:

可以看出结果都是一样,但是运行的效率是不一样的.

同样的数组,同样的结果,却不同的执行次数.所以在写代码的时候要注意了,千万不要加=号

关于限制深度的问题

(在2000年6月，SGI的C++标准模板库的stl_algo.h中的不稳定排序算法采用了Musser的introsort算法。在此实现中，切换到插入排序的数据量阀值为16个)

1
2
3
4
5
6
7
8
// Insertion sort is better at handling smaller regions.
 if elements.distance(from: range.lowerBound, to: range.upperBound) < 20 {
    _insertionSort(
      &elements,
      subRange: range
      )
    return
  }

说明在数量小于20的情况下采用插入排序,所以在Swift中阀值应该是20

1
2
3
4
5
6
7
if depthLimit == 0 {
    _heapSort(
      &elements,
      subRange: range
      )
    return
  }

在深度限制为0的时候采用堆排序,说明平衡已经被破坏,数据依旧很大,但是快速排序的效率低下,改用堆排序来维持O(logN)的时间复杂度