swift - 惰性集合导致 "unstable"过滤器和排序崩溃

Question

我刚刚看到一个线程，询问惰性集合。它们看起来像这样:

let array = Array(1...10).lazy

文档是这样描述惰性集合的:“一个集合包含与 Base 集合相同的元素，但在其上延迟实现了一些操作，例如 map 和 filter。”

这个想法是避免大量的中间集合。如果您有这样的代码:

设数组 = 1...10 .filter { $0 %2 == 0 } .sorted { $0 < $1 } .map { 字符串($0) }

然后代码中的每一步都会创建一个中间数组。对于大型阵列，这可能会占用大量内存。

不过，在使用惰性进行试验时，我发现如果处理惰性集合的一个或多个步骤在每次执行时都返回不同的结果，则可能会导致问题/崩溃。考虑这段代码:

@discardableResult func timeTest() -> Double {
    let start = Date()
    let array = 1...10
    let random = array
        .lazy
        .map { (value) -> UInt32 in
            let random = arc4random_uniform(100)
            print("Mapping", value, "to random val \(random)")
            return random
        }
        .filter {
            let result = $0 < 50
            print("  Testing \($0) < 50", result)
            return result
        }
        .map { (val: UInt32) -> NSNumber in
            print("    Mapping", val, "to NSNumber")
            return NSNumber(value: val)
        }
        .compactMap { (number) -> String? in
            print("      Mapping", number, "to String")
            return formatter.string(from: number)
        }
        .sorted { (lhv, rhv) -> Bool in //--> This is the line that crashes
            print("        Sorting strings")
            return (lhv.compare(rhv, options: .numeric) == .orderedAscending)
    }

    random.enumerated().forEach { print("String[\($0.0)] = \($0.1)") }

    let elapsed = Date().timeIntervalSince(start)

    print("Completed in ", String(format: "%0.3f", elapsed), " seconds")
    return elapsed
}

该代码将值从 1...100 映射到随机值，过滤掉小于 50 的值，对剩余值进行排序，将它们转换为字符串，然后打印它们。

这可能会产生这样的输出:

Mapping 1 to random val 47
  Testing 47 < 50 true
Mapping 1 to random val 57
    Mapping 57 to NSNumber
      Mapping 57 to String
Mapping 2 to random val 6
  Testing 6 < 50 true
Mapping 3 to random val 33
  Testing 33 < 50 true
Mapping 4 to random val 21
  Testing 21 < 50 true
Mapping 5 to random val 2
  Testing 2 < 50 true
Mapping 6 to random val 75
  Testing 75 < 50 false
Mapping 7 to random val 45
  Testing 45 < 50 true
Mapping 8 to random val 72
  Testing 72 < 50 false
Mapping 9 to random val 1
  Testing 1 < 50 true
Mapping 10 to random val 67
  Testing 67 < 50 false
Mapping 2 to random val 3
  Testing 3 < 50 true
Mapping 2 to random val 3
    Mapping 3 to NSNumber
      Mapping 3 to String
Mapping 3 to random val 6
  Testing 6 < 50 true
Mapping 3 to random val 86
    Mapping 86 to NSNumber
      Mapping 86 to String
Mapping 4 to random val 72
  Testing 72 < 50 false
Mapping 5 to random val 2
  Testing 2 < 50 true
Mapping 5 to random val 73
    Mapping 73 to NSNumber
      Mapping 73 to String
Mapping 6 to random val 31
  Testing 31 < 50 true
Mapping 6 to random val 53
    Mapping 53 to NSNumber
      Mapping 53 to String
Mapping 7 to random val 31
  Testing 31 < 50 true
Mapping 7 to random val 42
    Mapping 42 to NSNumber
      Mapping 42 to String
Mapping 8 to random val 41
  Testing 41 < 50 true
Mapping 8 to random val 23
    Mapping 23 to NSNumber
      Mapping 23 to String
Mapping 9 to random val 52
  Testing 52 < 50 false
Mapping 10 to random val 13
  Testing 13 < 50 true
Mapping 10 to random val 81
    Mapping 81 to NSNumber
      Mapping 81 to String
Mapping 1 to random val 84
  Testing 84 < 50 false
Mapping 2 to random val 1
  Testing 1 < 50 true
Mapping 2 to random val 82
    Mapping 82 to NSNumber
      Mapping 82 to String
