习惯性地将值从一个Vec移动/排序到另一个Vec

Question

我最近接触了rust，来自python背景。我还没有掌握函数式编程的窍门，所以我正在寻找关于编写习惯rust的见解/反馈。

在下面的例子中，我有一个Parent元素和Child元素的列表，并希望根据id将Child元素排序到它们各自的父元素中。

在python中，我将嵌套两个for循环，执行一个测试并相应地继续。但是我不确定是否有更好的/高效的/习惯的方法来做这件事。

我已经在有问题的代码部分做了标记。尽管任何反馈都很好!这是一个工作操场:https://play.rust-lang.org/?version=stable&模式= debug&版= 2018,要点= 233 cfa5b5798090fa969ba348a479b1c

#[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的部分或全部时，通常会将项从vector的末尾弹出。如果需要使用整个vector，可以直接将其传递给for循环:

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

可以使用迭代器来查找父节点，如下所示:

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

最重要的性能问题是，这需要执行n*m迭代总数，其中n和m是父节点和子节点的数量。如果这些数字可以达到数万，您将最终进行数亿次迭代，这将减慢您的速度。您可以创建一个临时映射id->对于父向量的位置可以进行操作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的向量创建对象。不过，差别并不大。创建Child和Parent对象的代码也很好。

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对象与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); 
}});

在上面的例子中，二分查找是一种使子代与父代匹配过程更有效的方法，假设Parents按其ID顺序排列。

更有效的方法是将父类放入HashMap.

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

下面显示了Child对象与HashMap中Parents的匹配方式，与二进制搜索示例类似。

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