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

Question

我看到一个答案到了这个问题,它在它的第一个版本,也有类似的代码如下:

let numbers = Array(0 ..< 50)

let result = numbers.lazy
    .filter {
        // gets called 2-3x per element in the range (0...15)!
        print("Calling filter for: \($0)")
        return $0 % 3 == 0
    }
    .prefix(5)

print(Array(result)) // [0, 3, 6, 9, 12]

通过使用惰性过滤器集合,它能够过滤numbers满足给定谓词的前5个元素(在这种情况下,可被3整除),而无需评估数组中的每个元素numbers.

然而,答案然后指出,filter(_:)每个元素可以多次调用谓词(范围1 ... 15中的元素为3次,结果为0时为2).

这种过滤器的惰性评估效率低下的原因是什么？有没有办法避免多次评估同一元素？

Answer 1

问题

这里的第一个罪魁祸首是切片懒惰过滤器收集通过使用prefix(_:)-这,在这种情况下,返回BidirectionalSlice的LazyFilterBidirectionalCollection.

通常,a的切片Collection需要存储基本集合,以及对切片"有效"的索引范围.因此,为了创建a的切片LazyFilterBidirectionalCollection以查看前5个元素,存储的索引范围必须是startIndex ..< indexAfterTheFifthElement.

为了得到indexAfterTheFifthElement,LazyFilterBidirectionalCollection必须遍历基集合(numbers)以找到满足谓词的第6个元素(你可以在这里看到索引的确切实现).

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

第二个罪魁祸首是Array's init(_:),它接受Sequence与数组Element类型相同类型的元素.该初始化程序的实现调用_copyToContiguousArray()序列,对于大多数序列,该序列将调用转发给此函数:

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

这里的问题是underestimatedCount.对于普通序列,这只是一个返回0的默认实现 - 但是,对于集合,它有一个默认实现,它获取count集合的内容(我在这里更详细地讨论).

为默认实现count的Collection(这BidirectionalSlice将在这里使用)很简单:

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

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

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

这个遍历索引的原因是没有重新评估结果的第一个元素的元素(在问题的例子中注意,0被评估的时间减去一次)是因为它不能直接访问所述startIndex的LazyFilterBidirectionalCollection,其具有以评估所有元素,直到在结果的第一个元素.相反,迭代器可以从切片本身的起始索引开始工作.

解决方案

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

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

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

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

因此,如果你说:

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

当传递给初始化器时,numbers(直到第5次匹配)的元素只会被filter(_:)'s谓词评估一次Array,因为你强迫Swift使用它Sequence的默认实现prefix(_:).

防止给定延迟过滤器集合上的所有索引操作的万无一失的方法是简单地使用延迟过滤器序列 - 这可以通过在以下内容中包装您希望执行惰性操作的集合来完成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]

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

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

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

结论(TL; DR)

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

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

但是,您应该警惕这样一个事实,即您可能会牺牲能够从最终索引集合,这对于诸如此类的操作非常重要suffix(_:).

最后,值得注意的是,这不是懒惰视图的问题LazyMapCollection,因为它们的元素不依赖于先前元素的"结果" - 因此如果它们的基本集合是a,它们可以在恒定时间内被索引RandomAccessCollection.