swift – 为什么在懒惰地评估过滤器(_ :)的谓词被调用了这么多次

这里的第一个罪魁祸首是通过使用前缀(_ :)来切换延迟过滤器集合 – 在这种情况下,它返回LazyFilterBidirectionalCollection的BidirectionalSlice.

通常,Collection的切片需要存储基本集合,以及对切片“有效”的索引范围.因此,为了创建LazyFilterBidirectionalCollection的切片以查看前5个元素,存储的索引范围必须是startIndex ..< indexAfterTheFifthElement. 为了获得indexAfterTheFifthElement,LazyFilterBidirectionalCollection必须遍历基本集合(数字)才能找到符合谓词的第6个元素(可以看到the exact implementation of the indexing here).

因此,需要针对谓词检查来自上述示例的0 … 15范围内的所有元素,以便创建惰性过滤器集合的切片.

第二个罪魁祸首是Array的init(_ :),它接受与数组元素类型相同类型的元素序列. The implementation of this initialiser对序列调用_copyToContiguousArray(),对于大多数序列,forwards the call to this function：

internal func _copySequenceToContiguousArray<S : Sequence>
                                    (_ source: S) -> ContiguousArray<S.Iterator.Element> {

  let initialCapacity = source.underestimatedCount // <- problem here

  var builder =
    _UnsafePartiallyInitializedContiguousArrayBuffer<S.Iterator.Element>(
      initialCapacity: initialCapacity)

  var iterator = source.makeIterator()

  // FIXME(performance): use _copyContents(initializing:).
  // Add elements up to the initial capacity without checking for regrowth.
  for _ in 0..<initialCapacity {
    builder.addWithExistingCapacity(iterator.next()!)
  }

  // Add remaining elements,if any.
  while let element = iterator.next() {
    builder.add(element)
  }

  return builder.finish()
}

这里的问题被低估了.对于普通序列,这只是一个返回0的默认实现 – 但是,对于集合,它有一个默认实现,它获取集合的计数(我进入in more detail here).

Collection的计数(BidirectionalSlice将在这里使用)的默认实现很简单：

public var count: IndexDistance {
    return distance(from: startIndex,to: endIndex)
}

对于我们的切片,它将遍历indexAfterTheFifthElement的索引,从而再次重新评估0 … 15范围内的元素.

最后,创建切片的迭代器,并迭代,将序列中的每个元素添加到新数组的缓冲区中.对于BidirectionalSlice,这将使用IndexingIterator,它只是通过推进索引并输出每个索引的元素来工作.

这个遍历索引的原因是没有重新评估结果的第一个元素的元素(在问题的例子中注意,0被评估的时间减去一次)是因为它不能直接访问LazyFilterBidirectionalCollection的startIndex,即has to evaluate all elements up to the first element in the result.相反,迭代器可以从切片本身的起始索引开始工作.

解决方案

简单的解决方案是避免切片延迟过滤器集合以获取其前缀,而是懒惰地应用前缀.

实际上有两个前缀(_ :)的实现.一个是provided by Collection,并返回SubSequence(对于大多数标准库集合,它是某种形式的切片).

另一个是provided by Sequence,它返回一个AnySequence – 它在引擎盖下使用_PrefixSequence的基本序列,它只需要一个迭代器并允许迭代它直到迭代了给定数量的元素 – 然后只是停止返回元素.

对于惰性集合,前缀(_ :)的这种实现很好,因为它不需要任何索引 – 它只是懒惰地应用前缀.

因此,如果你说：

let result : AnySequence = numbers.lazy
    .filter {
        // gets called 1x per element :)
        print("Calling filter for: ($0)")
        return $0 % 3 == 0
    }
    .prefix(5)

当传递给Array的初始化器时,数字的元素(直到第5个匹配)将仅由filter(_ :)的谓词计算一次,因为您强制Swift使用Sequence的前缀(_ :)的默认实现.

防止给定延迟过滤器集合上的所有索引操作的简单方法是简单地使用延迟过滤器序列 – 这可以通过在AnySequence中包装您希望执行延迟操作的集合来完成：

let numbers = Array(0 ..< 50)

let result = AnySequence(numbers).lazy
    .filter {
        // gets called 1x per element :)
        print("Calling filter for: ($0)")
        return $0 % 3 == 0
    }
    .dropFirst(5) // neither of these will do indexing,.prefix(5)    // but instead return a lazily evaluated AnySequence.


print(Array(result)) // [15,18,21,24,27]

但请注意,对于双向集合,这可能会对集合末尾的操作产生负面影响 – 因为整个序列必须通过迭代才能到达终点.

对于后缀(_ :)和dropLast(_ :)这样的操作,在序列上使用惰性集合(至少对于小输入)可能更有效,因为它们可以简单地从集合的末尾开始索引. .

虽然与所有与性能相关的问题一样,您应该首先检查这是否是一个问题,然后再运行您自己的测试,看看哪种方法更适合您的实现.

结论(TL; DR)

所以,经过这一切 – 在这里要学习的教训是,你应该警惕切片延迟过滤器集合可以重新评估基本集合的每个元素直到切片可以“查看”的结束索引这一事实.

通常,更倾向于将延迟过滤器集合视为序列而不是索引,因此意味着延迟操作无法评估任何元素(这样做会破坏性地迭代它们),直到急切的操作发生.

但是,您应该警惕您可能会牺牲能够从最终索引集合的事实,这对后缀(_ :)等操作很重要.

最后,值得注意的是,这不符合如LazyMapCollection懒惰的意见一个问题,因为它们的元素不依赖于以前的元素的“结果” – 因此,他们可以在固定的时间索引,如果他们的基地集合是一个RandomAccessCollection .