3
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

【Go】並列実行の勉強がてらスリープソートを書いてみよう

Posted at

まえがき

ゴルーチン、まるで分らない…Fuseです
そんな悩みを解決しようと並列実行が使えそうなものを考えてはみたもののなかなか思いつかない、
そんな中、Wikipediaを漁っていたら…

バケットソートのバケツをメモリ空間の代わりに時間に置き換えたもので、もともと掲示板4chanに投稿されたアイデアである。
「全要素の最大値×スリープさせる単位時間」で実際にソートできてしまう。それが役に立つ事例は例題程度であろう。

バケットソート/スリープソートより引用

これだッ!!

というわけで作ってみました。

完成品

ソースコード

環境

・Go 1.17.5 linux/amd64
・デプロイ先兼IDE Repl.it

解説(?)

main.go
package main

import (
	"fmt"  //入出力に使う
	"sync" //非同期実行に使う
	"time" //sleepに使う
)

func main() {
	var answer []int //ソート後のスライスがここに入る
	var numbers []int
	var n int
	var wg sync.WaitGroup
	print("ソートする要素数を入力してください(整数):")
	_, err := fmt.Scan(&n) //整数の個数Nを受け取る
	checkErr(err)          //エラーチェック
	wg.Add(n)              //カウンタをN個増やす
	for i := 0; i < n; i++ {
		var num int
		fmt.Printf("%d個めの要素を入力してください(整数):", i+1)
		_, err := fmt.Scan(&num)       //整数を1つ受け取る
		numbers = append(numbers, num) //配列に追加
		checkErr(err)                  //エラーチェック

	}
	for i := 0; i < n; i++ {
		go SleepWait(numbers[i], &answer, &wg) //非同期実行
	}
	wg.Wait()                  //全部終わったら
	fmt.Printf("%d\n", answer) //答えを表示
}
func checkErr(e error) { //エラーチェック用関数
	if e != nil {
		panic(e)
	}
}
func SleepWait(n int, sl *[]int, wg *sync.WaitGroup) {
	defer wg.Done()                                 //終わったらカウンタを減らす
	time.Sleep(time.Millisecond * time.Duration(n)) //数字ミリ秒待機
	*sl = append(*sl, n)                            //答えを示すスライスにくっ付ける
}

というわけでこれがコードの全体図です。
作る中で印象に残ったポイントをいくつか解説したいと思います。

main関数

(一部抜粋)main.go
func main() {
	var answer []int //ソート後のスライスがここに入る
	var numbers []int
	var n int
	var wg sync.WaitGroup
	print("ソートする要素数を入力してください(整数):")
	_, err := fmt.Scan(&n) //整数の個数Nを受け取る
	checkErr(err)          //エラーチェック
	wg.Add(n)              //カウンタをN個増やす
	for i := 0; i < n; i++ {
		var num int
		fmt.Printf("%d個めの要素を入力してください(整数):", i+1)
		_, err := fmt.Scan(&num)       //整数を1つ受け取る
		numbers = append(numbers, num) //配列に追加
		checkErr(err)                  //エラーチェック

	}
	for i := 0; i < n; i++ {
		go SleepWait(numbers[i], &answer, &wg) //非同期実行
	}
	wg.Wait()                  //全部終わったら
	fmt.Printf("%d\n", answer) //答えを表示
}

入力値の受け取りとゴルーチンの実行で二回forを回さないと入力待ちの間に時間がたってバグります(一敗)
他に方法がある可能性もありますが、私の知識ではこれしか思いつきませんでした。
関数側の変更を元の値にも反映したいので、スライスはポインタで渡します。
また、関数の非同期実行時にはgoをつけ忘れないように気をつけましょう。(一敗)
WaitGroupのカウントに要素数を入れて待ちます。
全てのゴルーチンの実行が終わったら(WaitGroupのカウントが0になったら)、
結果を出力して終了です。

SleepWait関数

(一部抜粋)main.go
func SleepWait(n int, sl *[]int, wg *sync.WaitGroup) {
	defer wg.Done()                                 //終わったらカウンタを減らす
	time.Sleep(time.Millisecond * time.Duration(n)) //数字ミリ秒待機
	*sl = append(*sl, n)                            //答えを示すスライスにくっ付ける
}

まずはdeferで関数終了後にWaitGroupのカウントを1つ減らすようにあらかじめ定義し、
nミリ秒経ったら渡されたスライスの最後にnをくっ付けて終了します。

あとがきと感想

わかりづらく敬遠していたゴルーチンですが、これで少し理解が深まったと思いました。
こういった変なアルゴリズムはいくつかあるので、また機会があったら触ってみたいですね。

3
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?