用 Go 语言实现一个多路归并的 Merge Sort：内存中有一个无序的 int64 数组，数组中有 16M 个整数，要求使用多个 goroutine 对这个无序数组进行排序，使得有元素按照从小到大的顺序排列，并且排序的性能需要比单线程 Quick Sort 快。
这道题我只能想到在子序列排序的时候加入goroutine提高并发。然后我的cpu是12线程的所以起12个goroutine去并发排序应该性能会比较高。在最后利用每个子序列最小数组成，然后将数组里最小数存入结果数组这里。就明显看出来性能差了好多。各位大佬有更好建议吗。
配上我画的渣图
```go
package main
import (
"fmt"
"math/rand"
"math"
)
var arr []int
var arrChan []chan chan int
var exp int = 12 //sort 2**exp integers using exp goroutines
func main() {
initArr(int(math.Pow(2, float64(exp))))
for i:=1; i < exp; i++ {
go work(i)
}
boot(0)
result := <- arrChan[len(arrChan)-1]
for i := range result {
fmt.Println(i)
}
}
func initArr(num int) {
arr = make([]int, num)
for i:=0; i < num; i++ {
arr[i]=rand.Intn(10000)
}
arrChan = make([]chan chan int, exp+1)
for i:=0; i < exp+1; i++{
arrChan[i] = make(chan chan int, 2)
}
}
func boot(index int) {
for i := 0; i < len(arr); i += 2 {
ch := make(chan int, int64(math.Pow(2, float64(index+1))))
arrChan[index+1] <- ch
min := i
max := i+1
if arr[min] > arr[max] {
max = i
min = i+1
}
ch <- arr[min]
ch <- arr[max]
close(ch)
}
}
func work(index int) {
//fmt.Println("work:", index)
in := arrChan[index]
for {
ch1, ok := <- in
if !ok {
close(arrChan[index+1])
break
}
ch2 := <- in
ch := make(chan int, int64(math.Pow(2, float64(index+1))))
arrChan[index+1] <- ch
var v1, v2 int
var v1min, init, v1closed, v2closed bool
for {
if !init {
init = true
v1 = <- ch1
v2 = <- ch2
if v1 < v2 {
v1min = true
}
} else {
if v1min {
v1, ok = <-ch1
if !ok {
v1closed = true
v1min = false
} else if !v2closed && v1 > v2 {
v1min = false
}
} else {
v2, ok = <- ch2
if !ok {
v2closed = true
v1min = true
} else if !v1closed && v1 < v2 {
v1min = true
}
}
}
if v1closed && v2closed {
close(ch)
break
}
if v1min {
ch <- v1
} else {
ch <- v2
}
}
}
}
```
#2
更多评论
package main
import (
"fmt"
"math/rand"
"math"
)
var arr []int
var arrChan []chan chan int
var exp int = 12 //sort 2**exp integers using exp goroutines
func main() {
initArr(int(math.Pow(2, float64(exp))))
for i:=1; i < exp; i++ {
go work(i)
}
boot(0)
result := <- arrChan[len(arrChan)-1]
for i := range result {
fmt.Println(i)
}
}
func initArr(num int) {
arr = make([]int, num)
for i:=0; i < num; i++ {
arr[i]=rand.Intn(10000)
}
arrChan = make([]chan chan int, exp+1)
for i:=0; i < exp+1; i++{
arrChan[i] = make(chan chan int, 2)
}
}
func boot(index int) {
for i := 0; i < len(arr); i += 2 {
ch := make(chan int, int64(math.Pow(2, float64(index+1))))
arrChan[index+1] <- ch
min := i
max := i+1
if arr[min] > arr[max] {
max = i
min = i+1
}
ch <- arr[min]
ch <- arr[max]
close(ch)
}
}
func work(index int) {
//fmt.Println("work:", index)
in := arrChan[index]
for {
ch1, ok := <- in
if !ok {
close(arrChan[index+1])
break
}
ch2 := <- in
ch := make(chan int, int64(math.Pow(2, float64(index+1))))
arrChan[index+1] <- ch
var v1, v2 int
var v1min, init, v1closed, v2closed bool
for {
if !init {
init = true
v1 = <- ch1
v2 = <- ch2
if v1 < v2 {
v1min = true
}
} else {
if v1min {
v1, ok = <-ch1
if !ok {
v1closed = true
v1min = false
} else if !v2closed && v1 > v2 {
v1min = false
}
} else {
v2, ok = <- ch2
if !ok {
v2closed = true
v1min = true
} else if !v1closed && v1 < v2 {
v1min = true
}
}
}
if v1closed && v2closed {
close(ch)
break
}
if v1min {
ch <- v1
} else {
ch <- v2
}
}
}
}
#1
今日阅读排行
一周阅读排行