英文:
Concurrent sort
问题
我遇到了一个死锁错误，已经苦思冥想了一段时间，如果能得到帮助，将不胜感激。以下是程序应该执行的内容。我希望能够解释为什么它会出错，以及是否可以改进我的思路。
编写一个程序来对整数数组进行排序。该程序应将数组分成4个部分，每个部分由不同的goroutine进行排序。每个分区的大小应该大致相等。然后，主goroutine应将这4个排序好的子数组合并成一个大的排序数组。
程序应提示用户输入一系列整数。每个对数组进行排序的goroutine应打印它将要排序的子数组。当排序完成时，主goroutine应打印整个排序好的列表。
package main
import (
"bufio"
"fmt"
"math"
"os"
"sort"
"strconv"
"strings"
"sync"
)
func splitAndSortList(intList []int, chunkSize float64, chunkLength int, i int, wg sync.WaitGroup, c chan []int) {
listN := intList[i*chunkLength : (i*chunkLength)+chunkLength]
sort.Ints(listN)
c <- listN
fmt.Println("Sorted Chunk: n -", i, " List", listN)
wg.Done()
}
func stringToInt(strList string, chunkSize float64) []int {
var intList []int
for _, s := range strings.Fields(strList) {
i, err := strconv.Atoi(s)
if err == nil {
intList = append(intList, i)
}
}
return intList
}
func main() {
fmt.Println("Enter a sequence of integers:")
reader := bufio.NewReader(os.Stdin)
numList, _ := reader.ReadString('\n')
chunkSize := 4.0
intList := stringToInt(numList, chunkSize)
floatListLen := float64(len(intList))
chunkLength := int(math.Ceil(float64(floatListLen / chunkSize)))
c := make(chan []int, chunkLength)
semiSortedList := []int{}
var wg sync.WaitGroup
for i := 0; i < int(chunkSize); i++ {
wg.Add(1)
go splitAndSortList(intList, chunkSize, chunkLength, i, wg, c)
}
wg.Wait()
close(c)
for l := range c {
semiSortedList = append(semiSortedList, l...)
}
fmt.Println("after sort", semiSortedList)
fmt.Println("Sorting Complete")
}
英文:
I am getting a deadlock error, have been banging my head for a while, any help would be appreciated. Below is what the program should do. I am looking for an explanation on why its breaking and if I can improve on my thought process
"
Write a program to sort an array of integers. The program should partition the array into 4 parts,
each of which is sorted by a different goroutine. Each partition should be of approximately equal size. Then the main goroutine should merge the 4 sorted subarrays into one large sorted array.
The program should prompt the user to input a series of integers. Each goroutine which
sorts ¼ of the array should print the subarray that it will sort. When sorting is complete,the main goroutine should print the entire sorted list.
"
package main
import (
"bufio"
"fmt"
"math"
"os"
"sort"
"strconv"
"strings"
"sync"
)
func splitAndSortList(intList []int, chunkSize float64, chunkLength int, i int, wg sync.WaitGroup, c chan []int) {
listN := intList[i*chunkLength : (i*chunkLength)+chunkLength]
sort.Ints(listN)
c <- listN
fmt.Println("Sorted Chunk: n -", i, " List", listN)
wg.Done()
}
func stringToInt(strList string, chunkSize float64) []int {
var intList []int
for _, s := range strings.Fields(strList) {
i, err := strconv.Atoi(s)
if err == nil {
intList = append(intList, i)
}
}
return intList
}
func main() {
fmt.Println("Enter a sequence of integers: ")
reader := bufio.NewReader(os.Stdin)
numList, _ := reader.ReadString('\n')
chunkSize := 4.0
intList := stringToInt(numList, chunkSize)
floatListLen := float64(len(intList))
chunkLength := int(math.Ceil(float64(floatListLen / chunkSize)))
c := make(chan []int, chunkLength)
semiSortedList := []int{}
var wg sync.WaitGroup
for i := 0; i < int(chunkSize); i++ {
wg.Add(1)
go splitAndSortList(intList, chunkSize, chunkLength, i, wg, c)
}
wg.Wait()
close(c)
for l := range c {
semiSortedList = append(semiSortedList, l...)
}
fmt.Println("after sort", semiSortedList)
fmt.Println("Sorting Complete")
}
</details>
# 答案1
**得分**: 1
代码中有两个bug。
1. `chunkLength`小于`chunkSize`。因此，在`splitAndSortList`函数中，你将会在`c <- listN`处阻塞，并且永远不会调用`wg.Done()`。
```golang
c := make(chan []int, chunkLength)
for i := 0; i < int(chunkSize); i++ {
- 你不能通过值传递
sync.WaitGroup。因为你会得到它的一个副本，然后在副本上调用wg.Done()。原始的等待组将永远阻塞。func splitAndSortList(wg *sync.WaitGroup)
以下是修复后的代码：
package main
import (
"bufio"
"fmt"
"math"
"os"
"sort"
"strconv"
"strings"
"sync"
)
func splitAndSortList(intList []int, chunkSize float64, chunkLength int, i int, wg *sync.WaitGroup, c chan []int) {
listN := intList[i*chunkLength : (i*chunkLength)+chunkLength]
sort.Ints(listN)
c <- listN
fmt.Println("Sorted Chunk: n -", i, " List", listN)
wg.Done()
}
func stringToInt(strList string, chunkSize float64) []int {
var intList []int
for _, s := range strings.Fields(strList) {
i, err := strconv.Atoi(s)
if err == nil {
intList = append(intList, i)
}
}
return intList
}
func main() {
fmt.Println("Enter a sequence of integers:")
reader := bufio.NewReader(os.Stdin)
numList, _ := reader.ReadString('\n')
chunkSize := 4.0
intList := stringToInt(numList, chunkSize)
floatListLen := float64(len(intList))
chunkLength := int(math.Ceil(float64(floatListLen / chunkSize)))
c := make(chan []int, int(chunkSize))
semiSortedList := []int{}
var wg sync.WaitGroup
for i := 0; i < int(chunkSize); i++ {
wg.Add(1)
go splitAndSortList(intList, chunkSize, chunkLength, i, &wg, c)
}
wg.Wait()
close(c)
for l := range c {
semiSortedList = append(semiSortedList, l...)
}
fmt.Println("after sort", semiSortedList)
fmt.Println("Sorting Complete")
}
英文:
There are two bugs in the code.
- chunkLength is small than chunkSize. Therefore, you will block inside of splitAndSortList function for
c <- listN, and it will never call wg.Done().
c := make(chan []int, chunkLength)
for i := 0; i < int(chunkSize); i++ {
- You must not pass sync.WaitGroup by value. Because you will get a copy of it, and then call wg.Done() on the copy. The original wait group will block forever.
func splitAndSortList(wg *sync.WaitGroup)
Here is working code:
package main
import (
"bufio"
"fmt"
"math"
"os"
"sort"
"strconv"
"strings"
"sync"
)
func splitAndSortList(intList []int, chunkSize float64, chunkLength int, i int, wg *sync.WaitGroup, c chan []int) {
listN := intList[i*chunkLength : (i*chunkLength)+chunkLength]
sort.Ints(listN)
c <- listN
fmt.Println("Sorted Chunk: n -", i, " List", listN)
wg.Done()
}
func stringToInt(strList string, chunkSize float64) []int {
var intList []int
for _, s := range strings.Fields(strList) {
i, err := strconv.Atoi(s)
if err == nil {
intList = append(intList, i)
}
}
return intList
}
func main() {
fmt.Println("Enter a sequence of integers: ")
reader := bufio.NewReader(os.Stdin)
numList, _ := reader.ReadString('\n')
chunkSize := 4.0
intList := stringToInt(numList, chunkSize)
floatListLen := float64(len(intList))
chunkLength := int(math.Ceil(float64(floatListLen / chunkSize)))
c := make(chan []int, int(chunkSize))
semiSortedList := []int{}
var wg sync.WaitGroup
for i := 0; i < int(chunkSize); i++ {
wg.Add(1)
go splitAndSortList(intList, chunkSize, chunkLength, i, &wg, c)
}
wg.Wait()
close(c)
for l := range c {
semiSortedList = append(semiSortedList, l...)
}
fmt.Println("after sort", semiSortedList)
fmt.Println("Sorting Complete")
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论