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

问题描述

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

I am trying to solve the leetcode problem distribute-candies. It is easy, just find out the minimum between the candies' kinds and candies half number.

这是我的解决方案(花费 48 毫秒):

Here's my solution (cost 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
}

但是，我找到了一个使用迭代器的解决方案:

However, I found a solution using an iterator:

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 毫秒.

and it costs 36ms.

我不太明白为什么迭代器解决方案比我的 for 循环解决方案快.Rust 是否在后台执行了一些神奇的优化?

I can't quite understand why the iterator solution is faster than my for loop solution. Are there some magic optimizations that Rust is performing in the background?

推荐答案

主要区别在于迭代器版本 内部使用 Iterator::size_hint 以确定在收集到 HashSet 之前要保留多少空间.这可以防止随着集合的增长而重复重新分配.

The main difference is that the iterator version internally uses Iterator::size_hint to determine how much space to reserve in the HashSet before collecting into it. This prevents repeatedly having to reallocate as the set grows.

您可以使用 HashSet::with_capacity 而不是 HashSet::new 来做同样的事情:

You can do the same using HashSet::with_capacity instead of HashSet::new:

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

在我的基准测试中，这一单一更改使您的代码比迭代器快得多.但是，如果我简化您的代码以移除早期的救助优化，它的运行时间几乎与迭代器版本完全相同.

In my benchmark this single change makes your code significantly faster than the iterator. However, if I simplify your code to remove the early bailout optimisation, it runs in almost exactly the same time as the iterator version.

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 预分配是主要区别.你的额外优化也证明是非常有效的 - 至少对于我碰巧选择的数据集.

This suggests to me that the HashSet preallocation is the dominant difference. Your additional optimisation also proves to be very effective - at least with the dataset that I happened to choose.

这篇关于为什么我的 for 循环代码比迭代器慢?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！