Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Check if Vec contains all elements from another Vec

There is a method contains that can be used to check if a particular element exists in a Vec. How to check if all elements from a Vec are contained in another Vec? Is there something more concise than iterating manually and checking all elements explicitly?

like image 435
Some Name Avatar asked Mar 02 '23 00:03

Some Name


1 Answers

You have two main choices:

  • naively check each element from one vector to see if it's in the other. This has time complexity O(n^2) but it's also very simple and has low overhead:

    assert!(b.iter().all(|item| a.contains(item)));
    
  • create a set of all of elements of one of the vectors, and then check if elements of the other are contained it it. This has O(n) time complexity, but higher overhead including an extra heap allocation:

    let a_set: HashSet<_> = a.iter().copied().collect();
    assert!(b.iter().all(|item| a_set.contains(item)));
    

Which one is "better" will depend on your requirements. If you only care about speed, the better choice will still depend on the number of elements in your vectors, so you should test both with realistic data. You could also test with a BTreeSet, which has different performance characteristics from HashSet.


Here are some rough benchmarks (source) for how the implementations vary with the size of the input. In all tests, b is half the size of a and contains a random subset of a's elements:

Size of a Vec::contains HashSet::contains BtreeSet::contains
10 14 386 327
100 1,754 3,187 5,371
1000 112,306 31,233 88,340
10000 2,821,867 254,801 728,268
100000 29,207,999 2,645,703 6,611,666

Times in nanoseconds.

The naive O(n^2) solution is fastest when the number of elements is small. The overhead of allocating a HashSet or BTreeSet is overshadowed by the impact of the number of comparisons when the size is more than about 200. BTreeSet is mostly a lot slower than HashSet, but is slightly faster when the number of elements is very small.

like image 139
Peter Hall Avatar answered Mar 04 '23 13:03

Peter Hall