RUST でクイックソート 3

雪もすっかり融けて無くなって歩き易くなったと思っている柴犬です。

概要

まず UTF8 でCSVファイルを作成を試みたところ、これはソートが遅いを除き何の問題もなくできました。

次に Shift-Jis でファイルの作成を試みてみました。

しかし、100万件のファイルの作成は30分以内にはできませんでした。

1000件にデータを減らし試みたところ、すんなりと作成できました。

こんなはずはありません。少なくとも GO 並みにならないとおかしいです。

問題は、ソートと文字列の結合にあると考え今後勉強して行きたいところです。

改善ができましたら投稿します。

UTF8 でファイルを作成

UTF8 の書き出しは速いです。

出力するまでに要した時間は20秒弱と、体感的に書き出しに時間がかかったと感じられませんでした。

use encoding_rs::SHIFT_JIS;
use std::error::Error;
use std::fs;
// 追加
use csv::Writer;

// 省略

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.enumerate() {
        if s.trim().len() == 0 {
            continue; 
        }

        let fields: Vec<_> = s
            .split(",")
            .map(|field| field.trim())
            .collect();
        elements.push(fields);
    }

    let right = elements.len();
    quicksort(&mut elements, 0, right - 1);

    // 変更
    let mut wtr = Writer::from_path("./output.csv")?;
    for s in elements {
        wtr.write_record(&s)?;
    }

    Ok(())
}

// 省略

UTF8で書き出されています。

文字列「住所」が Shift-Jis だと4バイトで、UTF8 だと6バイトだから、それが100万あるから全体で2000Kバイト増える計算になります。

したがって、計算が合います。

Shift-Jis に挑戦

Shift-Jis へのエンコードに、ベクトルまたはレコードで行う方法を見つけることができなかったので、仕方なく文字列の結合を行うことにしました。

遅くなるのは予想されましたが100万行を終わられることができませんでした。

copy

use encoding_rs::SHIFT_JIS;
use std::error::Error;
use std::fs;
// 追加
use std::io::Write;

// 省略

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 (i, s) in lines.enumerate() {
        if i == 0 || s.trim().len() == 0 {
            continue; 
        }

        let fields: Vec<_> = s
            .split(",")
            .map(|field| field.trim())
            .collect();
        elements.push(fields);
    }

    let right = elements.len();
    quicksort(&mut elements, 0, right - 1);

    // 変更（文字列の結合）
    let mut ol = String::new();
    for x in elements {
        if ol.len() == 0 {
            ol = format!("{}{}{}",x[0].clone(),",", x[1].clone());
        } else {
            ol = format!("{}{}{}", ol, "\n", format!("{}{}{}",x[0].clone(),",", x[1].clone()));
        }
    }

    let (enc, _, _) = SHIFT_JIS.encode(&ol);
    let output = enc.into_owned();

    let mut file = fs::File::create("./output.csv")?;
    file.write_all(&output)?;
    file.flush()?;

    Ok(())
}

// 省略

パソコンは頑張っています。

しかし、実行から30分経過しても終わらないのでタスクを終了しました。

レコード数を減らし挑戦

1000行に減らして実行してみました。

結果は実行と同時に出力されました。100万は1000の1000倍だから30分で終わらないのはおかしいのではとも思えます。

原因は文字の結合に問題があると推測しています。文字の結合を行う度に、結合したコピーが作られるので負担が累積して増加することを考えるとこの結果も当然のことと思います。

一度に結合できたらいいのですが、何かありそうな感じもしますが見つけられませんでした。

    // 変更（文字列の結合）
    let mut ol = String::new();
    for x in elements {
        if ol.len() == 0 {
            ol = format!("{}{}{}",x[0].clone(),",", x[1].clone());
        } else {
            ol = format!("{}{}{}", ol, "\n", format!("{}{}{}",x[0].clone(),",", x[1].clone()));
        }
    }