swift - 为什么过滤器(_ :)’s predicate get called so many times when evaluating it lazily?

Question

我看到了 an answer至 this 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 .

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

为了得到indexAfterTheFifthElement , LazyFilterBidirectionalCollection必须遍历基础集合( numbers )才能找到满足谓词的第 6 个元素(您可以看到 the exact implementation of the indexing here )。

因此，上面示例中 0...15 范围内的所有元素都需要根据谓词进行检查，以便创建惰性过滤器集合的切片。

第二个罪魁祸首是Array的 init(_:) ，它接受 Sequence与数组 Element 相同类型的元素类型。 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()
}

这里的问题是underestimatedCount .对于普通序列，它只有一个返回 0 的默认实现——然而，对于集合，它有一个默认实现，它获取 count的集合(我进入这个 in more detail here)。
count 的默认实现的 Collection (BidirectionalSlice 将在这里使用)很简单:

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

其中，对于我们的切片，将遍历索引直至 indexAfterTheFifthElement ，从而再次重新评估 0...15 范围内的元素。

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

这种遍历索引不会重新评估元素直到结果的第一个元素的原因(注意在问题的示例中，0 的评估次数少了一次)是因为它不直接访问startIndex的LazyFilterBidirectionalCollection , 其中 has to evaluate all elements up to the first element in the result .相反，迭代器可以从切片本身的起始索引开始工作。

解决方案

简单的解决方案是避免切片延迟过滤器集合以获得其前缀，而是延迟应用前缀。
prefix(_:)实际上有两种实现.一个是provided by Collection ，并返回 SubSequence (这是大多数标准库集合的某种形式的切片)。

另一个是provided by 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 这样的惰性 View ，这不是问题。 ，因为它们的元素不依赖于先前元素的“结果”——因此，如果它们的基本集合是 RandomAccessCollection，它们可以在恒定时间内被索引。 .