## 2019年9月26日木曜日

### Go - 並列和とセレクション - セレクション - 逐次アルゴリズム - 並行アルゴリズム - 分割、中央値、中央値の中央値、再帰関数

コード

main_test.go

```package main

import (
"testing"
)

func TestSequentialSelect(t *testing.T) {
for i := 0; i < 10; i++ {
numSlice := []int{10, 4, 0, 3, 1, 2, 9, 5, 8, 6, 7, 10}
want := i
k := i + 1
got := SequentialSelect(numSlice, k)
if got != want {
t.Errorf("SequentialSelect(%v, %v) got %v, want %v",
numSlice, k, got, want)
}
}
}

func TestConcurrentSelect(t *testing.T) {
for i := 0; i < 10; i++ {
numSlice := []int{10, 4, 0, 3, 1, 2, 9, 5, 8, 6, 7, 10}
want := i
k := i + 1
got := ConcurrentSelect(numSlice, k)
if got != want {
t.Errorf("SequentialSelect(%v, %v) got %v, want %v",
numSlice, k, got, want)
}
}
}
```

main.go

```package main

import (
"fmt"
"log"
"math/rand"
"os"
"strconv"
"sync"
"time"
)

func main() {
numSlice1 := []int{}
numSlice2 := []int{}
max, err := strconv.Atoi(os.Args[1])
if err != nil {
log.Fatal(err)
}
rand.Seed(time.Now().UTC().UnixNano())
for i := 0; i < max; i++ {
n := rand.Intn(max)
numSlice1 = append(numSlice1, n)
numSlice2 = append(numSlice2, n)
}
k := max / 2
t1 := time.Now().UnixNano()
n := SequentialSelect(numSlice1, k)
t1 = time.Now().UnixNano() - t1
fmt.Printf("逐次アルゴリズム: %vナノ秒 %v\n", t1, n)
t2 := time.Now().UnixNano()
m := ConcurrentSelect(numSlice2, k)
t2 = time.Now().UnixNano() - t2
fmt.Printf("並行アルゴリズム: %vナノ秒 %v\n", t2, m)
}

var Q int = 5

func SequentialSelect(nums []int, k int) int {
if len(nums) < Q {
return sortLessThanQ(nums, k)
}
chunkNum := len(nums)/Q + 1
medians := make([]int, chunkNum)
i := 0
for j := 0; j < len(nums)/Q; j++ {
medians[j] = sortSelect5(nums[i:], 3)
i += Q
}
lastNum := len(nums) - Q*len(nums)/Q
if lastNum != 0 {
lastQ := Q * len(nums) / Q
medians[chunkNum-1] = sortLessThanQ(nums[lastQ:], (lastNum+1)/2)
} else {
chunkNum--
medians = medians[:chunkNum]
}
median := SequentialSelect(medians, (chunkNum+1)/2)
lessEqualGreater, marks := countAndMark(nums, median)
if lessEqualGreater[0] >= k {
packSlice := pack(nums, marks, 0)
median := SequentialSelect(packSlice, k)
return median
}
if lessEqualGreater[0]+lessEqualGreater[1] >= k {
return median
}
packSlice := pack(nums, marks, 2)
median = SequentialSelect(packSlice,
k-(lessEqualGreater[0]+lessEqualGreater[1]))
return median
}
func ConcurrentSelect(nums []int, k int) int {
if len(nums) < Q {
return sortLessThanQ(nums, k)
}
chunkNum := len(nums)/Q + 1
medians := make([]int, chunkNum)
var wg sync.WaitGroup
for j := 0; j < len(nums)/Q; j++ {
go func(j int) {
defer wg.Done()
medians[j] = sortSelect5(nums[j*Q:], 3)
}(j)
}
go func() {
defer wg.Done()
lastNum := len(nums) - Q*len(nums)/Q
if lastNum != 0 {
lastQ := Q * len(nums) / Q
medians[chunkNum-1] = sortLessThanQ(nums[lastQ:], (lastNum+1)/2)
} else {
chunkNum--
medians = medians[:chunkNum]
}
}()
wg.Wait()
median := ConcurrentSelect(medians, (chunkNum+1)/2)
lessEqualGreater, marks := countAndMark(nums, median)
if lessEqualGreater[0] >= k {
packSlice := pack(nums, marks, 0)
median := ConcurrentSelect(packSlice, k)
return median
}
if lessEqualGreater[0]+lessEqualGreater[1] >= k {
return median
}
packSlice := pack(nums, marks, 2)
median = ConcurrentSelect(packSlice,
k-(lessEqualGreater[0]+lessEqualGreater[1]))
return median
}

func sortLessThanQ(nums []int, k int) int {
switch len(nums) {
case 1:
return nums[0]
case 2:
return sortSelect2(nums, k)
case 3:
return sortSelect3(nums, k)
case 4:
return sortSelect4(nums, k)
case 5:
return sortSelect5(nums, k)
default:
log.Fatal("Error")
return -1
}
}

// 冗長だけど単純なバブルソート
func swap(nums []int, i, j int) {
t := nums[i]
nums[i] = nums[j]
nums[j] = t
}
func sortSelect2(nums []int, k int) int {
if nums[0] > nums[1] {
swap(nums, 0, 1)
}
return nums[k-1]
}
func sortSelect3(nums []int, k int) int {
if nums[0] > nums[1] {
swap(nums, 0, 1)
}
if nums[1] > nums[2] {
swap(nums, 1, 2)
if nums[0] > nums[1] {
swap(nums, 0, 1)
}
}
return nums[k-1]
}
func sortSelect4(nums []int, k int) int {
if nums[0] > nums[1] {
swap(nums, 0, 1)
}
if nums[1] > nums[2] {
swap(nums, 1, 2)
if nums[0] > nums[1] {
swap(nums, 0, 1)
}
}
if nums[2] > nums[3] {
swap(nums, 2, 3)
if nums[1] > nums[2] {
swap(nums, 1, 2)
if nums[0] > nums[1] {
swap(nums, 0, 1)
}
}
}
return nums[k-1]
}
func sortSelect5(nums []int, k int) int {
if nums[0] > nums[1] {
swap(nums, 0, 1)
}
if nums[1] > nums[2] {
swap(nums, 1, 2)
if nums[0] > nums[1] {
swap(nums, 0, 1)
}
}
if nums[2] > nums[3] {
swap(nums, 2, 3)
if nums[1] > nums[2] {
swap(nums, 1, 2)
if nums[0] > nums[1] {
swap(nums, 0, 1)
}
}
}
if nums[3] > nums[4] {
swap(nums, 3, 4)
if nums[2] > nums[3] {
swap(nums, 2, 3)
if nums[1] > nums[2] {
swap(nums, 1, 2)
if nums[0] > nums[1] {
swap(nums, 0, 1)
}
}
}
}
return nums[k-1]
}

func countAndMark(nums []int, median int) ([]int, []int) {
lessEqualGreater := make([]int, 3)
marks := []int{}
for _, num := range nums {
if num < median {
lessEqualGreater[0]++
marks = append(marks, 0)
} else if num == median {
lessEqualGreater[1]++
marks = append(marks, 1)
} else {
lessEqualGreater[2]++
marks = append(marks, 2)
}
}
return lessEqualGreater, marks
}

func pack(nums []int, marks []int, scanSym int) []int {
packSlice := []int{}
for i, mark := range marks {
if mark == scanSym {
packSlice = append(packSlice, nums[i])
}
}
return packSlice
}
```

```\$ go test
PASS
ok   _/.../go/並行コンピューティング技法/ch6/main 0.005s
\$ go build main.go
\$ ./main 100

\$ ./main 10

\$ ./main 5

\$ ./main 4

\$ ./main 1

\$ ./main 10000

\$ ./main 1000000

\$
```