如何在 Golang 中并行生成组合

Question

我正在尝试使用 Golang 并行生成组合（例如，10 个数字中的每 6 个组合）。

我有一个串行运行的解决方案：Serial Code

对于项目数(n) = 3 和样本量(r) = 2 的情况，输出为：

Got  [1 2]
Got  [1 3]
Got  [2 3]

现在我尝试将其并行化，这是代码：Parallel Code。它不起作用，我不知道为什么。对于同样的问题，输出是：

Put  [3 3] into the channel.
Got  [3 3] out of the channel.
Put  [3 3] into the channel.
Got  [3 3] out of the channel.
Put  [3 3] into the channel.
Got  [3 3] out of the channel.

非常感谢任何帮助。

Answer 1

首先是数据竞争。

$ go run -race main.go
==================
WARNING: DATA RACE
Write at 0x00c0000b0018 by goroutine 11:
  main.combinationUtil()
      /home/leaf/spike/Whosebug/concomb/main.go:33 +0x11e

Previous write at 0x00c0000b0018 by goroutine 9:
  main.combinationUtil()
      /home/leaf/spike/Whosebug/concomb/main.go:33 +0x11e

Goroutine 11 (running) created at:
  main.combinationUtil()
      /home/leaf/spike/Whosebug/concomb/main.go:35 +0x211

Goroutine 9 (running) created at:
  main.combinationUtil()
      /home/leaf/spike/Whosebug/concomb/main.go:35 +0x211
==================
==================
WARNING: DATA RACE
Read at 0x00c0000b0010 by goroutine 12:
  runtime.slicecopy()
      /usr/lib/go-1.13/src/runtime/slice.go:197 +0x0
  main.combinationUtil()
      /home/leaf/spike/Whosebug/concomb/main.go:21 +0x39c

Previous write at 0x00c0000b0010 by goroutine 10:
  main.combinationUtil()
      /home/leaf/spike/Whosebug/concomb/main.go:33 +0x11e

Goroutine 12 (running) created at:
  main.combinationUtil()
      /home/leaf/spike/Whosebug/concomb/main.go:35 +0x211

Goroutine 10 (running) created at:
  main.combinationUtil()
      /home/leaf/spike/Whosebug/concomb/main.go:40 +0x2dc
==================

此数据争用是由同时写入 data 的底层数组引起的 - 这意味着 data 的底层数组（以及 data 的内容）共享于所有协程。这是不希望的。

在 Go 中，slice 的底层是一个切片 header（参见 reflect.SliceHeader），它用三个字节保存 len、cap 和 ptr 到基础数组。当您复制它时，它不会复制底层数组，而只会复制 header，因此底层数组是共享和竞争的——两者都不需要。

为避免这种情况，只需制作一份新副本即可。（使用同步技术可以避免竞争，但内容仍然是共享的）。然而，就时间和 space 而言，仅此一项就是成本计算操作。这是否值得拥有 parellel 的好处（如果有任何好处），是另一个主题，超出了这个答案的范围。

例如，

newdata := make([]int, r)
copy(newdata, data)

// current is included, put next at next location
newdata[index] = arr[i]
wg.Add(1)
go combinationUtil(ch, wg, arr, n, r, index+1, newdata, i+1)

// current is excluded, replace it with next (Note that
// i+1 is passed, but index is not changed)
wg.Add(1)
go combinationUtil(ch, wg, arr, n, r, index, newdata, i+1)

操场：https://play.golang.org/p/YebyCGapSMs

注意 1：这种简单的副本添加之所以有效，是因为递归不依赖于 data (data[index:]) 部分的更改。否则，需要有一个back-copy for newdata to data.

注2：正如我之前暗示的那样，我怀疑这种并行的效率如何。可以有其他计算并行组合的方法，它们可以更好地利用并行计算的能力，但需要完全不同的算法。但是，我不确定，所以如果有兴趣，你应该自己研究一下。

如何在 Golang 中并行生成组合

How to Generate Combinations in Parallel in Golang

parallel-processing

go

goroutine