Почему мой код для цикла медленнее, чем итератор?

Question

Я пытаюсь решить проблему с leetcode , распространять конфеты .Это легко, просто выясните минимум между видами конфет и половиной числа конфет.

Вот мое решение (стоимость 48 мс):

use std::collections::HashSet;

pub fn distribute_candies(candies: Vec<i32>) -> i32 {
    let sister_candies = (candies.len() / 2) as i32;
    let mut kind = 0;
    let mut candies_kinds = HashSet::new();
    for candy in candies.into_iter() {
        if candies_kinds.insert(candy) {
            kind += 1;
            if kind > sister_candies {
                return sister_candies;
            }
        }
    }
    kind
}

Однако я нашел решение, используяитератор:

use std::collections::HashSet;
use std::cmp::min;

pub fn distribute_candies(candies: Vec<i32>) -> i32 {
    min(candies.iter().collect::<HashSet<_>>().len(), candies.len() / 2) as i32
}

и это стоит 36 мс.

Я не могу понять, почему решение итератора быстрее, чем мое for решение с циклом.Есть ли какие-то магические оптимизации, которые Rust выполняет в фоновом режиме?

Answer 1

Основное отличие состоит в том, что версия итератора внутренне использует Iterator::size_hint, чтобы определить, сколько места нужно зарезервировать в HashSet перед тем, как собирать в него.Это предотвращает повторную перераспределение по мере роста набора.

Вы можете сделать то же самое, используя HashSet::with_capacity вместо HashSet::new:

let mut candies_kinds = HashSet::with_capacity(candies.len());

В моем тесте это единственное изменение делает ваш кодзначительно быстрее, чем итератор.Однако, если я упросту ваш код, чтобы убрать раннюю оптимизацию, он будет работать почти в то же время, что и версия итератора.

pub fn distribute_candies(candies: &[i32]) -> i32 {
    let sister_candies = (candies.len() / 2) as i32;
    let mut candies_kinds = HashSet::with_capacity(candies.len());
    for candy in candies.into_iter() {
        candies_kinds.insert(candy);
    }
    sister_candies.min(candies_kinds.len() as i32)
}

Время:

test tests::bench_iter                          ... bench:     262,315 ns/iter (+/- 23,704)
test tests::bench_loop                          ... bench:     307,697 ns/iter (+/- 16,119)
test tests::bench_loop_with_capacity            ... bench:     112,194 ns/iter (+/- 18,295)
test tests::bench_loop_with_capacity_no_bailout ... bench:     259,961 ns/iter (+/- 17,712)

Это предполагаетмне, что HashSet preallocation является доминирующей разницей.Ваша дополнительная оптимизация также оказывается очень эффективной - по крайней мере, с набором данных, который я выбрал.