wrongwrongな開発日記

情報系大学院生の忘備録

【Golang】簡単なQuickSortを並列化

wrongwrong163377.hatenablog.com
この記事のQuickSortのコードの門番には間違いがあるので訂正しました。

背景

wrongwrong163377.hatenablog.com
前回の記事の続きです。
記事作成時点のリポジトリは以下。
github.com

Golangの並列処理

以下の記事を参考にしました。
qiita.com
ざっくり読んだ感じだとgo func(){}()使えってことですかね。なんか.Netのtaskっぽく感じましたが勉強不足でお尻についてる()の意味とか分かってないです。
taskと比較すると、ラムダ式っぽい書き方しなくていいのが嬉しいかなと思いました。ラムダ式はパっと見書き方がぜんぜん違ったり、インデントがおかしくなりがちだったり、個人的には嫌悪感が先に来るんですよね。

ソースコード

ソースコードは以下の通りです。前回のコードから再帰呼出しをgoランタイムの中に入れて並列処理するように変更しました。

func qsort_go(arr []int) []int{
	//門番
	if len(arr) < 2{
		if len(arr) <= 1 || arr[0] <= arr[1]{
			return arr
		}else {
			return []int {arr[1], arr[0]}
		}
	}

	var piv int = arr[0]
	var small []int
	var big []int

	for i:=1;i<len(arr);i++{
		if piv > arr[i] {
			small = append(small, arr[i])
		}else {
			big = append(big, arr[i])
		}
	}

	finished := make(chan bool)
	go func(){
		small = qsort(small)
		finished <- true
	}()
	go func(){
		big = qsort(big)
		finished <- true
	}()

	// 終わるまで待つ
	<-finished
	<-finished

	return append(append(small, piv), big...)
}

比較

長さ50,000で値の範囲[0, 99]の乱数列に対して前回のqsortと今回のqsort_goの平均実行時間を簡単に比較してみました。
オプションやらは何も設定していないゆるゆる測定です。。。というか計測中CPU使用率が他プロセス含めても70%にすら達しなかったけどこれでいいんだろうか?
実行時間計測部は以下の通りです。

for i := 0; i < 100; i++{
	arr = RandomArr()

	start1 := time.Now()
	arrtemp = qsort(arr)
	end1 := time.Now()
	time1 += end1.Sub(start1).Seconds()

	start2 := time.Now()
	arrtemp = qsort_go(arr)
	end2 := time.Now()
	time2 += end2.Sub(start2).Seconds()
}

fmt.Println(time1 / 100)
fmt.Println(time2 / 100)
比較結果

平均すると並列化した方の実行時間は並列化前に比べ80%強となりました。

0.21223236900000003
0.17805255800000006