LoginSignup
3
1

More than 5 years have passed since last update.

@chalharu

Rustでソートアルゴリズム (4)マージソート

Last updated at Posted at 2017-07-26

概要

$O(n\log n)$で完了する安定ソートであるマージソートを実装する。
なお、マージソートにはトップダウン型とボトムアップ型の２つがあるが、両方実装してみる。

具体的なソートの方法についてはWikipedia参照

前提条件

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

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

トップダウン型マージソート

トップダウン型マージソート
fn sort<T: PartialOrd + Clone>(source: &mut [T]) {
    fn sort_inner<TInner: PartialOrd + Clone>(source: &mut [TInner], work: &mut [TInner]) {
        if source.len() > 1 {
            let mid = source.len() >> 1;
            sort_inner(&mut source[..mid], work);
            sort_inner(&mut source[mid..], work);
            work[..mid].clone_from_slice(&source[..mid]);

            let mut left_pos = 0;
            let mut right_pos = mid;
            let mut write_pos = 0;

            loop {
                if work[left_pos] <= source[right_pos] {
                    source[write_pos] = work[left_pos].clone();
                    left_pos += 1;
                    write_pos += 1;
                    if left_pos >= mid {
                        return;
                    }
                } else {
                    source[write_pos] = source[right_pos].clone();
                    right_pos += 1;
                    write_pos += 1;
                    if right_pos >= source.len() {
                        while left_pos < mid {
                            source[write_pos] = work[left_pos].clone();
                            write_pos += 1;
                            left_pos += 1;
                        }
                        return;
                    }
                }
            }
        }
    }

    // 作業メモリ確保
    let mut work = source[..(source.len() >> 1)].to_vec();
    sort_inner(source, &mut work);
}

なお、マージソートでは小さな配列に分割していくが、
要素数が少ない場合には挿入ソートの方が速い。

前々回のソースを使用して高速化してみる。

トップダウン型マージソート+挿入ソート
fn sort<T: PartialOrd + Clone>(source: &mut [T]) {
    const INSERT_THRESHOLD: usize = 32;

    fn insert_sort<TInner: PartialOrd>(source: &mut [TInner]) {
        let ptr = source.as_mut_ptr();
        for i in 1..source.len() {
            let mut j = i;
            unsafe {
                let mut t: TInner = 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);
            }
        }
    }

    fn sort_inner<TInner: PartialOrd + Clone>(source: &mut [TInner], work: &mut [TInner]) {
        if source.len() > INSERT_THRESHOLD {
            let mid = source.len() >> 1;
            sort_inner(&mut source[..mid], work);
            sort_inner(&mut source[mid..], work);
            work[..mid].clone_from_slice(&source[..mid]);

            let mut left_pos = 0;
            let mut right_pos = mid;
            let mut write_pos = 0;

            loop {
                if work[left_pos] <= source[right_pos] {
                    source[write_pos] = work[left_pos].clone();
                    left_pos += 1;
                    write_pos += 1;
                    if left_pos >= mid {
                        return;
                    }
                } else {
                    source[write_pos] = source[right_pos].clone();
                    right_pos += 1;
                    write_pos += 1;
                    if right_pos >= source.len() {
                        while left_pos < mid {
                            source[write_pos] = work[left_pos].clone();
                            write_pos += 1;
                            left_pos += 1;
                        }
                        return;
                    }
                }
            }
        } else {
            // 要素数が少なくなったら挿入ソートに移行
            insert_sort(source);
        }
    }

    let mut work = source[..(source.len() >> 1)].to_vec();
    sort_inner(source, &mut work);
}

まぁまぁ早くなったが、要素数によっては前回のヒープソートの方がまだ速い。
改善の余地がまだまだあるのだろう。

ボトムアップ型マージソート

