RUST でクイックソート 1

2022年12月26日

昨日早朝の雪に、柴犬はどうしたらいいのか困惑している様子です。

今回の概要

５か月前から勉強し始めたRUSTでクイックソートをしてみました。

Python や GO のようにはすんなりとはいきませんでした。

Shift_JISで書き込まれたCSVファイルを開きます。

そのファイルのデータを読み込みデコードします。

それをクイックソートします。

最後、Shift_JIS にエンコードして書き出しまでしたかったのですが、書き出しは次回とします。

RUSTは、他のプログラミング言語のようには習得できませんでした。残念。

cargo.toml

[dependencies]に次のことを追加します。

csv = "1.1"
encoding_rs = "0.8.29"

main.rs

メインコードです。

配列の扱い、所有権の扱いなど他のプログラミング言語とは異なりますので、かなりの量のコードを書くはめになりました。

copy

use encoding_rs::SHIFT_JIS;
use std::error::Error;
use std::fs;

fn partition<T: PartialOrd + Clone>(
        elements: &mut Vec<Vec<T>>,
        left: usize,
        right: usize,
) -> usize {
    let pivot1 = elements[right][0].clone();
    let pivot2 = elements[right][1].clone();
    let mut i = left;
    for mut j in left..right {
        if elements[j][0] < pivot1 {
            swap(elements, i, j);
            i += 1;
        } else if elements[j][0] == pivot1 {
            if elements[j][1] < pivot2 {
                swap(elements, i, j);
                i += 1;
            }
        }
    }
    swap(elements, i, right);
    return i as usize;
}

fn swap<T: PartialOrd + Clone>(
        elements: &mut Vec<Vec<T>>,
        i1: usize,
        i2: usize) {
    if i1 < i2 {
        let mut temp = elements[i2][0].clone();
        elements[i2][0] = elements[i1][0].clone();
        elements[i1][0] = temp;
        temp = elements[i2][1].clone();
        elements[i2][1] = elements[i1][1].clone();
        elements[i1][1] = temp;
    }
}

fn quicksort<T: PartialOrd + Clone>(
        elements: &mut Vec<Vec<T>>,
        left: usize,
        right: usize) {
    if left < right {
        let pivot = partition(elements, left, right);
        if pivot > 0 {
            quicksort(elements, left, pivot - 1);
        }
        quicksort(elements, pivot + 1, right);
    }
}

fn run() -> Result<(), Box<dyn Error>> {
    let path = "./input.csv";
    let buf = fs::read(path).unwrap();
    let (dec, _, _) = SHIFT_JIS.decode(&buf);
    let text = dec.into_owned();
    let lines = text.lines();

    let mut elements = Vec::new();
    for s in lines {
        let mut crec = Vec::new();
        crec.push(s.split(",").clone().nth(0));
        crec.push(s.split(",").clone().nth(1));
        elements.push(crec);
    }

    let right = elements.len();

    quicksort(&mut elements, 0, right - 1);

    for mut i in 0..50 {
        println!("{:?}/{:?}", elements[i][0], elements[i][1]);
    }

    Ok(())
}

fn main() {
    if let Err(err) = run() {
        println!("{:?}", err);
    }
}

CSVファイルは、GO、Python に使用したものと同じです。

ソートして実行してみました。ここまで20秒弱かかっています。

ちょっと、私の期待とはかけ離れた結果となりました。

これは、私の現在の知識ではどう改善したらいいのか分かりません。

補足

fn swap 関数を次のようにすると12秒まで縮小になりました。(2023年1月7日補足）


fn swap<T: PartialOrd + Clone>(
        elements: &mut Vec<Vec<T>>,
        i1: usize,
        i2: usize) {
    if i1 < i2 {
        elements.swap(i1, i2);
    }
}