CSV を GO でクィックソート 2

ぼくにはマイナンバーないのかな。そうだ（犬）登録番号があった。

概要

前回は、2次元の配列を1次元に変換してからソートを行なった後、1次元を2次にして出力していました。

今回は、2次元のままソートして出力できないか考えてみました。

ファイルが小さくなる原因

前回「 input.csv 」から「 output.csv 」への変換後のファイルの大きさが小さくなりましたが、その原因が分かりました。

それは、改行文字が違うことが原因のようです。

次の画像は今回のもので、左がインプット前、左がアウトプット後のファイルをメモ帳で開いたものです。

ここで、２つ画像の下のバーを見てください。

左は「Windows（CRLF）」、右は「Unix（LF）」となっています。

CRLF は2バイト、LF は1バイトですので小さくなるはずです。

今回も、「 output.csv 」が小さくなりました。

104万レコードだから104万バイト=>1000Kバイト少なくなり、計算が合います。

copy

package main

import (
    "encoding/csv"
    "log"
    "os"

    "golang.org/x/text/encoding/japanese"
    "golang.org/x/text/transform"
)

func QuickSort(elements [][]string, left int, right int) {
    if left < right {
        posi := getposi(elements, left, right)
        QuickSort(elements, left, posi-1)
        QuickSort(elements, posi+1, right)
    }
}

func getposi(elements [][]string, left int, right int) int {
    //軸を右端
    pivot := elements[right][0]
    //開始位置
    i := left
    //昇順にするため左に小さいもののエリア
    for j := left; j < right; j++ {
        //pivotより小さいものが見つかった
        if pivot > elements[j][0] {
            swap(elements[i], elements[j])
            //次の交換位置
            i += 1
        }
    }
    //pivotの位置iが定まったので交換
    swap(elements[i], elements[right])
    //位置を返す
    return i
}

func swap(element1 []string, element2 []string) {
    for i := 0; i < len(element1); i++ {
        val := element1[i]
        element1[i] = element2[i]
        element2[i] = val
    }
}

func main() {
    in, err := os.Open("./input.csv")

    if err != nil {
        log.Fatal(err)
    }
    defer in.Close()

    r := csv.NewReader(transform.NewReader(in, japanese.ShiftJIS.NewDecoder()))
    // records => [][]string
    records, err := r.ReadAll()
    if err != nil {
        log.Fatal(err)
    }

    QuickSort(records, 0, len(records)-1)

    // 書き込み先ファイル
    out, err := os.Create("./output.csv")
    if err != nil {
        log.Fatal(err)
    }
    defer out.Close()

    // 書き込み
    w := csv.NewWriter(transform.NewWriter(out, japanese.ShiftJIS.NewEncoder()))
    w.WriteAll(records)

}

複数列の条件への拡張

任意の列でソートができれば、複数列を条件にしてソートできるか試してみました。

関数 getposi（ func getposi ）を

func getposi(elements [][]string, left int, right int) int {
    //軸を右端
    pivot := elements[right][0]
    //開始位置
    i := left
    //昇順にするため左に小さいもののエリア
    for j := left; j < right; j++ {
        //pivotより小さいものが見つかった
        if pivot > elements[j][0] {
            swap(elements[i], elements[j])
            //次の交換位置
            i += 1
        }
    }
    //pivotの位置iが定まったので交換
    swap(elements[i], elements[right])
    //位置を返す
    return i
}

次のように入れ替えて実行してみました。

copy

func getposi(elements [][]string, left int, right int) int {
    //軸を右端
    pivot := elements[right][0] + elements[right][1]
    //開始位置
    i := left
    //昇順にするため左に小さいもののエリア
    for j := left; j < right; j++ {
        //pivotより小さいものが見つかった
        if pivot > (elements[j][0] + elements[j][1]) {
            swap(elements[i], elements[j])
            //次の交換位置
            i += 1
        }
    }
    //pivotの位置iが定まったので交換
    swap(elements[i], elements[right])
    //位置を返す
    return i
}

できました。

しかも、かかった時間も変わらず意図したとおりのものが出力されました。

ただただ、恐るべし GO です。

copy

package main

import (
    "encoding/csv"
    "log"
    "os"

    "golang.org/x/text/encoding/japanese"
    "golang.org/x/text/transform"
)

func QuickSort(elements [][]string, left int, right int) {
    if left < right {
        posi := getposi(elements, left, right)
        QuickSort(elements, left, posi-1)
        QuickSort(elements, posi+1, right)
    }
}

func getposi(elements [][]string, left int, right int) int {
    //軸を右端
    pivot := elements[right][0] + elements[right][1]
    //開始位置
    i := left
    //昇順にするため左に小さいもののエリア
    for j := left; j < right; j++ {
        //pivotより小さいものが見つかった
        if pivot > (elements[j][0] + elements[j][1]) {
            swap(elements[i], elements[j])
            //次の交換位置
            i += 1
        }
    }
    //pivotの位置iが定まったので交換
    swap(elements[i], elements[right])
    //位置を返す
    return i
}

func swap(element1 []string, element2 []string) {
    for i := 0; i < len(element1); i++ {
        val := element1[i]
        element1[i] = element2[i]
        element2[i] = val
    }
}

func main() {
    in, err := os.Open("./input.csv")

    if err != nil {
        log.Fatal(err)
    }
    defer in.Close()

    r := csv.NewReader(transform.NewReader(in, japanese.ShiftJIS.NewDecoder()))
    // records => [][]string
    records, err := r.ReadAll()
    if err != nil {
        log.Fatal(err)
    }

    QuickSort(records, 0, len(records)-1)

    // 書き込み先ファイル
    out, err := os.Create("./output.csv")
    if err != nil {
        log.Fatal(err)
    }
    defer out.Close()

    // 書き込み
    w := csv.NewWriter(transform.NewWriter(out, japanese.ShiftJIS.NewEncoder()))
    w.WriteAll(records)

}

ピボットを複数にして上下関係を決めれば柔軟にソートできます。

比較する関数（ getposi ）の修正を次のようして実行してみました。

ただ、ソート時間はかかるようになり、上の例ですと5秒ほど要しました。

copy

func getposi(elements [][]string, left int, right int) int {
    //軸を右端
    pivot1 := elements[right][0]
    pivot2 := elements[right][1]

    //開始位置
    i := left

    //昇順にするため左に小さいもののエリア
    for j := left; j < right; j++ {
        //pivot1より小さいものが見つかった
        if pivot1 > elements[j][0] {
            swap(elements[i], elements[j])
            //次の交換位置
            i += 1
        } else if pivot1 == elements[j][0] {
            //pivot2より小さいものが見つかった
            if pivot2 > elements[j][1] {
                swap(elements[i], elements[j])
                i += 1
            }
        }
    }

    //pivotの位置iが定まったので交換
    swap(elements[i], elements[right])

    //位置を返す
    return i

}