小编典典

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

swift

,它在它的第一个版本,也有类似的代码如下:

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,则为两次)。

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


阅读 270

收藏
2020-07-07

共1个答案

小编典典

问题所在

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

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

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

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

第二个罪魁祸首是Arrayinit(_:),它接受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集合的。

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

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

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

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

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


解决方案

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

实际上有两种实现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

2020-07-07