优化惰性集合
Optimizing lazy collections
这个问题是关于优化惰性集合的。我将首先解释问题，然后给出一些可能的解决方案的想法。问题在 粗体.
问题
Swift 期望对 Collection 的操作为 O(1)。一些操作，尤其是 prefix 和 suffix 类的类型，偏离并且在 O(n) 或更高的数量级上。
惰性集合无法在初始化期间遍历基础集合，因为计算应该尽可能地推迟，直到实际需要该值为止。
那么，我们如何优化惰性集合？当然这引出了一个问题，什么构成了优化的惰性集合？
想法
最明显的解决方案是缓存。这意味着对集合方法的第一次调用具有不利的时间复杂度，但对相同或其他方法的后续调用可能在 O(1) 中计算。我们将一些 space 的复杂度换成 O(n) 的阶数以加快计算速度。
尝试通过使用缓存来优化 struct 上的惰性集合是不可能的，因为 subscript(_ position:) 以及您需要实施以符合 LazyProtocolCollection 的所有其他方法都是非- mutating 和 struct 默认情况下是不可变的。这意味着我们必须为每次调用 属性 或方法重新计算所有操作。
这给我们留下了 classes。 类 是可变的，这意味着所有计算的属性和方法都可以在内部改变状态。当我们使用 类 来优化惰性集合时，我们有两个选择。首先，如果惰性类型的属性是 variables 那么我们就会把自己带入一个受伤的世界。如果我们更改 属性 它可能会使以前缓存的结果无效。我可以想象管理代码路径以使属性可变会令人头疼。其次，如果我们使用 lets 我们很好；初始化期间设置的状态无法更改，因此不需要更新缓存的结果。请注意，我们在这里只讨论具有没有副作用的纯方法的惰性集合。
但是类是引用类型。 对惰性集合使用引用类型有什么缺点？ Swift 标准库不为初学者使用它们。
对不同的方法有什么想法或想法吗？
Swift 的惰性集合旨在提供对元素的一次性访问。后续访问会导致冗余计算（例如，惰性映射序列会重新计算 transform 闭包。
如果您想要重复访问元素，最好只切分您关心的惰性 sequence/collection 部分，并从中创建一个适当的集合（例如数组）。
惰性评估和缓存每个元素的簿记开销可能大于收益。
我完全同意亚历山大的观点。如果您正在存储惰性集合，您通常会做错一些事情，并且重复访问的成本会不断地让您感到惊讶。
这些集合已经超出了它们的复杂性要求，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) 和 "fast" 不是一回事。感觉你正试图达到 "fast"，但这并没有解决复杂性承诺（也就是说，惰性结构已经在 Swift 中打破了它们的复杂性承诺）。
缓存是一个净负面因素，因为它使惰性数据结构的正常（和预期）使用变慢。使用惰性数据结构的正常方法是使用它们零次或一次。如果您要多次使用它们，则应使用严格的数据结构。缓存你从不使用的东西是浪费时间 and space.
当然有一些可以想象的用例，其中您有一个将被多次稀疏访问的大型数据结构，因此缓存会很有用，但这不是 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 实际上是作为一个包装 class 的结构实现的，但从概念上讲它是引用类型）。 Swift 中的许多值类型以这种方式存储内部缓冲区 classes，这允许它们在呈现不可变接口的同时在内部可变。 （这对于 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 不是那个工具是合理的。
这个问题是关于优化惰性集合的。我将首先解释问题，然后给出一些可能的解决方案的想法。问题在 粗体.
问题
Swift 期望对 Collection 的操作为 O(1)。一些操作，尤其是 prefix 和 suffix 类的类型，偏离并且在 O(n) 或更高的数量级上。
惰性集合无法在初始化期间遍历基础集合，因为计算应该尽可能地推迟，直到实际需要该值为止。
那么，我们如何优化惰性集合？当然这引出了一个问题，什么构成了优化的惰性集合？
想法
最明显的解决方案是缓存。这意味着对集合方法的第一次调用具有不利的时间复杂度，但对相同或其他方法的后续调用可能在 O(1) 中计算。我们将一些 space 的复杂度换成 O(n) 的阶数以加快计算速度。
尝试通过使用缓存来优化 struct 上的惰性集合是不可能的，因为 subscript(_ position:) 以及您需要实施以符合 LazyProtocolCollection 的所有其他方法都是非- mutating 和 struct 默认情况下是不可变的。这意味着我们必须为每次调用 属性 或方法重新计算所有操作。
这给我们留下了 classes。 类 是可变的，这意味着所有计算的属性和方法都可以在内部改变状态。当我们使用 类 来优化惰性集合时，我们有两个选择。首先，如果惰性类型的属性是 variables 那么我们就会把自己带入一个受伤的世界。如果我们更改 属性 它可能会使以前缓存的结果无效。我可以想象管理代码路径以使属性可变会令人头疼。其次，如果我们使用 lets 我们很好；初始化期间设置的状态无法更改，因此不需要更新缓存的结果。请注意，我们在这里只讨论具有没有副作用的纯方法的惰性集合。
但是类是引用类型。 对惰性集合使用引用类型有什么缺点？ Swift 标准库不为初学者使用它们。
对不同的方法有什么想法或想法吗？
Swift 的惰性集合旨在提供对元素的一次性访问。后续访问会导致冗余计算（例如，惰性映射序列会重新计算 transform 闭包。
如果您想要重复访问元素，最好只切分您关心的惰性 sequence/collection 部分，并从中创建一个适当的集合（例如数组）。
惰性评估和缓存每个元素的簿记开销可能大于收益。
我完全同意亚历山大的观点。如果您正在存储惰性集合，您通常会做错一些事情，并且重复访问的成本会不断地让您感到惊讶。
这些集合已经超出了它们的复杂性要求，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) 和 "fast" 不是一回事。感觉你正试图达到 "fast"，但这并没有解决复杂性承诺（也就是说，惰性结构已经在 Swift 中打破了它们的复杂性承诺）。
缓存是一个净负面因素，因为它使惰性数据结构的正常（和预期）使用变慢。使用惰性数据结构的正常方法是使用它们零次或一次。如果您要多次使用它们，则应使用严格的数据结构。缓存你从不使用的东西是浪费时间 and space.
当然有一些可以想象的用例，其中您有一个将被多次稀疏访问的大型数据结构，因此缓存会很有用，但这不是 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 实际上是作为一个包装 class 的结构实现的，但从概念上讲它是引用类型）。 Swift 中的许多值类型以这种方式存储内部缓冲区 classes，这允许它们在呈现不可变接口的同时在内部可变。 （这对于 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 不是那个工具是合理的。