从一个 Vec 到另一个 Vec 的惯用 moving/sorting 值

Question

我最近染上了锈病，来自 python 背景。我仍然掌握函数式编程的窍门，所以我正在寻找 insight/feedback 编写惯用的 rust。

在下面的示例中，我有一个 Parent 元素和 Child 元素的列表，并希望根据 [=15= 将 Child 元素分类到它们各自的父元素中].

在python中，我会嵌套两个for循环，执行测试并相应地继续。但我不太确定是否有 better/performant/idiomatic 方法可以做到这一点。

我已经标记了有问题的代码部分。尽管任何反馈都很棒！

这是一个可以使用的游乐场： https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=233cfa5b5798090fa969ba348a479b1c

#[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"]
        .iter()
        .map(|s| s.to_string())
        .map(Parent::from_id)
        .collect();

    let mut children: Vec<Child> = vec!["a", "a", "b", "c", "c", "c"]
        .iter()
        .map(|s| s.to_string())
        .map(Child::from_parent_id)
        .collect();

    // Is there a better way to do this?
    while let Some(child) = children.pop() {
        for parent in parents.iter_mut() {
            if child.parent_id == parent.id {
                parent.children.push(child);
                break;
            }
        }
    }

    dbg!(parents);
    dbg!(children);
}

Answer 1

当您需要保留部分或全部向量时，通常会使用从向量末尾弹出项目。如果需要消费整个vector，可以直接传给for循环：

for child in children {
    for parent in parents.iter_mut() {
        if child.parent_id == parent.id {
            parent.children.push(child);
            break;
        }
    }
}

您可以使用迭代器查找 parent，如下所示：

for child in children {
    parents
        .iter_mut()
        .find(|parent| parent.id == child.parent_id)
        .map(|parent| parent.children.push(child));
}

最重要的性能问题是总共需要执行 n*m 次迭代，其中 n 和 m 是 parent 的数量，children。如果这些数字可以达到数万，您最终将进行数亿次迭代，这会减慢您的速度。您可以为 parents 向量创建一个 id->position 的临时映射可以使操作 O(n + m):

let parent_pos_by_id: HashMap<_, _> = parents
    .iter()
    .enumerate()
    .map(|(idx, parent)| (parent.id.clone(), idx))
    .collect();

for child in children {
    if let Some(&parent_pos) = parent_pos_by_id.get(&child.parent_id) {
        parents[parent_pos].children.push(child);
    }
}

Answer 2

你的代码没问题。但这里有一些关于实施的替代想法。

通过实施 From 作为 .from_id() 和 .from_parent_id() 方法的替代方法，可以轻松实现从一种类型到另一种类型的转换。

impl From<&str> for Parent {
    fn from(id: &str) -> Self {
        Self { id: id.into(), children: vec![] }
    }
}

impl From<&str> for Child {
    fn from(id: &str) -> Self {
        Child { parent_id: id.into() }
    }
}

后续示例假定 From 已按上述方式实现。

为类型实现 From 可以简化从 id 向量创建 objects 的过程。不过，差异并不显着。您用于创建 Child 和 Parent objects 的代码也很好。

    let mut parents  = vec!["a", "b", "c"]
                        .into_iter().map(|id| id.into())
                        .collect::<Vec<Parent>>();

    let mut children = vec!["a", "a", "b", "c", "c", "c"]
                        .into_iter().map(|id| id.into())
                        .collect::<Vec<Child>>();

下面是通过调用 .for_each() 将 Child objects 与 Parents 匹配的更实用的方法示例 - 典型的 for 循环也一样好。

    children.into_iter().for_each(|child| {
        let cmp = |p: &Parent| p.id.cmp(&child.parent_id);

        if let Ok(idx) = parents.binary_search_by(cmp) {
            parents[idx].children.push(child); 
        }});

上述示例中的二分查找是使 children 与 parents 匹配过程更高效的一种方法，假设 Parent 按其 ID 排序。

一种更有效的方法是将 parents 放入 HashMap.

    let mut parents  = vec!["a", "b", "c"]
                        .into_iter().map(|id| (id.into(), id.into()))
                        .collect::<HashMap<String, Parent>>();

下面显示了匹配 Child objects 到 HashMap 中的 Parents 的方式类似于二进制搜索示例。

    children.into_iter().for_each(|child| { 
        if let Some(p) = parents.get_mut(&child.parent_id) {
            p.children.push(child); 
        }});

从一个 Vec 到另一个 Vec 的惯用 moving/sorting 值

Idiomatically moving/sorting values from one Vec into another

functional-programming

rust