rust - Rust 如何找出迭代器的上限？

Question

我正在浏览几个 Rust 示例，并且有一段特定的代码片段我并不真正理解它是如何工作的。特别是，this example高阶函数。我的重点是这段代码:

let sum_of_squared_odd_numbers: u32 =
    (0..).map(|n| n * n)             // All natural numbers squared
         .take_while(|&n| n < upper) // Below upper limit
         .filter(|n| is_odd(*n))     // That are odd
         .fold(0, |sum, i| sum + i); // Sum them

这是我的问题:

1. 编译器如何知道(0..) 何时结束？循环是否在编译时展开并且所有的 lambda 都被评估了？

2. 与命令式版本相比，这不是内存效率极低吗？例如 (0..).map(|n| n * n) 最终会占用 O(n) 内存。

Answer 1

How does the compiler know when (0..) ends?

编译器根本不知道。这是一个范围文字，特别是 RangeFrom .请注意，它实现了 Iterator特征。 Iterator的核心部分是next :

fn next(&mut self) -> Option<Self::Item>

也就是说，给迭代器一个可变的借用，它可以返回另一个项目(Some)或表示没有更多的项目(None)。迭代器完全有可能 go on forever .

在这个特定的例子中:

• 在停止 ^† 之前，该范围将产生每个无符号的 32 位数字。
• map 将在底层迭代器停止时停止。
• take_while 将在谓词失败或底层迭代器停止时停止。
• 过滤器 将在底层迭代器停止时停止。
• fold 将在底层迭代器停止时停止。

Isn't this extremely memory inefficient compared to the imperative version?

不!事实上，编译器很有可能将此编译为与命令式版本相同的代码!您可能想要 100% 确定地检查 LLVM IR 或程序集，但 Rust 的单态化功能与 LLVM 的优化器相结合可以做一些非常了不起的事情。

每个迭代器适配器 从前一个适配器中提取足够的项目来计算下一个值。在您的示例中，我希望为整个过程分配一个恒定的内存。

管道中唯一需要任何额外空间的组件是 fold，它只需要一个 u32 累加器值。所有其他适配器都没有额外的状态。

需要注意的重要一点是，调用 map、filter 和 take_while 迭代器适配器不会进行任何迭代器计算时间点。他们只是返回新对象:

// Note the type is
// Filter<TakeWhile<Map<RangeFrom<_>, [closure]>, [closure]>, [closure]>
let () = 
    (0..)
    .map(|n| n * n)            
    .take_while(|&n| n < 20)
    .filter(|n| n % 2 == 0);
// At this point, we still haven't even looked at a single value

每当您在最终适配器上调用 next 时，适配器堆栈的每一层都会完成足够的工作来获取下一个值。在原始示例中，fold 是一个迭代器终止符，它消耗整个迭代器，调用next 直到没有更多值。

† 作为bluss points out ，您真的不想尝试超过范围的最大值，因为它会 panic or loop forever ，取决于它是在 Debug模式还是 Release模式下构建的。