How to write a counter function for Vec<String> in Rust? [duplicate]

Question

Function name: my_counter
Input: ['foo', 'bar', 'bar', 'bar', 'bar']]
Output: {'foo': 1, 'bar': 4}

Note: The Output type is HashMap<String, usize>, but not HashMap<&str, usize>.

Here is my implementation which I believe is a little overhead. The 'bar' has been converted to string for four times, but might not needed.

pub fn my_counter(vec: &Vec<String>) -> HashMap<String, usize> {
    let mut result: HashMap<String, usize> = HashMap::new();
    for key in vec.iter() {
        let val = result.entry(key.to_string()).or_insert(0);
        *val += 1;
    }
    result
}

Anybody would like to share a better solution? Thanks very much~

Answer 1

One thing you could do is avoid creating new Strings by consuming (or moving) the original vector's values. Like this:

pub fn my_counter(vec: Vec<String>) -> HashMap<String, usize> {
    let mut result: HashMap<String, usize> = HashMap::new();
    for key in vec {
        let val = result.entry(key).or_insert(0);
        *val += 1;
    }
    result
}

Note the changed function signature: vec is now Vec<String>, not &Vec<String>. If that, for some reason, is not acceptable, then you really can't avoid creating new String values for the HashMap's keys. Let's say N is the number of vector items and M is the number of unique vector items. If you know you are gonna have lots of duplicate values in the vector (that is, M is much smaller than N), in theory you might be able to get away with creating only M new Strings. However, Rust doesn't seem to provide stable methods to directly achieve that. If using Nightly is OK for you, maybe try raw_entry_mut().

An alternative approach might be to first create a temporary HashMap<&str, usize> and then convert it to the desired "fully owned" HashMap<String, usize>. However, it's likely that would only make things worse. It really depends on the keys you have. It is one thing to have short keys and a ratio of M:N about 0.5-1.0 and completely different if you have long keys and a ratio of, say, 0.0001.

If you have a good idea on the number of unique keys, you can definitely speed things up to some degree by simply creating the HashMap with HashMap::with_capacity(...);. Using an alternative to the default hasher could also help in theory, although I have only tried FnvHashMap and even for short String keys I couldn't get any significant speed-up.