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

Question

我正在阅读几个Rust示例,并且有一些特定的代码片段,我真的不明白它是如何工作的.特别是高阶函数的这个例子.我的重点是这段代码:

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

编译器如何知道何时(0..)结束？

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

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

也就是说,给迭代器一个可变的借位,它可以返回另一个item(Some)或表示没有更多的项目(None).完全有可能让迭代器永远持续下去.

在这个特定的例子中:

• 在停止^†之前,该范围将产生每个无符号的32位数.
• 在map底层迭代器停止时将停止.
• 在take_while当断言失败或底层迭代器停止将停止.
• 在filter底层迭代器停止时将停止.
• 在fold底层迭代器停止时将停止.

与命令式版本相比,这不是非常低效的内存吗？

不!实际上,编译器很可能将其编译为与命令式版本相同的代码!你想要检查LLVM IR或程序集是100%确定的,但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指出的那样,你真的不想尝试超过范围的最大值,因为它会恐慌或永远循环,这取决于它是在调试版本还是发布模式下构建.