3
\$\begingroup\$

I'm just getting into Rust, and I've decided to implement the longest increasing subsequence algorithm suggested in the related Wikipedia page. Though this program compiles and returns the expected sequence for what's passed to lis, I am wondering if more experienced Rust programmers would have written this same algorithm in a different way?

 fn lis(x: Vec<i32>)-> Vec<i32> {
    let n = x.len();
    let mut m = vec![0; n];
    let mut p = vec![0; n];
    let mut l = 0;

    for i in 0..n {
        let mut lo = 1;
        let mut hi = l;

        while lo <= hi {
            let mut mid = (lo + hi) / 2;

            if x[m[mid]] <= x[i] {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        let mut new_l = lo;
        p[i] = m[new_l - 1];
        m[new_l] = i;

        if new_l > l {
            l = new_l;
        }
    }

    let mut o = vec![0; l];
    let mut k = m[l];
    for i in (0..l).rev() {
        o[i] = x[k];
        k    = p[k];
    }

    o
}

fn main() {
    let v = vec![0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15];
    let o = lis(v);
    println!("{:?}", o);
}
\$\endgroup\$
3
\$\begingroup\$
  1. The parameter x doesn't have to be a Vec, it could be a slice instead (&[i32]). However, if you had used a non-Copy item type (i32 is Copy), then in order to return individual items from the input Vec, you'd either have to clone the items or move them out of the Vec (using remove).

  2. You've implemented binary search by hand, but the Rust standard library provides a very flexible implementation via slice::binary_search_by.

I present you my own implementation of the algorithm, based on a slightly different C++ implementation, which is why there are so many differences compared to your version. I wrote this about one year ago, but sadly, I no longer use it. Note a few things though that are not necessarily relevant to the code review:

  1. This is a very generic function: the selector parameter is used to extract a particular field from each item in the slice. I was using this function on a slice of objects and I was interested in finding increasing values of a particular field of these objects.

  2. The function returns indices into the slice, not the values themselves. I needed to know the indices of the items in the longest increasing subsequence because I had to do something else with the items that were not in the subsequence (without destroying the original sequence), and using indices was the easiest way to do that. If I wanted to return the values without consuming the original sequence, I could have returned a Vec of references to the items instead (Vec<&T>).

  3. Single letter variable names don't really help to understand the algorithm. Since I was using this algorithm for practical purposes, I took the time to understand and document it. If this is just an exercise to learn idiomatic Rust, I suppose this kind of detail doesn't matter much.

  4. I like your use of a for loop on a reversed range iterator at the end. I should have done that myself!

/// Finds one of the [longest increasing subsequences][1]
/// from the subsequence created by applying `selector` on each item in `items`.
/// The result is a vector of indices within `items`
/// corresponding to one of the longest increasing subsequences.
///
/// [1]: https://en.wikipedia.org/wiki/Longest_increasing_subsequence
pub fn lis<T, I: Ord, F: Fn(&T) -> I>(items: &[T], selector: F) -> Vec<usize> {
    // This algorithm is adapted from
    // http://www.algorithmist.com/index.php?title=Longest_Increasing_Subsequence.cpp&oldid=13595

    let mut result = Vec::new();

    // If `items` is empty, then the result is also empty.
    if items.is_empty() {
        return result;
    }

    // This vector stores, for each item,
    // the index of the largest item prior to itself that is smaller than itself.
    // We'll use this vector at the end to build the final result.
    let mut previous_chain = vec![0; items.len()];

    // Initially, we assume that the first item is part of the result.
    // We will replace this index later if that's not the case.
    result.push(0);

    for i in 1..items.len() {
        // If the next item is greater than the last item of the current longest subsequence,
        // push its index at the end of the result and continue.
        if selector(&items[*result.last().unwrap()]) < selector(&items[i]) {
            previous_chain[i] = *result.last().unwrap();
            result.push(i);
            continue;
        }

        // Perform a binary search to find the index of an item in `result` to overwrite.
        // We want to overwrite an index that refers to the smallest item that is larger than `items[i]`.
        // If there is no such item, then we do nothing.
        let comparator = |&result_index| {
            use std::cmp::Ordering;

            // We don't return Ordering::Equal when we find an equal value,
            // because we want to find the index of the first equal value.
            if selector(&items[result_index]) < selector(&items[i]) {
                Ordering::Less
            } else {
                Ordering::Greater
            }
        };

        let next_element_index = match result.binary_search_by(comparator) {
            Ok(index) | Err(index) => index,
        };

        if selector(&items[i]) < selector(&items[result[next_element_index]]) {
            if next_element_index > 0 {
                previous_chain[i] = result[next_element_index - 1];
            }

            result[next_element_index] = i;
        }
    }

    // The last item in `result` is correct,
    // but we might have started overwriting earlier items
    // with what could have been a longer subsequence.
    // Walk back `previous_chain` to restore the proper subsequence.
    let mut u = result.len();
    let mut v = *result.last().unwrap();
    while u != 0 {
        u -= 1;
        result[u] = v;
        v = previous_chain[v];
    }

    result
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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