嵌套函數崩潰雨燕編譯

我寫了一個遞歸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()一個nested function：

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) 
}

現在first版本正常工作，但second一個沒有。
這怎麼可能？

來源

2015-02-23 Marcus Rossel

看起來你已經發現，在涉及到嵌套泛型函數編譯器的錯誤。這裏有一個減少也崩潰了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功能，你調用一個循環中，這是一個O（n）的功能removeAtIndex。這意味着你的合併排序不會有希望的複雜性。

這裏有一個替代版本考慮：

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）。嵌套不會給你買任何東西（除了上面引用外部參數的技巧之外，這可能是一個糟糕的做法，無論如何，我主要是這樣做，以表明你可以:)

來源

2015-02-23 18:20:02

我也注意到了這一點。如果我引入嵌套泛型，則操作系統甚至不會運行，並嘗試使用嵌套泛型編譯產生分段錯誤。 – kellanburket 2015-02-23 18:29:34

是的，這是一個編譯器崩潰，而不是一個運行時錯誤（我編輯了問題標題） – 2015-02-23 18:32:37

好的，我有幾個問題：（1）你怎麼知道'removeAtIndex'需要* O（n）*時間？ || （2）是否有可能在不初始化靜態數組的情況下創建靜態數組，通過在'let'定義的數組上使用'reserveCapacity'來以某種方式進行初始化？ || （3）你爲什麼對Swift有太多瞭解？ – 2015-02-23 21:20:02

您不需要使merge成爲通用功能。通用T已經爲mergeSort定義，所以你只需設置[T]作爲內部函數將參數：

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

來源

2015-02-23 18:07:41 kellanburket

嵌套函數崩潰雨燕編譯

回答

相關問題