Почему я получаю противоречивый результат, когда цепочечные итераторы вместо того, чтобы собирать во временный HashSet? - PullRequest
Новая
       41

Почему я получаю противоречивый результат, когда цепочечные итераторы вместо того, чтобы собирать во временный HashSet?

0 голосов
/ 18 сентября 2018

Я пишу функцию Rust, которая принимает список чисел и максимальное значение и суммирует все кратные заданных чисел до максимума (дубликаты учитываются только один раз).Первая версия функции, которую я написал, была 

use std::collections::HashSet;

pub fn sum_of_multiples(limit: u32, factors: &[u32]) -> u32 {
    let set: HashSet<u32> = factors
        .iter()
        .map(|factor| {
            let top: u32 = (limit - 1) / factor;

            (1..=top).map(move |num| num * factor)
        }).flatten()
        .collect();

    set.iter().fold(0, |acc, num| acc + num)
}

(я знаю, слияние HashSets, как это, вероятно, не лучшее решение).Это дает ожидаемый результат: 

println!("{}", sum_of_multiples(100, &[3, 5])) // 2318

Когда я вынимаю вызов на collect в середине и цепью последнего fold, я получаю другой ответ: 

pub fn sum_of_multiples(limit: u32, factors: &[u32]) -> u32 {
    let val: u32 = factors
        .iter()
        .map(|factor| {
            let top: u32 = (limit - 1) / factor;

            (1..=top).map(move |num| num * factor)
        }).flatten()
        .fold(0, |acc, num| acc + num);

    val
}

Результат: 

println!("{}", sum_of_multiples(100, &[3, 5])) // 2633

Я знаю, что итераторы вычисляются лениво, но я предположил, что они оцениваются последовательно в порядке их использования.Это из-за поведения flatten с HashSet s?Я не понимаю, почему результаты отличаются во второй раз, или каково значение (если таковое имеется) 2633 года.

Ответы [ 2 ]

0 голосов
/ 18 сентября 2018

Вы не удалили дубликаты во втором фрагменте, потому что вы используете свой итератор напрямую.

(я знаю, что объединение HashSet s, вероятно, не лучшее решение).

Поскольку вам требуется временное хранилище для удаления дубликатов, возможно, вы могли бы использовать Vec и затем поместить его в набор, или вместо набора вы можете отсортировать Vec и отфильтровать повторяющиеся значения.самостоятельно, но это требует тестирования.

Кроме того, itertools предоставляет уникальный адаптер, который отслеживает уникальные значения внутри.- E_net4

Это тоже нужно проверить.Это позволяет вам не беспокоиться о том, как это реализовано.

Наконец, вы можете написать свою функцию в одном выражении: 

use std::collections::HashSet;

pub fn sum_of_multiples(limit: u32, factors: &[u32]) -> u32 {
    factors
        .iter()
        .flat_map(|factor| {
            let top = (limit - 1) / factor;

            (1..=top).map(move |num| num * factor)
        })
        .collect::<HashSet<u32>>()
        .iter()
        .sum()
}
0 голосов
/ 18 сентября 2018

Вы удалили промежуточное звено HashSet, которое фактически служило цели, согласно вашему первоначальному заявлению о требованиях:

дубликаты учитываются только один раз

Удаление шага сохранения значений в HashSet означает, что дубликаты будут учитываться при каждом их появлении, что должно объяснить разницу.

...