Rust中如何高效实现Vec去重

在Rust中处理大量数据时，如何高效地对Vec进行去重操作？我了解到可以通过排序后使用dedup方法，或者用HashSet转换，但不确定哪种方式在时间和空间复杂度上更优。特别是当Vec元素较多时，是否还有其他更高性能的实现方式？希望能了解不同方法的性能对比及适用场景的建议。

2 回复

使用sort_unstable和dedup组合：

let mut vec = vec![1, 2, 2, 3];
vec.sort_unstable();
vec.dedup();

时间复杂度O(n log n)，原地操作，内存效率高。


在Rust中高效实现Vec去重，主要有以下几种方法：

1. 使用HashSet（推荐）

use std::collections::HashSet;

fn dedup<T: Eq + std::hash::Hash + Clone>(vec: &mut Vec<T>) {
    let set: HashSet<_> = vec.drain(..).collect();
    vec.extend(set.into_iter());
}

// 使用示例
let mut numbers = vec![1, 2, 2, 3, 4, 4, 5];
dedup(&mut numbers);
println!("{:?}", numbers); // [1, 2, 3, 4, 5]

优点：

  • 时间复杂度O(n)
  • 代码简洁
  • 保持任意顺序（HashSet不保证顺序，但实际测试通常保持插入顺序）

2. 保持原始顺序的HashSet方法

use std::collections::HashSet;

fn dedup_ordered<T: Eq + std::hash::Hash + Clone>(vec: &mut Vec<T>) {
    let mut set = HashSet::new();
    vec.retain(|x| set.insert(x.clone()));
}

// 使用示例
let mut numbers = vec![1, 2, 2, 3, 4, 4, 5];
dedup_ordered(&mut numbers);
println!("{:?}", numbers); // [1, 2, 3, 4, 5]

优点：

  • 保持原始顺序
  • 时间复杂度O(n)

3. 对已排序Vec使用dedup方法

let mut numbers = vec![1, 2, 2, 3, 4, 4, 5];
numbers.sort();
numbers.dedup();
println!("{:?}", numbers); // [1, 2, 3, 4, 5]

适用场景：

  • 当Vec已经排序或顺序不重要时
  • 时间复杂度O(n log n) + O(n)

性能比较

  • HashSet方法：最快，O(n)时间复杂度，推荐大多数场景使用
  • 排序+dedup：适用于需要排序或数据量较小的场景

选择哪种方法取决于是否需要保持顺序以及对性能的具体要求。

回到顶部