Idiomatically moving/sorting values from one Vec into another

user_16968574 0
Viewed 232

I recently picked up rust, coming from a python background. I'm still getting the hang of functional programming so I'm looking for insight/feedback on writing idiomatic rust.

In the example below I have a list of Parent elements and Child elements and want to sort the Child elements into their respective parents based off of an id.

In python I would nest two for loops, perform a test and continue accordingly. But I'm not quite sure if there is a better/performant/idiomatic way of doing this.

I've marked the section of the code in question. Although any feedback is great!

Here's a working playgound: 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);
}
rust functional-programming
2 Answers

Popping items off the end of the vector is mostly used when you need to retain parts or all of the vector. If you need to consume the whole vector, you can pass it to the for loop directly:

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

You can use iterators to look for the parent, like this:

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

The most important issue with performance is that this needs to perform n*m iterations in total, where n and m are number of parents and children. If those numbers can go into tens of thousands, you will end up with hundreds of millions of iterations, which will slow you down. You can create a temporary mapping of id->position for the parents vector can make the operation 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);
    }
}
user_16008980

The code you have is okay. But here are some alternative ideas on implementation.

Supporting conversion from one type to another is easy to achieve by implementing From as an alternative to the .from_id() and .from_parent_id() methods.

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() }
    }
}

The subsequent examples assume From has been implemented as above.

Having From implemented for the types can simplify creating the objects from the vector of id's. The difference isn't dramatic though. The code you have for creating the Child and Parent objects is fine too.

    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>>();

Below, is an example of a more functional way of matching the Child objects up with the Parents by invoking .for_each() - a typical for loop would be just as good.

    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); 
        }});

Binary search in the above example is one way to make the process of matching children to parents more efficient, assuming the Parents are in order by their ID's.

An even more efficient way is to put the parents into a HashMap.

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

Below shows matching Child objects to Parents in the HashMap in a way similar to the binary search example.

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