,它在它的第一个版本,也有类似的代码如下:
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。
numbers
但是,答案随后表明,filter(_:)每个元素可以多次调用’谓词(对于范围为1 … 15的元素,其谓词为3次,结果为0,则为两次)。
filter(_:)
懒惰评估此过滤器效率低下的原因是什么?有什么方法可以避免多次评估同一元素?
这里的第一个罪魁祸首是 切片 懒惰过滤器收集通过使用prefix(_:)-这,在这种情况下,返回BidirectionalSlice的LazyFilterBidirectionalCollection。
prefix(_:)
BidirectionalSlice
LazyFilterBidirectionalCollection
通常,对s的切片Collection需要对基本集合进行存储,以及对要“查看”的切片有效的索引范围。因此,为了创建a的切片LazyFilterBidirectionalCollection以查看前5个元素,存储的索引范围必须为startIndex ..< indexAfterTheFifthElement。
Collection
startIndex ..< indexAfterTheFifthElement
为了获取indexAfterTheFifthElement,LazyFilterBidirectionalCollection必须遍历基本集合(numbers),以找到满足谓词的 第6个 元素(您可以在此处看到索引的确切实现)。
indexAfterTheFifthElement
因此,只需简单地针对谓词检查上述示例中0 … 15范围内的所有元素,即可创建惰性过滤器集合的一部分。
第二个罪魁祸首是Array的init(_:),它接受Sequence与数组Element类型相同类型的元素。此初始化程序的实现调用_copyToContiguousArray()序列,对于大多数序列,该序列会将调用转发给此函数:
Array
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集合的。
underestimatedCount
count
为默认实现count的Collection(这BidirectionalSlice将在这里使用)很简单:
public var count: IndexDistance { return distance(from: startIndex, to: endIndex) }
对于我们的切片,该索引将遍历直到的索引indexAfterTheFifthElement,从而再次重新评估范围为0 … 15的元素。
最后,进行切片的迭代器,并对其进行迭代,将序列中的每个元素添加到新数组的缓冲区中。对于BidirectionalSlice,它将使用IndexingIterator,通过前进索引并为每个索引输出元素来简单地工作。
IndexingIterator
为什么之所以 这样 走了指数不重新评估的元素到结果的第一个元素(在问题的例子音符,0评价一个时间少)是由于它不直接访问的事实所述startIndex的LazyFilterBidirectionalCollection,其具有以评估所有元素,直到在结果的第一个元素。相反,迭代器可以从切片本身的起始索引开始工作。
startIndex
一种简单的解决方案是避免切片延迟过滤器集合以获取其前缀,而是延迟应用前缀。
实际上有两种实现prefix(_:)。一个由提供Collection,并返回一个SubSequence(对于大多数标准库集合来说,这是某种形式的切片)。
SubSequence
另一个由提供Sequence,返回一个AnySequence-在后台使用的基本序列_PrefixSequence,该序列简单地使用一个迭代器并允许对其进行迭代,直到迭代了给定数量的元素为止- 然后停止返回元素。
AnySequence
_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(_:)在传递给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(_:),它很可能是更有效的工作,以延迟集合一个序列(至少对于小输入),因为它们可以简单地从收集的结束索引。
suffix(_:)
dropLast(_:)
尽管与所有与性能相关的问题一样,您首先应该首先检查这是否是一个问题,然后再运行自己的测试以查看哪种方法更适合您的实现。
因此,在所有这些之后,您将要警惕的事实是,对惰性过滤器集合进行切片可以重新评估基础集合的每个元素,直到切片可以“查看”的最终索引。
通常,更可取的是将惰性过滤器集合视为无法索引的 序列 ,因此,这意味着惰性操作无法评估任何元素(否则可能会破坏性地迭代它们),直到急切的操作发生为止。
但是,您应该警惕以下事实:您可能会牺牲从结尾对集合进行索引的能力,这对于诸如这样的操作很重要suffix(_:)。
最后,值得注意的是,对于诸如这样的惰性视图来说,这不是问题LazyMapCollection,因为它们的元素不依赖于先前元素的“结果”,因此,如果它们的基本集合是a,则可以在恒定的时间对其进行索引RandomAccessCollection。
LazyMapCollection
RandomAccessCollection