一、问题描述
超长切片,切片元素类型为int,切片中元素乱序,使用多个goroutine查找给定值是否存在,找到目标值后立即结束所有的goroutine的执行
二、解决思路
把slice分成多段,每一段起一个task goroutine进行查找,找到目标值后在全局channel中放一条消息。在main goroutine中用select阻塞读取channel中的消息,读到后调用context包的cancel方法,在所有task goroutine的context Done通道中放一条消息, task goroutine读到消息后退出。
三、算法
1、把slice分成多段,每一段的长度根据实际情况定义,比如定义为5
2、通过context.Background定义根context,通过WithCancel方法生成子context,并通过返回的cancel方法控制子context对象的销毁及goroutine的退出。
3、定义全局channel resChan 用于传输找到目标值后的消息。
4、定义查找任务task(),顺序遍历即可,找到后在resChan中放一条消息,并通过select非阻塞读取context Done通道中的消息,读到了就推出。
5、根据定义的slice长度,把slice分割成多个子slice,并为每个子slice创建一个goroutine, go task()进行查找任务
6、在main goroutine中用select阻塞读取channel中的消息,读到后调用context包的cancel方法,通知task goroutine退出
四、实现
package main import ( "fmt" "context" ) func task(datas []int, target int, ctx context.Context, resChan chan bool) { for _, data := range datas { select { case <-ctx.Done(): return default: } if data == target { resChan <- true return } } } func Solution(datas []int, target int) { ctx, cancel := context.WithCancel(context.Background()) resChan := make(chan bool) // 分段长度 segmentLen := 5 dataLen := len(datas) for i := 0; i < dataLen; i += segmentLen { end := i + segmentLen if end >= segmentLen { end = dataLen - 1 } go task(datas[i:end], target, ctx, resChan) } select { case <-resChan: ant := fmt.Sprintf("find target: %d", target) fmt.Println(ant) cancel() return } } func main() { // case1 datas := []int{1, 2, 3, 4, 5, 6, 7, 8, 3} Solution(datas, 7) // case2 TODO找不到的情况, 考虑如何退出fatal error: all goroutines are asleep - deadlock! datas2 := []int{1, 2, 3, 4, 5, 6, 7, 8, 3} Solution(datas2, 77) }
五、在线运行
1、地址
https://play.studygolang.com/p/SXggECCT3Go
参考:
掘金:理解 Go Context 机制
https://golang.org/pkg/context/
练习题-大数组并发查找问题
Github: 多协程查询切片问题