swift - 优化惰性集合

Question

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

问题

Swift 期望对 Collection 的操作是 O(1)。一些操作，特别是 prefix 和 suffix 类类型，偏离并且在 O(n) 或更高的顺序上。

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

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

想法

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

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

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

但是类是引用类型。 对惰性集合使用引用类型有什么缺点？Swift 标准库不使用它们作为初学者。

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

Answer 1

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

这些集合已经超出了它们的复杂性要求，it's true :

Note: The performance of accessing startIndex, first, or any methods that depend on startIndex depends on how many elements satisfy the predicate at the start of the collection, and may not offer the usual performance given by the Collection protocol. Be aware, therefore, that general operations on LazyDropWhileCollection instances may not have the documented complexity.

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

这样的循环

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

仍然是 O(n^2)。还要记住 O(1) 和“快速”不是一回事。感觉就像您正在尝试“快速”，但这并没有解决复杂性 promise (也就是说，惰性结构已经在 Swift 中打破了它们的复杂性 promise )。

缓存是一个净负面因素，因为它使惰性数据结构的正常(和预期)使用变慢。使用惰性数据结构的正常方法是使用它们零次或一次。如果您要多次使用它们，则应使用严格的数据结构。缓存您从不使用的内容是浪费时间和空间。

肯定有一些可以想象的用例，其中您有一个大型数据结构，将被多次稀疏访问，因此缓存会很有用，但这不是构建 lazy 的用例处理。

Attempting to optimize lazy collections on structs by using caching is impossible since subscript(_ position:) and all other methods that you'd need to implement to conform to LazyProtocolCollection are non-mutating and structs are immutable by default. This means that we have to recompute all operations for every call to a property or method.

这不是真的。一个结构可以在内部存储一个引用类型来保存它的缓存，这很常见。字符串正是这样做的。它们包括一个 StringBuffer ，它是一个引用类型(由于与 Swift 编译器错误相关的原因， StringBuffer 实际上是作为一个包装类的结构实现的，但从概念上讲它是一个引用类型)。 Swift 中的许多值类型都以这种方式存储内部缓冲区类，这允许它们在呈现不可变接口(interface)的同时在内部可变。 (这对于 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 不是那个工具是合理的。