Go问答 这个面试题的满分答案是什么?

wxjeek · 2020年03月05日 · 最后由 NSObjects 回复于 2020年04月08日 · 1103 次阅读
本帖已被设为精华帖!

10 个线程分别产生 1 个 0-100 间的随机整数,要求线程各自输出这个随机数,从持有最小数的线程开始,最后是持有最大数的线程,依次输出

稍后放出我的答案

更多原创文章干货分享,请关注公众号
  • 加微信实战群请加微信(注明:实战群):gocnio

补充几句:

  • (伪)随机数本质上没办法并发产生(具体原因涉及伪随机数生成的原理):rand.Rand 下的方法都不是并发安全的,所以 rand.Intn 里有锁,所以并发 “分别产生” 随机数是个伪问题
  • 输出到标准输出,os.Stdout.Write 里也有锁,所以并发 “各自输出” 也是伪问题
  • 按照题目要求 “分别产生” 且 “各自输出”:即不允许 goroutine 之间交流,严格来说无解(也可以理解为原题陈述要求不严谨)

放松题目要求:

  • 有效率且有实际意义的实现,要分成 master,map,reduce 三个阶段:master 统一产生随机数序列,分发到多个 map worker,做一些业务逻辑,再统一到 reduce worker 做排序。如果数量太大,可以做 sharding 分配到多个 reduce worker,结果由各个 reduce worker 分段排序
  • 不管有没有效率,允许 goroutine 之间来来回回的用 channel 通信,也可以拼凑出来一个所谓答案
  • 还有一种简单有趣的 “解法”,如下

-----之前的回复-----

没有排序,各自输出本质上不能保证顺序,可以这么玩儿出来,但是有实际意义么?这不是脑筋急转弯么?

package main

import (
    "fmt"
    "math/rand"
    "sync"
    "time"
)

func outputRand(wg *sync.WaitGroup) {
    defer wg.Done()
    i := rand.Intn(100)
    time.Sleep(time.Duration(i) * time.Millisecond)
    fmt.Println(i)
}

func main() {
    rand.Seed(time.Now().UnixNano())
    var wg sync.WaitGroup
    for i := 0; i < 10; i++ {
        wg.Add(1)
        go outputRand(&wg)
    }
    wg.Wait()
}

解完了才想起来貌似几年前见过这道题,old 。。。

h12 回复

time.sleep 不是考这个的,我这样的

package go_rand

import (
 "fmt"
 "math/rand"
 "sort"
 "sync"
 "testing"
 "time"
)

var que []rs
var wg sync.WaitGroup

func TestRand(t *testing.T) {
 c := make(chan int, 10)
 o := make(chan int, 10)
 begin := make(chan int, 10)
 que = make([]rs, 0, 10)
 wg.Add(10)
 for i := 0; i < 10; i++ {
  go genRand(i, c, o, begin)
 }
 for i := 0; i < 10; i++ {
  <-o
 }
 sort.Slice(que, func(i, j int) bool {
  return que[i].rnum < que[j].rnum
 })
 for i := 0; i < 10; i++ {
  begin <- i
 }
 wg.Wait()
}

type rs struct {
 gid  int
 rnum int
}

func genRand(gid int, c, o, begin chan int) {
 rand.Seed(time.Now().UnixNano())
 num := rand.Intn(100)
 c <- num
 o <- 1
 que = append(que, rs{gid: gid, rnum: num})
 once := sync.Once{}
 //time.Sleep(2*time.Second)
 for {
  once.Do(func() {
   <-begin
  })
  if que[0].gid == gid {
   fmt.Printf("%d,", que[0].rnum)
   que = que[1:]
   wg.Done()
   break
  }
 }
}
Mrwxj 回复

上面代码的 slice 的并发安全没考虑,for 自旋优化也没考虑

4楼 已删除
package main

import (
    "fmt"
    "math/rand"
    "runtime"
    "sort"
)

const GO_SUM = 10

type message struct {
    num int
    createNum int
    isLast bool
}