Mapping 2 to random val 10
    Mapping 10 to NSNumber
      Mapping 10 to String
Mapping 3 to random val 58
  Testing 58 < 50 false
Mapping 4 to random val 98
  Testing 98 < 50 false
Mapping 5 to random val 12
  Testing 12 < 50 true
Mapping 5 to random val 9
    Mapping 9 to NSNumber
      Mapping 9 to String
Mapping 5 to random val 59
    Mapping 59 to NSNumber
      Mapping 59 to String
Mapping 6 to random val 49
  Testing 49 < 50 true
Mapping 6 to random val 29
    Mapping 29 to NSNumber
      Mapping 29 to String
Mapping 6 to random val 57
    Mapping 57 to NSNumber
      Mapping 57 to String
Mapping 7 to random val 20
  Testing 20 < 50 true
Mapping 7 to random val 87
    Mapping 87 to NSNumber
      Mapping 87 to String
Mapping 7 to random val 51
    Mapping 51 to NSNumber
      Mapping 51 to String
Mapping 8 to random val 2
  Testing 2 < 50 true
Mapping 8 to random val 93
    Mapping 93 to NSNumber
      Mapping 93 to String
Mapping 8 to random val 11
    Mapping 11 to NSNumber
      Mapping 11 to String
Mapping 9 to random val 18
  Testing 18 < 50 true
Mapping 9 to random val 47
    Mapping 47 to NSNumber
      Mapping 47 to String
Mapping 9 to random val 96
    Mapping 96 to NSNumber
      Mapping 96 to String
Mapping 10 to random val 10
  Testing 10 < 50 true
Mapping 10 to random val 44
    Mapping 44 to NSNumber
      Mapping 44 to String
Mapping 10 to random val 76
    Mapping 76 to NSNumber
      Mapping 76 to String

随后索引超出范围崩溃。

请注意，当一个值通过过滤器中的测试时，将再次调用原始映射到随机数。另请注意，有时重复映射到随机值会发生乱序。

我猜测每个高阶函数步骤都会重新评估前一步，并且由于随机数步骤每次都返回不同的值，然后过滤步骤每次都会返回不同数量的结果，所以它会感到困惑。

阅读本文的人是否对正在发生的事情有具体的了解？

Answer 1

此错误的原因是当 sorted(by:) 尝试执行时，数组的计数不同。 filter 更改结果数组的计数，这会干扰 sorted(by:) 的工作方式。

sorted(by:) 内部调用sort(by:):

@inlinable
public func sorted(
  by areInIncreasingOrder:
    (Element, Element) throws -> Bool
) rethrows -> [Element] {
  var result = ContiguousArray(self) 
  try result.sort(by: areInIncreasingOrder)
  return Array(result)
}

使用连续数组可以加快排序速度。

跳转到 definition 排序(按:):

@inlinable
public mutating func sort(
  by areInIncreasingOrder: (Element, Element) throws -> Bool
) rethrows {
  let didSortUnsafeBuffer = try _withUnsafeMutableBufferPointerIfSupported {
  buffer -> Void? in
    try buffer.sort(by: areInIncreasingOrder)
  }
  if didSortUnsafeBuffer == nil {
    try _introSort(within: startIndex..<endIndex, by: areInIncreasingOrder)
  }
}

我们可以看到它调用了内部函数_introSort(within:,by:)及其实际实现_introSortImpl(within:,by:,depthLimit:)。

与 .Net 和 C++ 一样，Swift 使用Introsort 算法 对数组元素进行排序。这是 Quicksort 和 heapSort 的混合体:它通过选择一个枢轴(3 的中位数)来划分数组。最后，当它到达深度 0 时，它切换到 heapSort。 sort 使用的 Introsort 算法的细节在 paper 中描述。 .

就地排序连续数组调用 this功能:

public mutating func replaceSubrange<C>(
  _ subrange: Range<Int>,
  with newElements: C
)

在内部调用 this :

internal mutating func _arrayOutOfPlaceReplace<C: Collection>(
  _ bounds: Range<Int>,
  with newValues: C,
  count insertCount: Int
)

这使得 this最终检查:

internal func _expectEnd<C: Collection>(of s: C, is i: C.Index)

如果数组的大小在排序时发生变化，则会引发错误并显示此消息

"invalid Collection: count differed in successive traversals"

与映射或过滤不同，对数组进行排序需要在排序时具有恒定大小和恒定值的数组。