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

Question

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

4

我正在尝试解决力扣问题 distribute-candies。这很简单，只需找到糖果种类和糖果数量一半之间的最小值。

以下是我的解决方案（耗时48ms）：

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 在后台执行了一些魔法优化吗？

- bayinamy

你的代码创建了一个容量为零的 HashSet，每次实际大小加倍时都必须重新分配。迭代器版本可以使用向量迭代器的大小提示来分配正确大小的 HashSet。你可以通过使用 HashSet::with_capacity(candies.len()) 而不是 HashSet::new() 来使你的代码做到同样的事情。 - Peter Hall

1

你是否考虑过先进行排序？虽然时间复杂度为O(N log N)，但可以避免完全的内存分配，可能更加友好地利用缓存，从而提高性能。一旦排序完成，简单的线性遍历数据就可以轻松地知道有多少种类。 - Matthieu M.

@MatthieuM。这可能会更快，但我不知道如何对其进行基准测试。它会改变原始数据，因此需要为bencher的每次迭代复制该数据。 - Peter Hall

@E4_net_or_something_like_that：当前的签名无论如何都会通过复制获取Vec... - Matthieu M.

没错。但是为了正确地测试它们，数据生成不应该包含在基准测试中。如果基准测试运行器上有一个前/后钩子就好了。 - Peter Hall

@MatthieuM。我制作了一个克隆每次迭代的基准测试。排序向量实际上更慢。 - Peter Hall

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Hall · Accepted Answer

主要区别在于迭代器版本内部使用 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的预分配是主要的差异。您的额外优化也被证明非常有效 - 至少在我选择的数据集中。