嵌套函数使Swift编译器崩溃

Question

我写了一个递归mergeSort函数：

func mergeSort<T: Comparable>(inout array: [T]) {
    if array.count <= 1 {
        return
    }
    var leftSlice = [T](array[0..<array.count / 2])
    var rightSlice = [T](array[array.count / 2...array.endIndex - 1])
    mergeSort(&leftSlice)
    mergeSort(&rightSlice)
    array = merge(leftSlice, rightSlice)
}
func merge<T: Comparable>(var left: [T], var right: [T]) -> [T] {
    var mergedValues = [T]()
    while !left.isEmpty && !right.isEmpty {
        mergedValues.append(left.first! < right.first! ? left.removeAtIndex(0) : right.removeAtIndex(0))
    }
    if !left.isEmpty {
        mergedValues += left
    } else if !right.isEmpty {
        mergedValues += right
    }
    return mergedValues
}

现在，由于merge()只应该由mergeSort()使用，我将其放置在mergeSort()内部，因此使merge()成为嵌套函数：

func mergeSort<T: Comparable>(inout array: [T]) {
    func merge<T: Comparable>(var left: [T], var right: [T]) -> [T] {
        var mergedValues = [T]()
        while !left.isEmpty && !right.isEmpty {
            mergedValues.append(left.first! < right.first! ? left.removeAtIndex(0) : right.removeAtIndex(0))
        }
        if !left.isEmpty {
            mergedValues += left
        } else if !right.isEmpty {
            mergedValues += right
        }
        return mergedValues
    }
    if array.count <= 1 {
        return
    }
    var leftSlice = [T](array[0..<array.count / 2])
    var rightSlice = [T](array[array.count / 2...array.endIndex - 1])
    mergeSort(&leftSlice)
    mergeSort(&rightSlice)
    array = merge(leftSlice, rightSlice)
}

现在第一个版本运行良好，但第二个版本不行
怎么可能呢？

Answer 1

看起来您在编译器中发现了一个与嵌套泛型函数有关的错误。以下是一个减少1.2编译器崩溃的方法：

func f<T>(t: T) {
    func g<U>(u: U) { }
}

但在这种情况下，实际上并不需要merge的通用版本。它的通用参数与外部函数相同，因此只需使用：

func mergeSort<T: Comparable>(inout array: [T]) {
    // no generic placeholder needed, T is the T for mergeSort
    func merge(var left: [T], var right: [T]) -> [T] {
      // etc.
    }
}

这似乎很好用。

然而，也值得指出的是，在merge函数中，您在循环中调用removeAtIndex，这是一个O（n）函数。这意味着您的合并排序将不会具有所希望的复杂性。

这里有一个可供选择的版本：

func mergeSort<T: Comparable>(inout array: [T], range: Range<Int>? = nil) {
    func merge(left: Range<Int>, right: Range<Int>) -> [T] {    
        var tmp: [T] = []
        tmp.reserveCapacity(count(left) + count(right))
        var l = left.startIndex, r = right.startIndex
        while l != left.endIndex && r != right.endIndex {
            if array[l] < array[r] {
                tmp.append(array[l++])
            }
            else {
                tmp.append(array[r++])
            }
        }
        // where left or right may be empty, this is a no-op
        tmp += source[l..<left.endIndex]
        tmp += source[r..<right.endIndex]
        return tmp
    }
    // this allows the original caller to omit the range,
    // the default being the full array
    let r = range ?? indices(array)
    if count(r) > 1 {
        let mid = r.startIndex.advancedBy(r.startIndex.distanceTo(r.endIndex)/2)
        let left = r.startIndex..<mid
        let right = mid..<r.endIndex
        mergeSort(&array, range: left)
        mergeSort(&array, range: right)
        let merged = merge(left, right)
        array.replaceRange(r, with: merged)
    }
}

我还想说的是，由于merge本身可能是一个通用的有用函数，因此您还可以将它独立起来，而不是嵌套它（类似地，在实现快速排序时，partition）。嵌套并不能为您带来任何好处（除了我上面使用的从嵌套中引用外部参数的技巧之外，这可能是一种糟糕的做法，我这样做主要是为了向您展示：）

Answer 2

您不需要使merge成为泛型函数。已经为mergeSort定义了通用T，因此您只需在内部函数中将[T]设置为参数

func merge(var left: [T], var right: [T]) -> [T] {
    var mergedValues = [T]()
    ...
}