Go 协程相关算法题

channel 并发 goroutine 协程 算法题
golang
发布日期:   2024-01-01
更新日期:   2026-02-10
文章字数:   1.2k
阅读时长:   6 分

Go 协程相关算法题

本文汇总以 goroutine、channel、sync 为核心的协程相关算法题，包括交替打印、顺序控制、生产者消费者、并发限制、并发安全计算等典型题型与实现。

交替打印

两协程交替打印数字与字母

题目：两个 goroutine，一个打印 1,2,3,...，一个打印 A,B,C,...，最终输出 1A2B3C...。

解法一：无缓冲 channel 互斥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func AlternatePrint() {
    numCh := make(chan struct{})
    letterCh := make(chan struct{})

    go func() {
        for i := 1; i <= 26; i++ {
            <-numCh
            fmt.Print(i)
            letterCh <- struct{}{}
        }
    }()
    go func() {
        for i := 'A'; i <= 'Z'; i++ {
            <-letterCh
            fmt.Print(string(i))
            numCh <- struct{}{}
        }
    }()

    numCh <- struct{}{}  // 先让数字协程打印
    time.Sleep(time.Second)
}

解法二：sync.Cond

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func AlternatePrintCond() {
    var mu sync.Mutex
    turn := 0
    cond := sync.NewCond(&mu)

    go func() {
        for i := 1; i <= 26; i++ {
            mu.Lock()
            for turn != 0 {
                cond.Wait()
            }
            fmt.Print(i)
            turn = 1
            cond.Signal()
            mu.Unlock()
        }
    }()
    go func() {
        for i := 'A'; i <= 'Z'; i++ {
            mu.Lock()
            for turn != 1 {
                cond.Wait()
            }
            fmt.Print(string(i))
            turn = 0
            cond.Signal()
            mu.Unlock()
        }
    }()

    time.Sleep(time.Second)
}

按序打印（Print in Order）

题目：三个函数 first()、second()、third() 由不同 goroutine 调用，要求无论调用顺序如何，输出始终为 "firstsecondthird"。

解法：channel 或 sync 控制顺序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
type Foo struct {
    ch1 chan struct{}
    ch2 chan struct{}
}

func NewFoo() *Foo {
    return &Foo{
        ch1: make(chan struct{}),
        ch2: make(chan struct{}),
    }
}

func (f *Foo) First() {
    fmt.Print("first")
    f.ch1 <- struct{}{}
}

func (f *Foo) Second() {
    <-f.ch1
    fmt.Print("second")
    f.ch2 <- struct{}{}
}

func (f *Foo) Third() {
    <-f.ch2
    fmt.Print("third")
}

// 使用：多个 goroutine 可任意顺序调用 first/second/third，输出顺序固定

交替打印奇偶数

题目：两个 goroutine，一个只打印奇数，一个只打印偶数，按 1,2,3,4,… 顺序输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func PrintOddEven(n int) {
    ch := make(chan struct{})
    done := make(chan struct{})

    go func() {
        for i := 1; i <= n; i += 2 {
            <-ch
            fmt.Println(i)
            ch <- struct{}{}
        }
        done <- struct{}{}
    }()
    go func() {
        for i := 2; i <= n; i += 2 {
            <-ch
            fmt.Println(i)
            ch <- struct{}{}
        }
        done <- struct{}{}
    }()

    ch <- struct{}{}  // 先让奇数打印
    <-done
    <-done
}

生产者消费者

题目：多个生产者向队列投递任务，多个消费者从队列取任务执行；队列有界，生产者满时阻塞。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
func ProducerConsumer(producers, consumers, taskCount, queueSize int) {
    ch := make(chan int, queueSize)
    var wg sync.WaitGroup

    for i := 0; i < producers; i++ {
        wg.Add(1)
        go func(id int) {
            defer wg.Done()
            for j := 0; j < taskCount/producers; j++ {
                ch <- id*1000 + j
            }
        }(i)
    }

    go func() {
        wg.Wait()
        close(ch)
    }()

    for i := 0; i < consumers; i++ {
        go func(id int) {
            for v := range ch {
                fmt.Printf("consumer %d: %d\n", id, v)
            }
        }(i)
    }

    time.Sleep(time.Second * 2)
}

