为什么双重反转的迭代器会表现得好像它从未反转过一样?

Why does a doubly-reversed iterator act as if it was never reversed?

提问人:mrbus2007 提问时间:8/25/2018 最后编辑:Masaki Haramrbus2007 更新时间:8/26/2018 访问量:668

问:

我有一个包含数字的输入向量。在输出向量中,我需要按从右到左的顺序获取部分乘积序列。输出的最后一个元素必须等于输入中的最后一个元素;输出的倒数第二个元素必须是输入的最后一个和倒数第二个元素的乘积;等等。例如,如果输入向量是

let input = vec![2, 3, 4];

那么我需要输出是 .[24, 12, 4]

我的实现在输入上采用迭代器,反转它,s,再次反转和s:mapcollect

fn main() {
    let input = vec![2, 3, 4];
    let mut prod = 1;
    let p: Vec<usize> = input
        .iter()
        .rev()
        .map(|v| {
            prod *= v;
            prod
        }).rev()
        .collect();
    println!("{:?}", p);
}

结果是 [2, 6, 24],与我删除两个 s 相同。两者并不能解决问题,他们只是“歼灭”了对方。rev()rev()

这个任务是否可以在不使用的情况下以“呼叫链”方式解决?for

评论

1赞 Yann Vernier 8/25/2018
在我看来,你想要一个 ,而不是一个 .让操作改变外部状态是某种混淆的。scanmapmapfor

答:

11赞 mcarton 8/25/2018 #1

此行为实际上在文档中明确描述

关于副作用的注意事项

映射迭代器实现了 DoubleEndedIterator,这意味着 您还可以向后映射

[...]

但是,如果你的闭包有状态,那么向后迭代可能会以你的方式起作用 没想到。[...]

解决此问题的一种方法是添加一个中间集合,以确保第二个不适用于:revMap

fn main() {
    let input = vec![2, 3, 4];
    let mut prod = 1;
    let p: Vec<usize> = input
        .iter()
        .map(|v| {
            prod *= v;
            prod
        }).rev()
        .collect::<Vec<_>>()
        .into_iter()
        .rev()
        .collect();
    println!("{:?}", p);
}

但这需要额外的分配。另一种方法是收集,然后反转

fn main() {
    let input = vec![2, 3, 4];
    let mut prod = 1;
    let mut p: Vec<usize> = input
        .iter()
        .rev()
        .map(|v| {
            prod *= v;
            prod
        }).collect();
    p.reverse();

    println!("{:?}", p);
}

评论

0赞 mrbus2007 8/25/2018
非常感谢,@mcarton。但确切地说,预期的结果是 ,所以我们需要 before .[24, 12, 4]revmap
1赞 cafce25 6/11/2023
你没有。你所需要的只是你反向收集,所以在任何地方都可以。.rev().collect()
2赞 Yann Vernier 8/25/2018 #2

变量将状态从一个项目传递到下一个项目,这不是映射的作用。映射独立地对每个元素进行操作,这使得它们易于并行化且更易于推理。您要求的结果是精确的右扫描前缀总和的反转情况),但我不确定是否有方便的方法可以从右侧收集(可能最简单的可变方法是使用 VecDeque::p ush_front)。这导致我在第一个版本中分两遍执行该操作:prod

fn main() {
    let input: Vec<usize> = vec![2, 3, 4];
    let initprod = 1;
    let prev: Vec<usize> = input
        .iter()
        .rev()
        .scan(initprod, |prod, &v| {
            *prod *= v;
            Some(*prod)
        }).collect();
    let p: Vec<usize> = prev.into_iter().rev().collect();
    println!("{:?}", p);
}

请注意,这是不可变的; 携带状态。使用也意味着被消耗。我们可以像 mcarton 所示使用,但我们需要有一个可变变量。扫描可以并行化,但程度低于地图。例如,请参阅有关将它们添加到人造丝的讨论。人们还可以考虑 ExactSizeIterator 是否应该允许反向收集到普通向量中,但标准库扫描方法会破坏已知大小 use(按照惯例,这会将其转换为 take-while-scan)。initprodprodinto_iterprevvec.reverseOptionnext

这是一个较少的复制变体,使用预分配的 VecDeque 从右侧收集。我使用了一个额外的范围来限制可变性。它还需要 Rust 1.21 或更高版本才能使用 .跟踪项目数量和环形缓冲区结构会产生不必要的开销,但至少在某种程度上仍然清晰可辨。for_each

use std::collections::VecDeque;

fn main() {
    let input: Vec<usize> = vec![2,3,4];
    let p = {
        let mut pmut = VecDeque::with_capacity(input.len());
        let initprod = 1;
        input
            .iter()
            .rev()
            .scan(initprod, |prod, &v| {
                *prod *= v;
                Some(*prod)
            })
            .for_each(|v| { 
                pmut.push_front(v)
            });
        pmut
    };
    println!("{:?}", p);
}

顺便说一句,按照一句古老的格言,Lisp程序员知道一切的价值和什么都没有的成本,这里有一个Haskell版本,我真的不知道它有多低效:

scanr1 (*) [2, 3, 4]

评论

0赞 Shepmaster 8/25/2018
在像 Rust 这样的语言中,可变性本身并没有错,它限制可变变量一次只能由一个事物使用。例如,我希望效率更高,因为它不需要为向量释放和重新分配空间。Vec::reverse
0赞 Shepmaster 8/25/2018
从右边收集 — 在 A 和 Do 或 A 和 Do 上实现 NewType 似乎是合理的。FromIteratorVecreverseVecDequepush_front
0赞 Yann Vernier 8/25/2018
我同意,可变 vec 上的反向更有效。这只是将突变适合的范围限制在降低以下错误的风险范围内的问题。
3赞 Shepmaster 8/25/2018
let p = { /* ... */ pmut };会更惯用。