ボトムアップ型マージソート
fn sort<T: PartialOrd + Clone>(source: &mut [T]) {
    fn sort_inner<TInner: PartialOrd + Clone>(
        work_source: &[TInner],
        work: &mut [TInner],
        size: usize,
    ) {
        let band = size << 1;
        let mut write_pos = 0;
        let b = work_source.len() - size;

        let mut j = 0;
        while j < b {
            let mid = j + size;
            let end = cmp::min(j + band, work_source.len());
            let mut left_pos = j;
            let mut right_pos = mid;

            loop {
                if work_source[left_pos] <= work_source[right_pos] {
                    work[write_pos] = work_source[left_pos].clone();
                    left_pos += 1;
                    write_pos += 1;
                    if left_pos >= mid {
                        while right_pos < end {
                            work[write_pos] = work_source[right_pos].clone();
                            write_pos += 1;
                            right_pos += 1;
                        }
                        break;
                    }
                } else {
                    work[write_pos] = work_source[right_pos].clone();
                    right_pos += 1;
                    write_pos += 1;
                    if right_pos >= end {
                        while left_pos < mid {
                            work[write_pos] = work_source[left_pos].clone();
                            write_pos += 1;
                            left_pos += 1;
                        }
                        break;
                    }
                }
            }
            j += band;
        }

        if j < work_source.len() {
            work[j..work_source.len()].clone_from_slice(&work_source[j..work_source.len()]);
        }
    }

    let mut work = source.to_vec(); // 配列の初期化
    let mut i = 1;
    loop {
        if i < source.len() {
            sort_inner(source, &mut work, i);
            i <<= 1;
        } else {
            return;
        }
        if i < source.len() {
            sort_inner(&work, source, i);
            i <<= 1;
        } else {
            source.clone_from_slice(&work);
            return;
        }
    }
}

トップダウン型と比べ、再帰呼び出しがなくなったのが大きなメリットだ。
その為、トップダウン型よりかなり速い。
このコードではメモリ確保量が倍になっているが、メモリ確保量が変わらないコードも書ける。
先程と同様に挿入ソートを利用して高速化してみる。

ボトムアップ型マージソート+挿入ソート
fn sort<T: PartialOrd + Clone>(source: &mut [T]) {
    const INSERT_THRESHOLD: usize = 32;

    fn partial_insert_sort<TInner: PartialOrd>(source: &mut [TInner], size: usize) {
        let ptr = source.as_mut_ptr();
        let mut left = 0;
        while left < source.len() {
            let right = cmp::min(left + size, source.len());
            for i in left..right {
                let mut j = i;
                unsafe {
                    let mut t: TInner = mem::uninitialized();
                    ptr::copy_nonoverlapping(ptr.offset(j as isize), &mut t, 1);
                    while left < 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);
                }
            }
            left = right;
        }
    }

    fn sort_inner<TInner: PartialOrd + Clone>(
        work_source: &[TInner],
        work: &mut [TInner],
        size: usize,
    ) {
        let band = size << 1;
        let mut write_pos = 0;
        let b = work_source.len() - size;

        let mut j = 0;
        while j < b {
            let mid = j + size;
            let end = cmp::min(j + band, work_source.len());
            let mut left_pos = j;
            let mut right_pos = mid;

            loop {
                if work_source[left_pos] <= work_source[right_pos] {
                    work[write_pos] = work_source[left_pos].clone();
                    left_pos += 1;
                    write_pos += 1;
                    if left_pos >= mid {
                        while right_pos < end {
                            work[write_pos] = work_source[right_pos].clone();
                            write_pos += 1;
                            right_pos += 1;
                        }
                        break;
                    }
                } else {
                    work[write_pos] = work_source[right_pos].clone();
                    right_pos += 1;
                    write_pos += 1;
                    if right_pos >= end {
                        while left_pos < mid {
                            work[write_pos] = work_source[left_pos].clone();
                            write_pos += 1;
                            left_pos += 1;
                        }
                        break;
                    }
                }
            }
            j += band;
        }

        if j < work_source.len() {
            work[j..work_source.len()].clone_from_slice(&work_source[j..work_source.len()]);
        }
    }

    // 初めにINSERT_THRESHOLDサイズで挿入ソートを行う
    partial_insert_sort(source, INSERT_THRESHOLD);

    if source.len() <= INSERT_THRESHOLD {
        return;
    }

    let mut work = source.to_vec(); // 配列の初期化
    let mut i = INSERT_THRESHOLD;
    loop {
        if i < source.len() {
            sort_inner(source, &mut work, i);
            i <<= 1;
        } else {
            return;
        }
        if i < source.len() {
            sort_inner(&work, source, i);
            i <<= 1;
        } else {
            source.clone_from_slice(&work);
            return;
        }
    }
}

