Posted at

Swiftではどのようにソートを行っているか

More than 3 years have passed since last update.

Swiftのソートアルゴリズムを読んでみた。だけ。

(2016年7月8日お昼頃までのコミットのソースを読んでます)

Swiftのソートというと sort とか sortInPlace である。では具体的に何ソートをしているかというと、イントロソートである。

イントロソートの具体的な実装については

https://github.com/apple/swift/blob/5d1af107a33cb2459258524bf8a858d30e2906d3/stdlib/public/core/Sort.swift.gyb

を読むと分かる。

↑で実装されたイントロソートは

https://github.com/apple/swift/blob/6ef62f3c7357caa288bc97ba320b9c1a5dec51d8/stdlib/public/core/CollectionAlgorithms.swift.gyb

で呼び出されているっぽい。

以下、Sort.swift.gybについて。


そもそも.swift.gybについて

Swiftの実装の一部はSwiftそのものだが、ほとんど同じ実装になるものについては.swift.gybファイル中でPythonまじりで書かれている。

https://lists.swift.org/pipermail/swift-users/Week-of-Mon-20151207/000227.html


def cmp(a, b, p)

%{

def cmp(a, b, p):
if p:
return "isOrderedBefore(" + a + ", " + b + ")"
else:
return "(" + a + " < " + b + ")"

}%

// Generate two versions of sorting functions: one with an explicitly passed
// predicate 'isOrderedBefore' and the other for Comparable types that don't
// need such a predicate.

定番のcompare。 isOrderedBeforesortsortInPlace の引数で渡されるもの↓

Screen Shot 2016-07-08 at 2.07.42 PM.png


各種ソート

% preds = [True, False]

% for p in preds:

# 略

% end

により、 の位置にある


  • 挿入ソート


    • func _insertionSort<C>



  • クイックソート


    • func _partition<C>



  • イントロソート


    • func _introSort<C>

    • func _introSortImpl<C>



  • ヒープソート


    • func _siftDown<C>

    • func _heapify<C>

    • func _heapSort<C>



のそれぞれについて True 版と False 版の2つを作る。正確に言うと、 isOrderedBefore 有り版と無し版を両方生成する。たぶん。


func _insertionSort<C>

挿入ソート。

func _insertionSort<C>(

_ elements: inout C,
subRange range: Range<C.Index>
${", isOrderedBefore: inout (C.Iterator.Element, C.Iterator.Element) -> Bool" if p else ""}
) where
C : protocol<MutableCollection, BidirectionalCollection>
${"" if p else ", C.Iterator.Element : Comparable"} {

if !range.isEmpty {
let start = range.lowerBound

// Keep track of the end of the initial sequence of sorted
// elements.
var sortedEnd = start

// One element is trivially already-sorted, thus pre-increment
// Continue until the sorted elements cover the whole sequence
elements.formIndex(after: &sortedEnd)
while sortedEnd != range.upperBound {
// get the first unsorted element
let x: C.Iterator.Element = elements[sortedEnd]

// Look backwards for x's position in the sorted sequence,
// moving elements forward to make room.
var i = sortedEnd
repeat {
let predecessor: C.Iterator.Element = elements[elements.index(before: i)]

// if x doesn't belong before y, we've found its position
if !${cmp("x", "predecessor", p)} {
break
}

// Move y forward
elements[i] = predecessor
elements.formIndex(before: &i)
} while i != start

if i != sortedEnd {
// Plop x into position
elements[i] = x
}
elements.formIndex(after: &sortedEnd)
}
}
}


func _partition<C>

たぶんクイックソートのこと。

func _partition<C>(

_ elements: inout C,
subRange range: Range<C.Index>
${", isOrderedBefore: inout (C.Iterator.Element, C.Iterator.Element) -> Bool" if p else ""}
) -> C.Index
where
C : protocol<MutableCollection, RandomAccessCollection>
${"" if p else ", C.Iterator.Element : Comparable"} {

var lo = range.lowerBound
var hi = range.upperBound

if lo == hi {
return lo
}

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

// 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 !${cmp("elements[lo]", "pivot", p)} { break FindLo }
elements.formIndex(after: &lo)
}
break Loop
} while false

FindHi: repeat {
elements.formIndex(before: &hi)
while hi != lo {
if ${cmp("elements[hi]", "pivot", p)} { 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
}


introSort

イントロソート。再帰のレベルによって使用するソートを切り替える。そのため、イントロソートの実装は func _introSort<C>func _introSortImpl<C> の2つで行っている。

コメント中にあるpsファイルは考案者であるDavid R Musserさんの論文。


func _introSort<C>

public // @testable

func _introSort<C>(
_ elements: inout C,
subRange range: Range<C.Index>
${", isOrderedBefore: (C.Iterator.Element, C.Iterator.Element) -> Bool" if p else ""}
) where
C : protocol<MutableCollection, RandomAccessCollection>
${"" if p else ", C.Iterator.Element : Comparable"} {

% if p:
var isOrderedBeforeVar = isOrderedBefore
% end
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,
${"isOrderedBefore: &isOrderedBeforeVar," if p else ""}
depthLimit: depthLimit)
}


func _introSortImpl<C>


  • 基本はクイックソート。

  • 20未満の距離の範囲では挿入ソートを行う。

  • クイックソートをした分だけ再帰レベルの値が減っていく。レベル0になったらヒープソートで済ます。

func _introSortImpl<C>(

_ elements: inout C,
subRange range: Range<C.Index>
${", isOrderedBefore: inout (C.Iterator.Element, C.Iterator.Element) -> Bool" if p else ""},
depthLimit: Int
) where
C : protocol<MutableCollection, RandomAccessCollection>
${"" if p else ", C.Iterator.Element : Comparable"} {

// Insertion sort is better at handling smaller regions.
if elements.distance(from: range.lowerBound, to: range.upperBound) < 20 {
_insertionSort(
&elements,
subRange: range
${", isOrderedBefore: &isOrderedBefore" if p else ""})
return
}
if depthLimit == 0 {
_heapSort(
&elements,
subRange: range
${", isOrderedBefore: &isOrderedBefore" if p else ""})
return
}

// 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
${", isOrderedBefore: &isOrderedBefore" if p else ""})
_introSortImpl(
&elements,
subRange: range.lowerBound..<partIdx,
${"isOrderedBefore: &isOrderedBefore, " if p else ""}
depthLimit: depthLimit &- 1)
_introSortImpl(
&elements,
subRange: (elements.index(after: partIdx))..<range.upperBound,
${"isOrderedBefore: &isOrderedBefore, " if p else ""}
depthLimit: depthLimit &- 1)
}