限制并发数（Worker Pool / 信号量）

题目：大量任务并发执行，但同一时刻最多 N 个在执行（限制并发数）。

解法一：带缓冲 channel 作信号量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func LimitConcurrency(tasks []func(), limit int) {
    sem := make(chan struct{}, limit)
    var wg sync.WaitGroup

    for _, t := range tasks {
        wg.Add(1)
        go func(fn func()) {
            defer wg.Done()
            sem <- struct{}{}
            defer func() { <-sem }()
            fn()
        }(t)
    }

    wg.Wait()
}

解法二：固定 worker 池

1
2
3
4
5
6
7
8
9
10
11
12
13
func WorkerPool(tasks <-chan int, numWorkers int) {
    var wg sync.WaitGroup
    for i := 0; i < numWorkers; i++ {
        wg.Add(1)
        go func() {
            defer wg.Done()
            for t := range tasks {
                fmt.Println(t)
            }
        }()
    }
    wg.Wait()
}

并发安全求和 / Map 统计

题目：将一个大数组分片，多 goroutine 分别求和，最后汇总；或多 goroutine 统计词频后合并。

分片求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
func ConcurrentSum(arr []int, numWorkers int) int {
    n := len(arr)
    if n == 0 {
        return 0
    }
    step := (n + numWorkers - 1) / numWorkers
    var wg sync.WaitGroup
    results := make(chan int, numWorkers)

    for i := 0; i < numWorkers; i++ {
        start := i * step
        end := start + step
        if end > n {
            end = n
        }
        if start >= n {
            break
        }
        wg.Add(1)
        go func(slice []int) {
            defer wg.Done()
            sum := 0
            for _, v := range slice {
                sum += v
            }
            results <- sum
        }(arr[start:end])
    }

    go func() {
        wg.Wait()
        close(results)
    }()

    total := 0
    for s := range results {
        total += s
    }
    return total
}

词频统计（map + mutex）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func ConcurrentWordCount(texts []string) map[string]int {
    var mu sync.Mutex
    count := make(map[string]int)
    var wg sync.WaitGroup

    for _, text := range texts {
        wg.Add(1)
        go func(s string) {
            defer wg.Done()
            words := strings.Fields(s)
            mu.Lock()
            for _, w := range words {
                count[w]++
            }
            mu.Unlock()
        }(text)
    }

    wg.Wait()
    return count
}

超时与多路复用

题目：调用多个服务，取最先返回的结果，或带超时。

取最快结果（竞速）

1
2
3
4
5
6
7
8
9
func FirstSuccess(services []func() string) string {
    ch := make(chan string, len(services))
    for _, fn := range services {
        go func(f func() string) {
            ch <- f()
        }(fn)
    }
    return <-ch
}

带超时的调用

1
2
3
4
5
6
7
8
9
10
11
12
13
func DoWithTimeout(fn func(), timeout time.Duration) bool {
    done := make(chan struct{})
    go func() {
        fn()
        close(done)
    }()
    select {
    case <-done:
        return true
    case <-time.After(timeout):
        return false
    }
}

读者写者（多读单写）

题目：多个 goroutine 可并发读，写时独占；读多写少场景。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
type RWMutexCounter struct {
    mu    sync.RWMutex
    value int
}

func (c *RWMutexCounter) Read() int {
    c.mu.RLock()
    defer c.mu.RUnlock()
    return c.value
}

func (c *RWMutexCounter) Write(delta int) {
    c.mu.Lock()
    defer c.mu.Unlock()
    c.value += delta
}

总结

题型 常用手段
交替打印 无缓冲 channel、sync.Cond
按序执行 channel 串联、sync 条件变量
生产者消费者 有界 channel、close 通知结束
限制并发数 带缓冲 channel 作信号量
并发安全汇总 mutex、atomic、分片后合并
超时/竞速 select + time.After、channel

掌握上述模式后，大部分协程相关算法题都可以拆解为：同步顺序（channel/cond）、并发度控制（信号量/worker pool）、共享数据保护（mutex/atomic）的组合。

文章作者: djaigo
文章链接: https://blog.djaigo.com/golang/xie-cheng-xiang-guan-suan-fa-ti.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 djaigo !
channel 并发 goroutine 协程 算法题
赏
评论
  目录