29.合并排序挑战¶

挑战1：加快追加的速度¶

考虑一下下面的代码：

let size = 1024
var values: [Int] = []
// 1
for i in 0 ..< size {
  values.append(i)
}

这段代码将导致近十次的重新分配。在//1处添加一条语句，将其减少到一次分配。

Note

reserveCapacity是你的朋友。;］

挑战 2: 合并两个序列¶

编写一个函数，接收两个排序的序列并将其合并为一个序列。下面是开始时的函数签名：

func merge<T: Sequence>(first: T, second: T)
  -> AnySequence<T.Element> where T.Element: Comparable {}

AnySequence是一个类型擦除器，抽象出具体的实现细节。

解决方案¶

挑战1的解决方案¶

let size = 1024
var values: [Int] = []
values.reserveCapacity(size)
for i in 0 ..< size {
  values.append(i)
}

使用reserveCapacity是加快追加速度的好方法。

挑战2的解决方案¶

这个挑战的棘手之处在于Sequence的能力有限。这种算法的传统实现依赖于Collection类型的能力，如数组，以保持对索引的跟踪。

由于Sequence类型没有索引的概念，你将使用其迭代器。

打开启动项目，开始。将其内容更新为以下内容：

func merge<T: Sequence>(first: T, second: T)
  -> AnySequence<T.Element> where T.Element: Comparable {

  // 1
  var result: [T.Element] = []

  // 2
  var firstIterator = first.makeIterator()
  var secondIterator = second.makeIterator()

  // 3
  var firstNextValue = firstIterator.next()
  var secondNextValue = secondIterator.next()

  // ...
}

设置该算法包括以下步骤：

创建一个新的容器来存储合并后的序列。
抓住第一个和第二个序列的迭代器。迭代器通过next方法依次分配序列的值。
创建两个变量，初始化为第一个和第二个迭代器的第一个值。next返回序列的一个可选的元素，nil返回值表明迭代器已经分配了序列中的所有元素。

使用迭代器，你将通过比较第一个和第二个下一个值来决定哪个元素应该被附加到result数组中。在merge函数的末尾写上以下内容：

while let first = firstNextValue,
      let second = secondNextValue {

  if first < second { // 1
    result.append(first)
    firstNextValue = firstIterator.next()
  } else if second < first { // 2
    result.append(second)
    secondNextValue = secondIterator.next()
  } else { // 3
    result.append(first)
    result.append(second)
    firstNextValue = firstIterator.next()
    secondNextValue = secondIterator.next()
  }
}

这段代码是合并算法的主要组成部分。使用while let，你检查是否有必要比较哪些值要插入result数组中。

如果第一个值小于第二个值，你将在result中追加第一个值，并通过在第一个迭代器上调用next播种下一个要比较的值。
如果第二个值小于第一个值，你将做相反的事情。你通过在第二个迭代器上调用next来为下一个要比较的值播种。
你同时追加first和second的值，如果它们相等，你就给两个下一个值做种子。

这个过程将继续下去，直到其中一个迭代器用完了要分配的元素。在这种情况下，这意味着剩下元素的迭代器的元素等于或大于result中的当前值。

要添加剩下的那些值，在merge函数的末尾写上以下内容：

while let first = firstNextValue {
  result.append(first)
  firstNextValue = firstIterator.next()
}

while let second = secondNextValue {
  result.append(second)
  secondNextValue = secondIterator.next()
}

return AnySequence<T.Element>(result)

通过写下以下内容，确认这个功能是有效的：

var array1 = [1, 2, 3, 4, 5, 6, 7, 8]
var array2 = [1, 3, 4, 5, 5, 6, 7, 7]

for element in merge(first: array1, second: array2) {
  print(element)
}

你应该看到以下控制台输出：