Goでバケットソートアルゴリズム(ビット列を使用)

概要

• 『珠玉のプログラミング 本質を見抜いたアルゴリズムとデータ構造』コラム1 の擬似コードを(少しアレンジして)Goで実装してみました

お題

• アメリカの(少し昔の)無料電話番号は『地域コード(800)』+『7桁の整数』
• ソートされていないこの7桁の整数のリストを、昇順ソートして出力する

やり方

• 整数をビット列で表現することで、使うメモリ&アクセスを節約し速度を上げる戦略
• 1~9,999,999までの9,999,999個の整数を64bit環境でメモリ展開すると
  • Int配列: 約76.3MB
  • ビット列: 約1.2MB
• 「入力ファイルに整数iがあればi番目のビットを1(オン)にする」
• つまり16以下の整数で{1,2,3,5,8,13}を0111010010000100の16bit=2Byteで表現する

サンプルコード(ビット列を使用)

• バケットソートの一種（+ビット圧縮でメモリ効率化）

sample_bit.go

package main

import (
    "bufio"
    "fmt"
    "log"
    "math"
    "os"
    "strconv"
    "time"
)

// エラー共通処理
func failOnError(err error) {
    if err != nil {
        log.Fatal("Error:", err)
    }
}

// 整数をbit配列で表した場合の位置(xバイト目のy番目のbit)を返却する
func getAddress(num int) (uint, uint) {
    return uint(num / 8), uint(num % 8)
}

// ファイルから整数を読み取り、
// 入力ファイルに整数iがあればi番目のビットを1(オン)にしたByte配列を返す
func fromFile(filePath string) []byte {
    f, err := os.Open(filePath)
    failOnError(err)
    defer f.Close()

    // 最大値が判明している場合は最初からその分メモリを確保すれば良い
    // 最大値が不明な場合はいちいちメモリを確保し直す必要がある?=逆に遅くなる可能性も
    size := math.Pow10(7)/8 + 1
    lines := make([]byte, int(size))
    scanner := bufio.NewScanner(f)
    for scanner.Scan() {
        num, _ := strconv.Atoi(scanner.Text())
        index, order := getAddress(num)
        x := 1 << order
        b := lines[index]
        lines[index] = b | byte(x)
    }
    if err := scanner.Err(); err != nil {
        failOnError(err)
    }
    return lines
}

// 整数iをi番目のビットを1(オン)にすることで表現したByte配列を、
// 該当する整数に戻して出力する
func writeByteList(path string, list []byte) {
    f, err := os.OpenFile(path, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 0600)
    failOnError(err)
    defer f.Close()

    var writer *bufio.Writer
    writer = bufio.NewWriter(f)
    index := 0
    for _, b := range list {
        for order := 0; order < 8; order++ {
            x := 1 << uint(order)
            ret := b & byte(x)
            if ret > 0 {
                writer.WriteString(strconv.Itoa(index) + "\n")
            }
            index++
        }
    }
    writer.Flush()
}

func main() {
    start := time.Now() // 処理時間　計測開始
    bytes := fromFile("/var/tmp/sample.csv")
    writeByteList("/var/tmp/output2.csv", bytes)
    fmt.Println(time.Since(start)) // 処理時間　計測完了
}

サンプルコード(ふつうにsort.Sort()関数使用)(比較用)

• 標準のGoのソートは quickSort+heapSort

sample_standardsort.go

package main

import (
    "bufio"
    "fmt"
    "log"
    "os"
    "sort"
    "strconv"
    "time"
)

// エラー共通処理
func failOnError(err error) {
    if err != nil {
        log.Fatal("Error:", err)
    }
}

// ファイルから整数を読み取りint配列を返す
func fromFile(filePath string) []int {
    f, err := os.Open(filePath)
    failOnError(err)
    defer f.Close()

    lines := make([]int, 0)

    scanner := bufio.NewScanner(f)
    for scanner.Scan() {
        num, _ := strconv.Atoi(scanner.Text())
        lines = append(lines, num)
    }
    if err := scanner.Err(); err != nil {
        failOnError(err)
    }
    return lines
}

// int配列を\n区切りでファイル出力する
func writeIntList(path string, list []int) {
    f, err := os.OpenFile(path, os.O_WRONLY|os.O_CREATE|os.O_TRUNC, 0600)
    failOnError(err)
    defer f.Close()

    var writer *bufio.Writer
    writer = bufio.NewWriter(f)
    for _, v := range list {
        writer.WriteString(strconv.Itoa(v) + "\n")
    }
    writer.Flush()
}

func main() {
    start := time.Now() // 処理時間　計測開始
    lines := fromFile("/var/tmp/sample.csv")
    sort.Sort(sort.IntSlice(lines)) // Int配列の標準ソートを実施
    writeIntList("/var/tmp/output.csv", lines)
    fmt.Println(time.Since(start)) // 処理時間　計測完了
}

おまけ) テスト用の入力ファイルを作る

• 動作確認用にx~yのランダム値を出力するコードも作りました
• min-maxの範囲からn個の整数をランダム抽出する方法(ただし重複は含まない)
• (電話番号のフォーマットに則すると「1」ではなく「0000001」が正しい出力ですが、問題の本質ではないため簡略化してしまっています)

効果測定

• もともとの問題は 使用可能なメモリが1MB程度しかなく それ以上メモリを使うとディスクSwapが発生し極端に遅くなるという条件です
• が、最近はそこまでのメモリ制限も少なくなってきていると思いますので 『メモリ16GB + Swap利用なし』という前提条件ガン無視のMacBookProで計測しました
• 入力は1~9,999,999の間のランダムな整数で、1,000回試行平均です

値の範囲	値の個数	ヒット率	標準Sort関数	ビット列	標準Sortを1とした場合の比率
1~9,999,999	10,000	1/1000	6.50ms	39.91ms	6.14
1~9,999,999	100,000	1/100	101.91ms	101.48ms	0.99
1~9,999,999	1,000,000	1/10	752.73ms	533.88ms	0.70
1~9,999,999	9,999,999	1/1	6.42s	4.05s	0.63

このアルゴリズムが有用な条件

• 値が限られた範囲内にある
• 密度がそれなりに高い
• 重複がない(または、重複を無視して良い)
• 付随する情報がない (←この条件がいちばんキツイ)

　まとめ

• メモリ制限なしの状況だと、ビット列アルゴリズムだとかえって遅くなるのではと思いましたが、データの密度が上がれば速くなりました。
• "(実行時間と使用メモリのトレードオフとよく言うけれど、) 私の経験では、「使用するメモリを小さくすることで実行時間も小さくなる」ということの方が多いようです "(p.8) と本文にあり、すべてメモリに乗る状況下でも(データの密度次第で)効果があることがわかりました。
• ソートのルールさえあれば数値以外のアルファベットなども同じアルゴリズムでソートもできるけど、あまり現実的じゃないかなぁ。。
• お気づきの点がありましたらお気軽にコメントください!