Go大切片并发查找问题笔记

一、问题描述
超长切片,切片元素类型为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: 多协程查询切片问题

发表评论

电子邮件地址不会被公开。 必填项已用*标注