如何快速获取Rust向量中唯一元素及其计数？优化百万级低效实现

原实现的核心问题是对每个唯一元素重复遍历整个向量计数，时间复杂度为O(n²)，百万级数据量下重复遍历会导致性能急剧下降。以下是几种高效的优化方案：

1. HashMap一次遍历统计（通用最优方案） #

通过单次遍历向量，利用HashMap的entry API直接更新元素计数，时间复杂度为O(n)，适用于任意可哈希类型：

use std::collections::HashMap;

fn main() {
    let kmers: Vec<u8> = vec![64, 64, 64, 65, 65, 65];
    let mut counts = HashMap::new();

    // 仅遍历一次完成统计
    for &kmer in &kmers {
        *counts.entry(kmer).or_insert(0) += 1;
    }

    println!("{:?}", counts);
}

2. BTreeMap有序统计 #

如果需要结果按元素大小排序，可替换为BTreeMap，性能略低于HashMap但能保证有序输出：

use std::collections::BTreeMap;

fn main() {
    let kmers: Vec<u8> = vec![64, 64, 64, 65, 65, 65];
    let mut counts = BTreeMap::new();

    for &kmer in &kmers {
        *counts.entry(kmer).or_insert(0) += 1;
    }

    println!("{:?}", counts);
}

3. 数组计数（针对有限范围整数类型） #

对于u8这类取值范围固定且较小的整数，直接用数组计数是极致性能方案，无哈希开销和动态分配：

fn main() {
    let kmers: Vec<u8> = vec![64, 64, 64, 65, 65, 65];
    let mut counts = [0usize; 256];

    for &kmer in &kmers {
        counts[kmer as usize] += 1;
    }

    // 过滤掉无计数的元素，得到最终结果
    let unique_with_counts: Vec<(u8, usize)> = counts
        .into_iter()
        .enumerate()
        .filter(|&(_, count)| count > 0)
        .map(|(val, count)| (val as u8, count))
        .collect();

    println!("{:?}", unique_with_counts);
}

内容的提问来源于stack exchange，提问作者Oliver