Почему дважды обращенный итератор действует так, как будто он никогда не был обращен?

Question

У меня есть входной вектор, который содержит числа. В выходном векторе мне нужно получить последовательность частичных произведений, но в порядке справа налево. Последний элемент вывода должен быть равен последнему на входе; второй-последний элемент выходных данных должен быть произведением последних и вторых-последних элементов входных данных; и так далее. Например, если входной вектор равен

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

тогда мне нужно, чтобы результат был [24, 12, 4].

Моя реализация берет итератор для ввода, переворачивает его, map s, снова переворачивает и collect s:

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], так же, как если бы я удалил оба rev() s. Два rev() не решают проблему, они просто "уничтожают" друг друга.

Решается ли эта задача в стиле «цепочки вызовов», без использования for?

Answer 1

Ваша переменная prod передает состояние от одного элемента к следующему, а это не то, что делает отображение.Сопоставления работают с каждым элементом независимо, что облегчает их распараллеливание и упрощает рассуждение.Результат, который вы запрашиваете, должен быть точным при правильном сканировании (обратный случай префиксной суммы ), но я не уверен, что есть удобные методы для сбора изправильно (вероятно, самый простой изменяемый способ - использовать VecDeque::push_front).Это заставило меня выполнить операцию за два прохода для моей первой версии:

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);
}

Обратите внимание, что initprod является неизменным;prod несет государство.Использование into_iter также означает, что prev потребляется.Мы могли бы использовать vec.reverse, как показано mcarton, но тогда нам нужна переменная переменная.Сканы могут быть распараллелены, но в меньшей степени, чем карты.См., Например, обсуждение о добавлении их в район .Можно также рассмотреть вопрос о том, должен ли ExactSizeIterator разрешить обратный сбор в обычный вектор, но стандартная библиотека scan метод разбивает известный размер, используя Option (который поnext конвенция превращает его в "сканирование на время").

Вот несколько вариантов копирования, использующих предварительно выделенный 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);
}

Кстати, после старой поговорки о том, что программисты на Лиспе знают ценность всего и ничего не стоят, вот версия на Haskell, я не знаю, насколько она неэффективна:

scanr1 (*) [2, 3, 4]

Answer 2

Это поведение на самом деле явно описано в документации :

Примечания о побочных эффектах

Итератор map реализует DoubleEndedIterator, что означает, что Вы также можете map в обратном направлении:

[...]

Но если ваше закрытие имеет состояние, итерация в обратном направлении может действовать так, как вы делаете не ожидайте. [...]

Чтобы решить эту проблему , добавьте посредника collect, чтобы убедиться, что второй rev не применяется к Map:

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);
}