performance - 为什么我的 for 循环代码比迭代器慢？

Question

我正在尝试解决 leetcode 问题 distribute-candies .很简单，只要找出糖果种类和糖果半数之间的最小值即可。

这是我的解决方案(耗时 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

主要区别在于迭代器版本internally uses 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 预分配是主要区别。您的额外优化也被证明是非常有效的 - 至少对于我碰巧选择的数据集是这样。