Rustでソートアルゴリズム (2)挿入ソート・シェルソート

概要

要素が少ない時はほぼ最速となる挿入ソートを実装し、その発展形であるシェルソートを実装する。

前提条件

前回と同様にRustのバージョンは1.19.0とします。

% rustc --version
rustc 1.19.0 (0ade33941 2017-07-17)

挿入ソート

Wikipediaでの説明

InsertSort

fn sort<T: PartialOrd>(source: &mut [T]) {
    for i in 1..source.len() {
        let mut j = i;
        while 0 < j && source[j - 1] > source[j] {
            source.swap(j - 1, j);
            j -= 1;
        }
    }
}

とりあえず書いて見たが、非常に遅い。
少し改善を図ってみる。

InsertSort改良

fn sort<T: PartialOrd + Clone>(source: &mut [T]) {
    for i in 1..source.len() {
        let mut j = i;
        let t = source[j].clone();
        while 0 < j && source[j - 1] > t {
            source[j] = source[j - 1].clone();
            j -= 1;
        }
        source[j] = t;
    }
}

Clone制約を要求するようになったが、倍ぐらいに高速化した。
なおrustでは、Index bounds checkが存在する為、配列アクセスの方法によってはかなり遅くなる。
Rust の Index bounds check の性能影響を調べてみた - gifnksmの雑多なメモ
今回のソースでは、範囲外アクセスは考えられないことから、Index bounds checkを外す為、unsafeを使って高速化してみる。

InsertSort改良+unsafe

fn sort<T: PartialOrd + Clone>(source: &mut [T]) {
    for i in 1..source.len() {
        let mut j = i;
        unsafe {
            let t = (*source.get_unchecked(j)).clone();
            while 0 < j && *source.get_unchecked(j - 1) > t {
                *source.get_unchecked_mut(j) = (*source.get_unchecked(j - 1)).clone();
                j -= 1;
            }
            *source.get_unchecked_mut(j) = t;
        }
    }
}

最初と比較して３倍ぐらいに高速化した。
なお、次のサイトの通り、std::ptr::copy_nonoverlappingを使うと、速度が変わらずClone制約を取り払うことができる
Rustで挿入ソート + 強制move outで高速化 - 簡潔なQ

InsertSort改良+unsafe改良版

fn sort<T: PartialOrd>(source: &mut [T]) {
    let len = source.len();
    let ptr = source.as_mut_ptr();
    for i in 1..len {
        unsafe {
            let mut j = i;
            let mut t: T = mem::uninitialized();
            ptr::copy_nonoverlapping(ptr.offset(j as isize), &mut t, 1);
            while 0 < j && *(ptr.offset((j - 1) as isize)) > t {
                ptr::copy_nonoverlapping(
                    ptr.offset((j - 1) as isize),
                    ptr.offset(j as isize),
                    1,
                );
                j -= 1;
            }
            ptr::copy_nonoverlapping(&t, ptr.offset(j as isize), 1);
            mem::forget(t);
        }
    }
}

ただ、unsafeの多用はRustの安全性を損なうこととなる為、注意が必要である。

シェルソート

挿入ソートを改良したシェルソートといったものがある。
Wikipediaでの説明

ShellSort

fn sort<T: PartialOrd + Clone>(source: &mut [T]) {
    let mut h = 1;
    while h < source.len() / 9 {
        h = h * 3 + 1;
    }

    while h > 0 {
        for i in h..source.len() {
            let mut j = i;
            let t = source[j].clone();
            while h <= j && source[j - h] > t {
                source[j] = source[j - h].clone();
                j -= h;
            }
            source[j] = t;
        }
        h /= 3;
    }
}

前回作成したコムソートより若干高速だった。