如果我有这样的代码:
pub fn f(x: u16) -> impl Iterator<Item = u16> {
std::iter::once(0).chain((x >> 10)..x)
}
当我使用once
在迭代器前面链接一个常量时,当迭代器被消耗时,我是否为它支付O(n)成本?我无法从程序集中判断(除了它肯定在内存中设置了一个额外的数据结构之外)。我该怎么说?
如前所述,once()
的成本为O(1)。您所考虑的O(n)成本来自chain()
,而不是once()
,因为至少在优化之前,<Chain as Iterator>::next()
必须在每一步决定是从第一个迭代器中获取项还是从第二个迭代机中获取项。
然而,通过使用内部迭代——迭代的控制流由迭代器本身负责,可以避免产生这种成本,这样就不需要重复调用next()
。最像for
的方式是for_each()
。如果您查看此代码生成的程序集,您可以看到在main2()
:中使用for_each()
的版本中它要简单得多
pub fn f(x: u16) -> impl Iterator<Item = u16> {
std::iter::once(0).chain((x >> 10)..x)
}
pub fn main1() -> u16 {
let mut sum = 0;
for item in f(3) {
sum += std::hint::black_box(item);
}
sum
}
pub fn main2() -> u16 {
let mut sum = 0;
f(3).for_each(|item| {
sum += std::hint::black_box(item);
});
sum
}
(我使用std::hint::black_box()
来阻止将循环优化为常数。)
这有帮助的原因是for_each()
是根据fold()
实现的,Chain
迭代器覆盖fold()
的默认实现,因此它调用第一个迭代器自己的fold()
,然后调用第二个迭代者的。没有每个项目的条件句。
您不必显式地使用for_each()
或fold()
——您应该期望可以从中受益的任何迭代器操作,如sum()
或collect()
,都会这样做。通常,如果您正在寻找最佳迭代器性能,并且涉及到chain()
等内容,尝试使用对迭代器的单个调用来表达您的操作,而不是next()
或转换为next()
的东西,如for item in iter {}
循环。
但是,如果要使用像continue
或await
这样的控制流结构,则需要一个for
循环。
如果我在迭代器前面使用一次将常量链接起来,我会为此付出O(n)代价吗?
什么n的O(n)?
我脑海中的曾经在运行时翻译成if,这表明它确实如此。
代码方面的Once
实际上只是Option
迭代器的包装器,而所做的就是在自身上调用take
。
take
为:
mem::replace(self, None)
所以在once
中没有实际的if at runtime
,条件是在迭代协议中。
chain
中存在一些条件,因为它需要从第一个运算符切换到第二个运算符,所以它在那里变得有点复杂。
如何判断?
如果使用godbolt,可能会更容易,因为它的装配视图比操场要好得多。