やはりこちらも大体においてトップダウン型より速い。
が、なぜか1024要素でソートした場合にはトップダウン型に負けてしまった。

最後に全体的にunsafeを使ってみる。

ボトムアップ型マージソート+挿入ソート（unsafe）
fn sort<T: PartialOrd>(source: &mut [T]) {
    const INSERT_THRESHOLD: isize = 32;

    fn partial_insert_sort<TInner: PartialOrd>(ptr: *mut TInner, size: isize, len: isize) {
        let mut left = 0;
        while left < len {
            let right = cmp::min(left + size, len);
            for i in left..right {
                let mut j = i;
                unsafe {
                    let mut t: TInner = mem::uninitialized();
                    ptr::copy_nonoverlapping(ptr.offset(j), &mut t, 1);
                    while left < j && *(ptr.offset(j - 1)) > t {
                        ptr::copy_nonoverlapping(ptr.offset(j - 1), ptr.offset(j), 1);
                        j -= 1;
                    }
                    ptr::copy_nonoverlapping(&t, ptr.offset(j), 1);
                    mem::forget(t);
                }
            }
            left = right;
        }
    }

    fn sort_inner<TInner: PartialOrd>(
        ptr: *const TInner,
        wri_ptr: *mut TInner,
        size: isize,
        len: isize,
    ) {
        let band = size << 1;
        let mut write_pos = 0;
        let b = len - size;

        let mut j = 0;
        while j < b {
            let mid = j + size;
            let end = cmp::min(j + band, len);
            let mut left_pos = j;
            let mut right_pos = mid;

            loop {
                unsafe {
                    if *(ptr.offset(left_pos)) <= *(ptr.offset(right_pos)) {
                        ptr::copy_nonoverlapping(
                            ptr.offset(left_pos),
                            wri_ptr.offset(write_pos),
                            1,
                        );
                        left_pos += 1;
                        write_pos += 1;
                        if left_pos >= mid {
                            while right_pos < end {
                                ptr::copy_nonoverlapping(
                                    ptr.offset(right_pos),
                                    wri_ptr.offset(write_pos),
                                    1,
                                );
                                write_pos += 1;
                                right_pos += 1;
                            }
                            break;
                        }
                    } else {
                        ptr::copy_nonoverlapping(
                            ptr.offset(right_pos),
                            wri_ptr.offset(write_pos),
                            1,
                        );
                        right_pos += 1;
                        write_pos += 1;
                        if right_pos >= end {
                            while left_pos < mid {
                                ptr::copy_nonoverlapping(
                                    ptr.offset(left_pos),
                                    wri_ptr.offset(write_pos),
                                    1,
                                );
                                write_pos += 1;
                                left_pos += 1;
                            }
                            break;
                        }
                    }
                }
            }
            j += band;
        }

        if j < len {
            unsafe {
                ptr::copy_nonoverlapping(ptr.offset(j), wri_ptr.offset(j), (len - j) as usize);
            }
        }
    }


    let len = source.len() as isize;
    let src_ptr = source.as_mut_ptr();

    // 初めにINSERT_THRESHOLDサイズで挿入ソートを行う
    partial_insert_sort(src_ptr, INSERT_THRESHOLD, len);

    if len as isize <= INSERT_THRESHOLD {
        return;
    }

    let mut work = Vec::<T>::with_capacity(len as usize); // 配列の初期化
    unsafe {
        work.set_len(len as usize);
    }
    let wrk_ptr = work.as_mut_ptr();
    let mut i = INSERT_THRESHOLD;
    loop {
        if i < len {
            sort_inner(src_ptr, wrk_ptr, i, len);
            i <<= 1;
        } else {
            return;
        }
        if i < len {
            sort_inner(wrk_ptr, src_ptr, i, len);
            i <<= 1;
        } else {
            unsafe {
                ptr::copy_nonoverlapping(wrk_ptr, src_ptr, len as usize);
            }
            return;
        }
    }
}

ほぼ同じソースのはずなのにどういうわけか遅くなった。
Clone制約が外れているのがメリットである。

3
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
3
1