1
\$\begingroup\$

Continuing the Algorithm in a Nutshell series, here is the code:

trait MaxElem<T> {
    fn max_elem<'a>(&'a self) -> &'a T;
}

impl<T> MaxElem<T> for Vec<T> where T: PartialOrd {
    fn max_elem<'a>(&'a self) -> &'a T {
        max_elem_helper(self, 0, self.len())
    }
}


fn max_elem_helper<'a, T>(vec: &'a Vec<T>, left: usize, right: usize) -> &'a T 
    where T: PartialOrd
{
    if right - left == 1 {
        return &vec[left];
    }
    let mid = (left + right) / 2;
    let max1 = max_elem_helper(vec, left, mid);
    let max2 = max_elem_helper(vec, mid, right);
    if max1 > max2 {
        max1
    } else {
        max2
    }
}

#[cfg(test)]
mod test {
    use max_elem::MaxElem;
    #[test]
    fn test_max_elem() {
        let vec = vec![11, 2, 9, 1, 3, 88]; 
        let m = *vec.max_elem(); 
        assert_eq!(m, 88);
    }
}

It's a simple algorithm that divide a vector into two parts and recursively search for the maximum.

All suggestions are welcome.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Unless this was a sorted dataset, dividing and conquering to scan all N numbers shouldn't be any more efficient than just doing it the naive way and scanning all N numbers in a for loop I would think. Please correct me if I'm wrong. \$\endgroup\$
    – JPMC
    Sep 19, 2016 at 17:02
  • 1
    \$\begingroup\$ @JPMC if the data was sorted, wouldn't finding the maximum be an O(1) operation (and maybe even a single line of code?) ^_^ \$\endgroup\$
    – Shepmaster
    Sep 19, 2016 at 17:42
  • \$\begingroup\$ You're not showing it here, but I assume this is intended to run on multiple threads? \$\endgroup\$
    – notriddle
    Sep 19, 2016 at 18:15
  • \$\begingroup\$ Good point about the sorted case Shep! Though then I still do not see the advantage of this divide-and-conquer method unless @notriddle is correct about multiple threads then. And even with multithreading, this would be good for larger datasets only due to the overhead of threading outweighing the speedup on small sets. I'm trying to think of a use case for this code specifically, not that it doesn't look good or anything. \$\endgroup\$
    – JPMC
    Sep 19, 2016 at 18:51

1 Answer 1

5
\$\begingroup\$

First of all I'm not sure why you use a divide and conquer approach here, given that just walking over the entire list once and getting the maximum element is both shorter and more efficient.

Secondly I would use the more general &[T] instead of &Vec<T>.

Your implementation will recurse forever and crash with a stack overflow when the input is empty.

Because you demand PartialOrd rather than Ord, the result you get from max_elem will depend on the order of the list. For instance, a list with floating point numbers may get inconsistent results when NaN is present: if the list ends with NaN then than will be the maximum element. If it begins with NaN but also contains other numbers, then a different number will be the maximum element. It is even possible for NaN to hide the maximum number, and make the method return a number that is not the largest. A demonstration:

fn show(v: Vec<f64>) { 
    println!("Max element of {:?} is {}", v, v.max_elem());
}
show(vec![1.0, std::f64::NAN]); // the max is NaN
show(vec![std::f64::NAN, 1.0]); // the max is 1
show(vec![10000.0, std::f64::NAN, 1.0, 1.0]); // the max is 1

Basically you should just use .iter().max() when you want the maximum element of some iterable structure, which avoids all of these problems.

\$\endgroup\$
1
  • \$\begingroup\$ the more general &[T] — and potentially more performant. &[T] has one less level of indirection. \$\endgroup\$
    – Shepmaster
    Sep 19, 2016 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.