## 2019年9月13日金曜日

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

コード

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++ {
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
}

\$ 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

\$ go run main.go 10000000

\$ go run main.go 100000000

\$