Rust中将Child元素从Vec按id归入对应Parent Vec的惯用实现方法

你当前的双层循环实现在数据量小的时候可以正常运行，但时间复杂度为O(M*N)（M为Parent数量，N为Child数量），数据规模上升后性能会明显下降。Rust中更符合惯用规范且性能更优的实现方式是借助哈希表建立Parent ID到Parent实例的索引，将整体时间复杂度降到O(M + N)。

优化后完整代码 #

use std::collections::HashMap;

#[derive(Debug)]
struct Parent {
    id: String,
    children: Vec<Child>,
}

impl Parent {
    pub fn from_id(id: String) -> Self {
        Self {
            id,
            children: Vec::new(),
        }
    }
}

#[derive(Debug)]
struct Child {
    parent_id: String,
}

impl Child {
    pub fn from_parent_id(parent_id: String) -> Self {
        Self { parent_id }
    }
}

fn main() {
    let mut parents: Vec<Parent> = vec!["a", "b", "c"]
        .into_iter() // 直接消费迭代器避免额外拷贝，比iter().map(to_string)更高效
        .map(|s| s.to_string())
        .map(Parent::from_id)
        .collect();

    let children: Vec<Child> = vec!["a", "a", "b", "c", "c", "c"]
        .into_iter() // 同上优化迭代器
        .map(|s| s.to_string())
        .map(Child::from_parent_id)
        .collect();

    // 构建ID到Parent可变引用的哈希索引，查找复杂度O(1)
    let mut parent_map: HashMap<&str, &mut Parent> = parents
        .iter_mut()
        .map(|parent| (parent.id.as_str(), parent))
        .collect();

    // 单次遍历Child即可完成关联，无需嵌套循环
    for child in children {
        if let Some(parent) = parent_map.get_mut(child.parent_id.as_str()) {
            parent.children.push(child);
        }
        // 若需要收集没有对应Parent的异常Child，可在此处加else分支存储
    }

    dbg!(parents);
}

其他可选优化建议 #

• 如果业务场景允许，可以用数字类型（比如u32、u64）作为ID类型，比String类型的ID内存占用更低，哈希查找速度也更快
• 如果能保证所有Child的parent_id都存在对应的Parent，可以去掉if let判断直接调用unwrap()，但生产环境建议保留判断逻辑避免异常输入导致程序panic
• 原来的pop()处理Child会倒序插入子元素列表，如果对Child的顺序有要求，直接正向迭代Child向量得到的顺序和你原始构造的顺序一致

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