heapSort

ヒープソート。ヒープソートなので、_siftDownと_heapifyがある。


func _siftDown<C>

siftDownとは、ヒープ構造からルートを削除する操作である。ってwikipedia先生が言ってた。 leftright を比較したのち、ルートである index と差し替えているのがわかる。

func _siftDown<C>(

_ elements: inout C,
index: C.Index,
subRange range: Range<C.Index>
${", isOrderedBefore: inout (C.Iterator.Element, C.Iterator.Element) -> Bool" if p else ""}
) where
C : protocol<MutableCollection, RandomAccessCollection>
${"" if p else ", C.Iterator.Element : Comparable"} {

let countToIndex = elements.distance(from: range.lowerBound, to: index)
let countFromIndex = elements.distance(from: index, to: range.upperBound)
// Check if left child is within bounds. If not, return, because there are
// no children of the given node in the heap.
if countToIndex + 1 >= countFromIndex {
return
}
let left = elements.index(index, offsetBy: countToIndex + 1)
var largest = index
if ${cmp("elements[largest]", "elements[left]", p)} {
largest = left
}
// Check if right child is also within bounds before trying to examine it.
if countToIndex + 2 < countFromIndex {
let right = elements.index(after: left)
if ${cmp("elements[largest]", "elements[right]", p)} {
largest = right
}
}
// If a child is bigger than the current node, swap them and continue sifting
// down.
if largest != index {
swap(&elements[index], &elements[largest])
_siftDown(
&elements,
index: largest,
subRange: range
${", isOrderedBefore: &isOrderedBefore" if p else ""})
}
}


func _heapify<C>

ヒープ構造を作る。コメントにある通り、2分木において、親ノードの値が子ノードの値より大きいようなやつ。

func _heapify<C>(

_ elements: inout C,
subRange range: Range<C.Index>
${", isOrderedBefore: inout (C.Iterator.Element, C.Iterator.Element) -> Bool" if p else ""}
) where
C : protocol<MutableCollection, RandomAccessCollection>
${"" if p else ", C.Iterator.Element : Comparable"} {
// Here we build a heap starting from the lowest nodes and moving to the root.
// On every step we sift down the current node to obey the max-heap property:
// parent >= max(leftChild, rightChild)
//
// We skip the rightmost half of the array, because these nodes don't have
// any children.
let root = range.lowerBound
var node = elements.index(
root,
offsetBy: elements.distance(
from: range.lowerBound, to: range.upperBound) / 2)

while node != root {
elements.formIndex(before: &node)
_siftDown(
&elements,
index: node,
subRange: range
${", isOrderedBefore: &isOrderedBefore" if p else ""})
}
}


func _heapSort<C>

_heapifyでヒープを作った後、_siftDownとswapを繰り返す。ヒープ構造が空になったら終わり。

func _heapSort<C>(

_ elements: inout C,
subRange range: Range<C.Index>
${", isOrderedBefore: inout (C.Iterator.Element, C.Iterator.Element) -> Bool" if p else ""}
) where
C : protocol<MutableCollection, RandomAccessCollection>
${"" if p else ", C.Iterator.Element : Comparable"} {
var hi = range.upperBound
let lo = range.lowerBound
_heapify(
&elements,
subRange: range
${", isOrderedBefore: &isOrderedBefore" if p else ""})
elements.formIndex(before: &hi)
while hi != lo {
swap(&elements[lo], &elements[hi])
_siftDown(
&elements,
index: lo,
subRange: lo..<hi
${", isOrderedBefore: &isOrderedBefore" if p else ""})
elements.formIndex(before: &hi)
}
}


func swap<T>

定番のswap。

対象の ab は互いに同じところを参照していないとか、 retain / release がないよう最適化しているとか。

/// Exchange the values of `a` and `b`.

///
/// - Precondition: `a` and `b` do not alias each other.
public func swap<T>(_ a: inout T, _ b: inout T) {
// Semantically equivalent to (a, b) = (b, a).
// Microoptimized to avoid retain/release traffic.
let p1 = Builtin.addressof(&a)
let p2 = Builtin.addressof(&b)
_debugPrecondition(
p1 != p2,
"swapping a location with itself is not supported")

// Take from P1.
let tmp: T = Builtin.take(p1)
// Transfer P2 into P1.
Builtin.initialize(Builtin.take(p2) as T, p1)
// Initialize P2.
Builtin.initialize(tmp, p2)
}


まとめ

3種のソートでイントロソートでした。