func main() {
    countCh     := make(chan struct{}, GO_SUM)
    sendCh      := make([]chan *message, GO_SUM)
    receiveCh   := make([]chan *message, GO_SUM)
    overCh      := make([]chan struct{}, GO_SUM)
    for i := 0; i < GO_SUM; i++ {
        sendCh[i] = make(chan *message, 1)
        receiveCh[i] = make(chan *message, 1)
        overCh[i] = make(chan struct{}, 1)
        go outPut(i, sendCh[i], receiveCh[i], countCh, overCh[i])
    }

    for {
        if len(countCh) == GO_SUM {
            data := make([]*message, GO_SUM)
            for i := 0; i < GO_SUM; i++{
                select {
                case tmp := <-sendCh[i]:
                    data[i] = tmp
                }
            }
            sort.Slice(data, func(i, j int) bool {
                return data[i].createNum < data[j].createNum
            })
            data[GO_SUM - 1].isLast = true
            for i := 0; i < GO_SUM; i++{
                tmp := data[i]
                receiveCh[tmp.num] <- tmp
                <-overCh[tmp.num]
            }
            for i := 0; i < GO_SUM; i++ {
                <-countCh
            }
        }
        runtime.Gosched()
    }
}

func outPut(num int, send chan *message, receive chan *message, countCh, overCh chan struct{}) {
    for {
        tmp := &message{
            num,
            rand.Intn(100) + 1,
            false,
        }
        send <- tmp
        countCh <- struct{}{}
        result := <-receive
        fmt.Print(result.createNum, " ")
        if result.isLast {
            fmt.Println()
        }
        overCh <- struct{}{}
        runtime.Gosched()
    }
}

overChan got 💯

astaxie 将本帖设为了精华贴 03月06日 22:41

我的答案:

package main

import (
    "fmt"
    "math/rand"
    "sort"
    "time"
)

type req struct {
    ch chan struct{}
    rand int
}

func main() {
    ch := make(chan *req, 10)
    for i := 0; i < 10; i++ {
        go func(ch chan<-*req){
            r := rand.Intn(100)
            rq := &req{
                ch: make(chan struct{}),
                rand: r,
            }
            ch <- rq
            <-rq.ch
            fmt.Println(r)
        }(ch)
    }

    res := make([]*req, 0, 10)
    i := 0
    for r := range ch {
        res = append(res, r)
        i++
        if i > 9 {
            break
        }
    }
    sort.SliceStable(res, func(i int, j int) bool {
        if res[i].rand < res[j].rand {
            return true
        }
        return false
    })

    for i := 0; i < 10; i++ {
        res[i].ch <- struct{}{}
        time.Sleep(1 * time.Second)
    }
}

h12 回复

你写的 “睡眠排序” 也太秀了

我的答案是:

package main

import (
    "fmt"
    "math/rand"
    "sync"
    "sync/atomic"
)

func main() {
    dones := [100][10]chan int{}

    var wg sync.WaitGroup
    var count int32
    wg.Add(10)
    for i := 0; i < 10; i++ {
        go func() {
            c := atomic.AddInt32(&count, 1)
            a := rand.Intn(100)
            dones[a][c-1] = make(chan int)
            wg.Done()
            <-dones[a][c-1]
            fmt.Println(a)
            <-dones[a][c-1]
        }()
    }
    wg.Wait()
    for i := 0; i < 100; i++ {
        for j := 0; j < 10; j++ {
            if dones[i][j] != nil {
                dones[i][j] <- 0
                dones[i][j] <- 0
            }
        }
    }

}

我这样是不是跑题了?😅

func main()  {
    rand.Seed(time.Now().Unix())
    ics := make([]chan int,0)
    nums := make([]int,0)
    for i := 0; i < 10; i++ {
        ic := make(chan int)
        ics = append(ics,ic)
        go outputRand(ic)
        r := rand.Intn(100)
        nums = append(nums,r)
    }

    sort.SliceStable(nums, func(i, j int) bool {
        return nums[i] < nums[j]
    })

    for i, value := range nums {
        ics[i] <- value
        time.Sleep(1 * time.Millisecond)
    }
}

func outputRand(wg chan int)  {
    fmt.Println(<-wg)
}
需要 登录 后方可回复, 如果你还没有账号请点击这里 注册