Go - 並列和とプリフィックススキャン - 並列和 - より現実的なアルゴリズム - PRAMアルゴリズム、部分和

並行コンピューティング技法
―実践マルチコア/マルチスレッドプログラミング
原著
楽天ブックス Yahoo!

開発環境

• macOS Mojave - Apple (OS)
• Emacs (Text Editor)
• Windows 10 Pro (OS)
• Visual Studio Code (Text Editor)
• Go (プログラミング言語)

並行コンピューティング技法 ―実践マルチコア/マルチスレッドプログラミング (Clay Breshears(著)、千住 治郎(翻訳)、オライリージャパン)の6章(並列和とプリフィックススキャン)、6.1(並列和)、6.1.2(より現実的なアルゴリズム)をC言語(Windowsスレッド、POSIXスレッド、Pthreadライブラリ、OpenMPライブラリ等)ではなくGo言語(go文、goroutine、channel等)で取り組んでみる。

コード

main_test.go

package main

import "testing"

var want = 55
var intSlice = []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

func TestSummationSequential(t *testing.T) {
 got := summationSequential(intSlice)
 if got != want {
  t.Errorf("summationSequential({%#v}) got %v, want %v",
   intSlice, got, want)

 }
}

func TestSummationConcurrent(t *testing.T) {
 got := summationConcurrent(intSlice)
 if got != want {
  t.Errorf("summationConcurrent({%#v}) got %v, want %v",
   intSlice, got, want)

 }
}

main.go

package main

import (
 "fmt"
 "log"
 "os"
 "runtime"
 "strconv"
 "sync"
 "time"
)

func main() {
 numSlice := []int{}
 max, err := strconv.Atoi(os.Args[1])
 if err != nil {
  log.Fatal(err)
 }
 for i := 1; i <= max; i++ {
  numSlice = append(numSlice, i)
 }
 t1 := time.Now().UnixNano()
 sum1 := summationSequential(numSlice)
 t1 = time.Now().UnixNano() - t1
 t2 := time.Now().UnixNano()
 sum2 := summationConcurrent(numSlice)
 t2 = time.Now().UnixNano() - t2
 fmt.Printf("逐次アルゴリズム: %v %vミリ秒\n", sum1, t1/int64(time.Millisecond))
 fmt.Printf("並行アルゴリズム: %v %vミリ秒\n", sum2, t2/int64(time.Millisecond))
}

func summationSequential(numSlice []int) int {
 sum := 0
 for _, x := range numSlice {
  sum += x
 }
 return sum
}

func summationConcurrent(numSlice []int) int {
 numCPU := runtime.NumCPU()
 channelInt := make(chan int, numCPU)
 lenNumSlice := len(numSlice)
 lenPartial := lenNumSlice / numCPU
 var wg sync.WaitGroup
 for i := 0; i < numCPU; i++ {
  wg.Add(1)
  go func(j int) {
   defer wg.Done()
   var end int
   if j == (numCPU - 1) {
    end = lenNumSlice
   } else {
    end = lenPartial * (j + 1)
   }
   sum := 0
   for i := lenPartial * j; i < end; i++ {
    sum += numSlice[i]
   }
   channelInt <- sum
  }(i)
 }
 sum := 0
 go func() {
  wg.Wait()
  close(channelInt)
 }()
 for i := range channelInt {
  sum += i
 }
 return sum
}

入出力結果(Bash、cmd.exe(コマンドプロンプト)、Terminal)

$ go test
# _/.../go/並行コンピューティング技法/ch6/sample1 [_/.../go/並行コンピューティング技法/ch6/sample1.test]
./main_test.go:9:9: undefined: summationSequential
./main_test.go:18:9: undefined: summationConcurrent
FAIL _/.../go/並行コンピューティング技法/ch6/sample1 [build failed]
$ go test
# _/.../go/並行コンピューティング技法/ch6/sample1 [_/.../go/並行コンピューティング技法/ch6/sample1.test]
./main_test.go:18:9: undefined: summationConcurrent
FAIL _/.../go/並行コンピューティング技法/ch6/sample1 [build failed]
$ go test
--- FAIL: TestSummationConcurrent (0.00s)
    main_test.go:20: summationConcurrent({[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}}) got 0, want 55
FAIL
exit status 1
FAIL _/.../go/並行コンピューティング技法/ch6/sample1 0.005s

$ go test
PASS
ok   _/.../go/並行コンピューティング技法/ch6/sample1 0.005s
$ go run main.go 1000000
逐次アルゴリズム: 500000500000 0ミリ秒
並行アルゴリズム: 500000500000 0ミリ秒
$ go run main.go 10000000
逐次アルゴリズム: 50000005000000 6ミリ秒
並行アルゴリズム: 50000005000000 3ミリ秒
$ go run main.go 100000000
逐次アルゴリズム: 5000000050000000 68ミリ秒
並行アルゴリズム: 5000000050000000 37ミリ秒
$