Swift Collection低估了使用量

Question

什么是用例集合underestimateCount.文档说它与标准收集计数具有相同的复杂性.

我看过它的声明:

/// Returns a value less than or equal to the number of elements in
/// `self`, *nondestructively*.
///
/// - Complexity: O(N).
public func underestimateCount() -> Int

但它并没有告诉我什么时候应该使用它以及出于什么原因.

Answer 1

underestimatedCount实际上是Sequence协议的要求,并且有一个只返回的默认实现0:

public var underestimatedCount: Int {
  return 0
}

但是,对于提供其自身实现的序列underestimatedCount,这对于需要序列有多长的下限的逻辑非常有用,而不必迭代它(请记住,Sequence不能保证非破坏性迭代).

例如,map(_:)on on Sequence(参见其在此实现中)的方法underestimateCount用于为结果数组保留初始容量:

  public func map<T>(
    _ transform: (Iterator.Element) throws -> T
  ) rethrows -> [T] {

    let initialCapacity = underestimatedCount
    var result = ContiguousArray<T>()
    result.reserveCapacity(initialCapacity) 

    // ...

这允许map(_:)最小化重复附加的成本result,因为已经(可能)已经为其分配了(可能)已经为其分配的初始内存块(尽管其值得注意的是ContiguousArray具有指数增长策略以分摊附加成本).

然而,在的情况下Collection,默认实现的underestimateCount实际上只是返回集合的count:

public var underestimatedCount: Int {
    // TODO: swift-3-indexing-model - review the following
  return numericCast(count)
}

对于符合RandomAccessCollectionO(n)的集合,这将是O(1)操作.

因此,由于这个默认实现,直接使用Collection's' underestimatedCount绝对不如使用Sequence's',因为Collection保证非破坏性迭代,并且在大多数情况下underestimatedCount只返回count.

当然,自定义集合类型可以提供它们自己的实现underestimatedCount- 给出它们包含的元素数量的下限,以可能比它们的count实现更有效的方式,这可能是有用的.