优化惰性集合

这个问题是关于优化惰性集合的。我将首先解释问题，然后给出一些可能的解决方案的想法。问题在bold.

Problem

Swift 预计运营Collections 为 O(1)。一些操作，特别是prefix and suffix类类型、偏离类型且数量级为 O(n) 或更高。

惰性集合无法在初始化期间迭代基集合，因为计算应尽可能延迟，直到实际需要该值为止。

So, 我们如何优化惰性集合？当然，这引出了一个问题，什么构成了优化的惰性集合？

Thoughts

最明显的解决方案是caching。这意味着对集合方法的第一次调用具有不利的时间复杂度，但对相同或其他方法的后续调用可能会在 O(1) 中计算。我们将一些空间复杂度换成 O(n) 量级，以获得更快的计算速度。

尝试优化惰性集合struct通过使用缓存是不可能的，因为subscript(_ position:)以及您需要实现以符合的所有其他方法LazyProtocolCollection是非mutating and struct默认情况下 s 是不可变的。这意味着我们必须为每次调用属性或方法重新计算所有操作。

这给我们留下了classes.类是可变的，这意味着所有计算属性和方法都可以在内部改变状态。当我们使用类来优化惰性集合时，我们有两个选择。首先，如果惰性类型的属性是var那么我们就会把自己带入一个受伤的世界。如果我们更改属性，则可能会使之前缓存的结果无效。我可以想象管理代码路径以使属性可变是一件令人头痛的事情。其次，如果我们使用let我们很好；初始化期间设置的状态无法更改，因此不需要更新缓存结果。请注意，我们在这里仅讨论具有纯方法且没有副作用的惰性集合。

但类是引用类型。对惰性集合使用引用类型有哪些缺点？Swift 标准库对于初学者来说并不使用它们。

对不同方法有什么想法或想法吗？

我完全同意亚历山大的观点。如果您存储惰性集合，那么您通常会做错一些事情，并且重复访问的成本会不断让您感到惊讶。

这些集合已经超出了它们的复杂性要求，这是真的 https://developer.apple.com/documentation/swift/lazydropwhilecollection:

注意：访问 startIndex、first 或任何依赖于 startIndex 的方法的性能取决于有多少元素满足集合开头的谓词，并且可能无法提供 Collection 协议给出的通常性能。因此，请注意，LazyDropWhileCollection 实例上的常规操作可能没有记录的复杂性。

但缓存并不能解决这个问题。第一次访问时它们仍然是 O(n)，所以像这样的循环

for i in 0..<xs.count { print(xs[i]) }

仍然是 O(n^2)。还要记住 O(1) 和“快”不是一回事。感觉就像你试图达到“快速”，但这并不能解决复杂性承诺（也就是说，惰性结构已经打破了 Swift 中的复杂性承诺）。

缓存是一个净负面因素，因为它使惰性数据结构的正常（和预期）使用速度变慢。使用惰性数据结构的正常方法是消耗它们零次或一次。如果您要多次使用它们，则应该使用严格的数据结构。缓存你从不使用的东西是浪费时间and space.

当然，在某些可以想象的用例中，您有一个大型数据结构，将被稀疏地多次访问，因此缓存会很有用，但这不是用例lazy是为了处理而建造的。

尝试使用缓存来优化结构上的惰性集合是不可能的，因为 subscript(_position:) 以及您需要实现以符合 LazyProtocolCollection 的所有其他方法都是不可变的，并且默认情况下结构是不可变的。这意味着我们必须为每次调用属性或方法重新计算所有操作。

这不是真的。结构体可以在内部存储引用类型来保存其缓存，这很常见。字符串正是这样做的。它们包括一个StringBuffer这是一个引用类型（由于与 Swift 编译器错误相关的原因，StringBuffer实际上是作为包装类的结构实现的，但从概念上讲它是引用类型）。 Swift 中的许多值类型都以这种方式存储内部缓冲区类，这使得它们在呈现不可变接口的同时可以在内部可变。 （这对于 CoW 以及许多其他性能和内存相关的原因也很重要。）

请注意，今天添加缓存也会破坏现有的用例lazy:

struct Massive {
    let id: Int
    // Lots of data, but rarely needed.
}

// We have lots of items that we look at occassionally
let ids = 0..<10_000_000

// `massives` is lazy. When we ask for something it creates it, but when we're 
// done with it, it's thrown away. If `lazy` forced caching, then everything 
// we accessed would be forever. Also, if the values in `Massive` change over
// time, I certainly may want it to be rebuilt at this point and not cached.
let massives = ids.lazy.map(Massive.init)
let aMassive = massives[10]

这并不是说缓存数据结构在某些情况下没有用处，但它肯定并不总是有利的。它会带来大量成本，并在帮助其他用途的同时破坏一些用途。因此，如果您想要这些其他用例，您应该构建一个提供它们的数据结构。但合理的是lazy不是那个工具。