为什么filter（_ :)的谓词在懒惰地求值时会被调用那么多次？

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，则为两次）。

懒惰评估此过滤器效率低下的原因是什么？有什么方法可以避免多次评估同一元素？

Answer 1

问题所在

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

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

为了获取indexAfterTheFifthElement，LazyFilterBidirectionalCollection必须遍历基本集合（numbers），以找到满足谓词的
第6个
元素（您可以在此处看到索引的确切实现）。

因此，只需简单地针对谓词检查上述示例中0 … 15范围内的所有元素，即可创建惰性过滤器集合的一部分。

第二个罪魁祸首是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集合的。

为默认实现count的Collection（这BidirectionalSlice将在这里使用）很简单：

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

对于我们的切片，该索引将遍历直到的索引indexAfterTheFifthElement，从而再次重新评估范围为0 … 15的元素。

最后，进行切片的迭代器，并对其进行迭代，将序列中的每个元素添加到新数组的缓冲区中。对于BidirectionalSlice，它将使用IndexingIterator，通过前进索引并为每个索引输出元素来简单地工作。

为什么之所以 这样
走了指数不重新评估的元素到结果的第一个元素（在问题的例子音符，0评价一个时间少）是由于它不直接访问的事实所述startIndex的LazyFilterBidirectionalCollection，其具有以评估所有元素，直到在结果的第一个元素。相反，迭代器可以从切片本身的起始索引开始工作。

解决方案

一种简单的解决方案是避免切片延迟过滤器集合以获取其前缀，而是延迟应用前缀。

实际上有两种实现prefix(_:)。一个由提供Collection，并返回一个SubSequence（对于大多数标准库集合来说，这是某种形式的切片）。

另一个由提供Sequence，返回一个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(_:)，它很可能是更有效的工作，以延迟集合一个序列（至少对于小输入），因为它们可以简单地从收集的结束索引。

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

结论（TL; DR）

因此，在所有这些之后，您将要警惕的事实是，对惰性过滤器集合进行切片可以重新评估基础集合的每个元素，直到切片可以“查看”的最终索引。

通常，更可取的是将惰性过滤器集合视为无法索引的 序列 ，因此，这意味着惰性操作无法评估任何元素（否则可能会破坏性地迭代它们），直到急切的操作发生为止。

但是，您应该警惕以下事实：您可能会牺牲从结尾对集合进行索引的能力，这对于诸如这样的操作很重要suffix(_:)。

最后，值得注意的是，对于诸如这样的惰性视图来说，这不是问题LazyMapCollection，因为它们的元素不依赖于先前元素的“结果”，因此，如果它们的基本集合是a，则可以在恒定的时间对其进行索引RandomAccessCollection。