Performance issue about the Isogram problem iteration approach

herobs · January 15, 2024, 6:36am

exercism/rust/blob/80cfa6139b1d37b11f490ba416473b7ff4d3ead9/exercises/practice/isogram/.approaches/introduction.md?plain=1#L15-L29


      
          ## Approach: `filter` and `map` with `all` on a `HashSet`
          
          ```rust
          use std::collections::HashSet;
          
          pub fn check(candidate: &str) -> bool {
              let mut hs = std::collections::HashSet::new();
              candidate
                  .bytes()
                  .filter(|c| c.is_ascii_alphabetic())
                  .map(|c| c.to_ascii_lowercase())
                  .all(|c| hs.insert(c))
          ```
          
          For more information, check the [`filter` and `map` with `all` on a `HashSet` approach][approach-filter-all]

This approach will consume all items in the iterator. But once we find a duplicate letter, we can stop early and sure that the word isn’t an Isogram.

Instead, we can do it like the following, because of the laziness evaluation of iterator.

pub fn check(candidate: &str) -> bool {
    let mut seen = HashSet::<char>::new();
    candidate
        .chars()
        .filter(|&c| c.is_ascii_alphabetic())
        .filter(|&c| !seen.insert(c.to_ascii_lowercase()))
        .next()
        == None
}

Most of the community solutions don’t realized this potential problem when the inputs are huge.

IsaacG · January 15, 2024, 11:01am

Yup! Ideally that’s the sort of thing a mentor would mention during a code review and is just one reason a code review can be so beneficial! Additionally, the Dig Deeper docs, as they get built out, should contain helpful tidbits like this. Speaking of which, if it’s not yet there, this would make a great contribution to the Approaches docs! How do you feel about contributing to the track docs? Disregard

senekor · January 15, 2024, 11:28am

Iterator::all is short-circuiting

herobs · January 15, 2024, 11:51am

Yes, it’s short-circuting. My first thought when I saw the all keyword is wrong. It’s anti-intuition in some degrees.