Алгоритм наибольшей возрастающей подпоследовательности


Я просто попасть в Руст, и я решил реализовать самую длинную возрастающую подпоследовательность алгоритм, предложенный в соответствующем разделе Википедии. Хотя эта программа компилирует и возвращает ожидаемый последовательности для того, что передается lisЯ интересно, если более опытные ржавчины программистов написал бы этот же алгоритм по-другому?

 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);
}


155
3
задан 11 февраля 2018 в 09:02 Источник Поделиться
Комментарии
1 ответ


  1. Параметр x не должно быть Vecэто может быть кусочек вместо (&[i32]). Однако, если вы использовали неCopy тип элемента (i32 это Copy), то для того, чтобы возвратить отдельные элементы из входного Vecнужно обязательно clone предметы или перемещать их из Vec (используя remove).

  2. Вы реализовали двоичный поиск вручную, но ржавчина стандартная библиотека обеспечивает очень гибкую реализацию через slice::binary_search_by.

Представляю вам свою собственную реализацию алгоритма, основанных на слегка разные реализации на C++ , который является, почему существует так много различий по сравнению с вашей версией. Я писал это около года назад, но, к сожалению, я больше не использовать его. Отмечу несколько вещей, хотя это не обязательно отношение к рассмотрению код:


  1. Это самая обычная функция: selector параметр используется для извлечения конкретного поля от каждого элемента в срезе. Я использовал эту функцию на кусочек объектов, и я был заинтересован в поиске увеличения значений определенного поля этих объектов.

  2. Функция возвращает показатели на срез, а не сами значения. Мне нужно было узнать индексы элементов в самой длинной возрастающей подпоследовательности, потому что я должен был сделать что-то еще с тем, что не были в подпоследовательности (без разрушения исходной последовательности), и с помощью индексов был самый простой способ сделать это. Если бы я захотел вернуть ценности, не потребляя первоначальной последовательности, я бы вернул Vec ссылок на предметы вместо (Vec<&T>).

  3. Одной переменной букву имена не помогают понять алгоритм. Поскольку я использовал этот алгоритм для практических целей, я взял время, чтобы понять и задокументировать его. Если это просто упражнение, чтобы узнать идиоматических ржавчины, я думаю, такая деталь не имеет большого значения.

  4. Мне нравится ваше использование for петли на обратной диапазона итераторов в конце. Я должен был сделать это сам!

/// 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
}

3
ответ дан 11 февраля 2018 в 10:02 Источник Поделиться