4

Here is an example function with the pattern I am referring to:

fn check_sub_listiness<T: PartialEq>(big_list: &[T], small_list: &[T]) -> bool {
    for poss_sublist in big_list.windows(small_list.len()) {
        if poss_sublist == small_list {
            return true;
        }
    }
    false
}

This code takes a big list and a small list and returns whether the small list is a sublist of the big list. I wrote it as part of an Exercism exercise I was doing. I find myself using this pattern alot, where I loop through some options, check for a condition, and return true if I find it or false if I make it to the end of the loop without finding what I was looking for. Is there a name for this? More importantly, is there a better more semantic way to write it (in Rust or any other language).

Benjamin Peinhardt
  • 406
  • 3
  • 13
  • Does this find the largest matching sequence between two arrays? – tadman Dec 11 '20 at 06:26
  • It takes in two slices of generic type T and searches the large slice to see if it contains a the smaller slice as a sublist. The windows method returns an iterator over "sub slices" of a given size. So ``` for sub_slice in ['h','e','y'].windows(2) { println!("{}",sub_slice); } ``` would print: ['h','e'] ['e','y'] I think. I typed this directly into comments so I have no idea if that works – Benjamin Peinhardt Dec 11 '20 at 06:35
  • 1
    There's almost certainly a more efficient way of doing this. – tadman Dec 11 '20 at 06:38
  • 1
    Haha that's why we're all here tadman – Benjamin Peinhardt Dec 11 '20 at 06:39
  • 1
    Please check https://en.wikipedia.org/wiki/String-searching_algorithm and https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm – MaxV Dec 11 '20 at 06:48
  • If you're looking for a good implementation then you may be interested in https://docs.rs/aho-corasick/0.7.15/aho_corasick/ – MaxV Dec 11 '20 at 06:51
  • I think this question is essentially a duplicate of https://stackoverflow.com/questions/47043167/does-rust-contain-a-way-to-directly-check-whether-or-not-one-vector-is-a-substr – Ivan C Dec 11 '20 at 06:53
  • 1
    So it's not the String search that concerns me. Depending on the implementation on the overloaded ==, I think this is roughly O(n), which is good for a haystack/needle problem I think. Im really wondering if there is a shorthand or more semantic way of denoting the loop { if found thing { return true } } if never found return false logic structure – Benjamin Peinhardt Dec 11 '20 at 07:02

2 Answers2

4

Iterating until success is like .find() but if you're only interested in a true/false result you can use .any(), which does exactly what you're asking for.

Tests if any element of the iterator matches a predicate.

any() takes a closure that returns true or false. It applies this closure to each element of the iterator, and if any of them return true, then so does any(). If they all return false, it returns false.

any() is short-circuiting; in other words, it will stop processing as soon as it finds a true, given that no matter what else happens, the result will also be true.

An empty iterator returns false.

So your loop can be written like this:

fn check_sub_listiness<T: PartialEq>(big_list: &[T], small_list: &[T]) -> bool {
    big_list.windows(small_list.len()).any(|poss_sublist| {
        poss_sublist == small_list
    })
}
kmdreko
  • 42,554
  • 6
  • 57
  • 106
1

The loop you provided is an instance of exhaustive search, I would probably call it that. Hence the call for a more efficient loop, but I'm also sceptical if that's possible here. If the big list is sorted, you coud work with binary search.

Roland Brand
  • 41
  • 5
  • The big list was not necessarily sorted! The context of the problem was to find a phrase within an essay I think, but this was a long time ago so it's hard to remember. – Benjamin Peinhardt Aug 14 '21 at 02:36