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

More than 3 years have passed since last update.


概要


お題


  • アメリカの(少し昔の)無料電話番号は『地域コード(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()関数使用)(比較用)


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)) // 処理時間 計測完了
}



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


効果測定


  • もともとの問題は 使用可能なメモリが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) と本文にあり、すべてメモリに乗る状況下でも(データの密度次第で)効果があることがわかりました。

  • ソートのルールさえあれば数値以外のアルファベットなども同じアルゴリズムでソートもできるけど、あまり現実的じゃないかなぁ。。

  • お気づきの点がありましたらお気軽にコメントください!