Сортировка слиянием в Русте


Я только начал изучать ржавчины и собрали эту работу сортировка слиянием. Интересно, что я забыл и что я мог бы улучшить.

Я не мог понять, чище способ борьбы с Option тип, возвращаемый итератор, чем просто проверить, что значения не None а потом .unwrap()Инг мои результаты, но я бы очень признателен за любые предложения.

Включенные варианты рабочих испытаний. Дайте мне знать, если есть дела, которые я пропустил.

pub fn merge_sort(mut input: Vec<usize>) -> Vec<usize> {
    let length = input.len();
    // Base case
    if length < 2 {
        return input;
    }

    let right = merge_sort(input.split_off(length / 2));
    let left = merge_sort(input);

    let mut left_iter = left.iter().peekable();
    let mut right_iter = right.iter().peekable();

    let mut merged = Vec::new();
    let mut i = 0;
    while i < length {
        if left_iter.peek() > right_iter.peek() && right_iter.peek() != None {
            merged.push(*(right_iter.next().unwrap()));
        } else if left_iter.peek() != None {
            merged.push(*(left_iter.next().unwrap()));
        }
        i += 1;
    }

    merged
}

#[cfg(test)]
mod tests {
    use merge_sort;

    #[test]
    fn it_works() {
        assert_eq!(merge_sort(vec![4, 3]), vec![3, 4]);
    }

    #[test]
    fn test_base_case() {
        assert_eq!(merge_sort(vec![3]), vec![3]);
    }

    #[test]
    fn totally_backwards() {
        assert_eq!(
            merge_sort(vec![100, 90, 50, 14, 9, 7, 3]),
            vec![3, 7, 9, 14, 50, 90, 100]
        );
    }

}


Комментарии
2 ответа

Отказ от ответственности: я новичок в Руст, но у меня есть опыт программирования на C, С++ и Haskell. Возьмите все, что я говорю с зерном соли.

Все это выглядит разумно, за исключением while петли и собственности. И есть ошибка.

Ошибка с отсортированными векторами

Вы пробовали свой код на сортированные наборы?

#[test]
fn it_works_on_sorted() {
assert_eq!(merge_sort(vec![1, 2, 3, 4]), vec![1, 2, 3, 4]);
}

Ваш код не будет работать. Вместо этого, вы будете в конечном итоге с vec![1]. Это потому, что

left_iter.peek() > right_iter.peek()

это false как только у нас кончатся элементы на левой стороне, так

None < Some(x)

это всегда справедливо для всех x. Но в данном случае мы не будем добавлять элементы с правой стороны! Вместо этого, мы смотрим на наших теперь пустой левый список:

if left_iter.peek() != None {
// left_iter.peek() is None, not executed
merged.push(*(left_iter.next().unwrap()));
}
// ALWAYS executed
i += 1;

Так i += 1 это всегда происходит, мы в конечном итоге с i == length, хотя мы никогда не pushЭд правой стороне. Так i < length скрывается ошибка. В следующем разделе показано, как избавиться от этого один:

А

Почему мы должны отслеживать длина нашего вектора? У нас есть итераторы под рукой, так что не надо, да? Когда один из наших итераторов в итоге мы наполняем наш вектор с остальными.

Это довольно легко:

while let (Some(&x), Some(&y)) = (left_iter.peek(), right_iter.peek()) {
if *x <= *y {
merged.push(*(left_iter.next().unwrap()))
} else {
merged.push(*(right_iter.next().unwrap()))
}
}

for x in left_iter {
merged.push(*x)
}

for y in right_iter {
merged.push(*y)
}

Vector::new() против Vector::with_capacity

Мы уже знаем, что merged будет length элементы, поэтому мы должны использовать Vector::with_capacity вместо:

let mut merged = Vec::with_capacity(length);

Собственности

merge_sort можно взять кусочек вместо вектора. Таким образом это более общее. Фактическая реализация остается в качестве упражнения, но это более или менее то же самое:

/// Sorts a slice in-place with mergesort.
///
/// ```
/// let mut example = [1,4,2,5,3];
///
/// merge_sort_inplace(example)
/// assert_eq!(example, [1,2,3,4,5]);
/// ```
pub fn merge_sort_inplace(input: &mut [usize]) {
let length = input.len();

if length < 2 {
return;
}

let (left, right) = input.split_at_mut(length / 2);

merge_sort_inplace(left);
merge_sort_inplace(right);

// ... similar to your variant
}

Обратите внимание, что название немного некорректно, merge_sort_inplace все равно нужно \$\mathcal \тета(Н)\$ дополнительная память , если не тянуть некоторые трюки.

Мы даже можете повторно использовать этот вариант, если вы все еще хотите взять вектор:

fn merge_sort(mut input: Vec<usize>) -> Vec<usize> {
merge_sort_inplace(&mut input);
input
}

7
ответ дан 11 марта 2018 в 10:03 Источник Поделиться

Одна очевидная вещь, которую я вижу заключается в том, что вы потребляете вход. Я предлагаю вам попробовать использовать кусочки вместо того, чтобы, так что вы не потребляют входы и вам не придется тратить время и память расщепления вектора.

4
ответ дан 11 марта 2018 в 09:03 Источник Поделиться