优化惰性集合

Question

这个问题是关于优化惰性集合的。我将首先解释问题，然后对可能的解决方案进行一些思考。问题以粗体显示。

问题

Swift期望对Collections的操作为O（1）。一些操作中，特别是prefix与suffix样类型，偏离且为O（n）或更高的量级上。

延迟集合不能在初始化期间遍历基本集合，因为应该将计算尽可能长地延迟，直到实际需要该值为止。

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

思想

最明显的解决方案是缓存。这意味着第一次调用集合的方法具有不利的时间复杂度，但是随后可以在O（1）中计算对相同或其他方法的后续调用。为了更快的计算，我们将一些空间复杂度交易为O（n）的数量级。

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

这给我们留下了classes。类是可变的，这意味着所有计算的属性和方法都可以在内部改变状态。当我们使用类优化延迟集合时，我们有两个选择。首先，如果惰性类型的属性是variable，那么我们将自己带入一个充满痛苦的世界。如果更改属性，则可能会使先前缓存的结果无效。我可以想象管理代码路径以使属性可变为令人头疼的问题。其次，如果我们使用lets ，那么我们很好。初始化期间设置的状态无法更改，因此不需要更新缓存的结果。请注意，此处我们仅讨论的是带有纯方法且没有副作用的惰性集合。

但是类是引用类型。将引用类型用于惰性集合有什么弊端？Swift标准库不使用它们作为入门。

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

Answer 1

我在这里完全同意亚历山大。如果您存储的是懒惰的收藏，通常您在做错事，而重复访问的费用将使您不断感到惊讶。

这些集合已经满足了其复杂性要求，这是真的：

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

但是缓存不能解决这个问题。第一次访问它们仍然是O（n），所以像

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

仍然是O（n ^ 2）。还请记住，O（1）和“快速”不是同一回事。感觉就像您正在尝试“快速”，但这并不能解决复杂性承诺（也就是说，惰性结构已经在Swift中违反了其复杂性承诺）。

缓存是一个净负数，因为它会使懒惰数据结构的正常（和预期）使用变慢。使用惰性数据结构的通常方法是消耗它们零次或一次。如果要多次使用它们，则应使用严格的数据结构。缓存一些您从未使用过的东西会浪费时间和空间。

在某些情况下，当然可以想象到您有一个大型数据结构，该结构将被稀疏访问多次，因此缓存将很有用，但这并不是lazy为处理这种情况而设计的。

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

这不是真的 结构可以在内部存储引用类型以保存其缓存，这很常见。字符串正是这样做的。它们包括a 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工具。