基于golang實現(xiàn)，有非并發(fā)實現(xiàn)和并發(fā)實現(xiàn)
遞歸
全排列問題创夜，比如打印1-9的共9個字母的全排列。先輸出1仙逻，然后是2-9的全排列驰吓，輸出2涧尿，然后1-9中去除2的全排列。于是很自然想到遞歸的方法檬贰。寫出偽代碼：
permutaion(prefix, set) {
if set 為空
print prefix
for s in set:
permuetaion(prefix+s, set - s)
}
go遞歸實現(xiàn)
func permutaionImpl(prefix []byte, s []byte, cur int) {
if cur == len(s) {
fmt.Println(prefix)
return
}
for _, b := range s {
exist := false
for i := 0; i < cur; i++ {
if prefix[i] == b {
exist = true
break
}
}
if !exist {
prefix[cur] = b
permutaionImpl(prefix, s, cur+1)
}
}
}
func Permutation(s []byte) {
//前綴slice
p := make([]byte, len(s), len(s))
permutaionImpl(p, s, 0)
}
并發(fā)1
剛才實現(xiàn)的是go單線程執(zhí)行的姑廉，改成并發(fā)版本的, 參考rob pike講Go Concurrency Patterns，多個goroutine通過channel連接起來翁涤。goroutine1發(fā)送1給goroutine2, goroutine2發(fā)送12給goroutine3桥言，goroutine3發(fā)送123給goroutine4， 以此類推葵礼。
func prefixIncrement(in []byte, s []byte, next chan []byte) {
for _, c := range s {
exist := false
for _, e := range in {
if e == c {
exist = true
break
}
}
if exist {
continue
}
temp := make([]byte, 0)
temp = append(temp, in...)
temp = append(temp, c)
next <- temp
}
}
func permutaionConImpl(req chan []byte, out chan []byte, s []byte) {
go func() {
//遞歸退出條件: len(v) == len(s)-1
v, ok := <-req
if !ok {
return
}
next := out
if len(v) != len(s)-1 {
next = make(chan []byte)
permutaionConImpl(next, out, s)
}
prefixIncrement(v, s, next)
for in := range req {
prefixIncrement(in, s, next)
}
close(next)
}()
}
// PermutationConcurrency 并發(fā)計算全排列
func PermutationConcurrency(s []byte) {
req, out := make(chan []byte), make(chan []byte)
//開啟goroutine計算
permutaionConImpl(req, out, s)
over := make(chan struct{})
//要開goroutine讀取out号阿，如果放在主函數(shù)中，會導(dǎo)致死鎖鸳粉。
go func() {
for res := range out {
fmt.Println(res)
}
close(over)
}()
for _, c := range s {
sl := []byte{c}
req <- sl
}
close(req)
<-over
}
并發(fā)2
并發(fā)1中把每個排列的階段拆分到不同的goroutine扔涧， 從goroutine1開始每個goroutine越來越繁忙，最后一個goroutine要輸出n!個slice届谈，任務(wù)輕重很不均衡扰柠。于是也可以考慮讓每個goroutine做同樣的事情，比如下面的實現(xiàn)
func PermutationConcurrencyVertical(s []byte) {
var sg sync.WaitGroup
for _, c := range s {
sg.Add(1)
//要傳參數(shù)進(jìn)去疼约，避免只取到最后一個值
go func(k byte) {
p := make([]byte, len(s), len(s))
p[0] = k
permutaionImpl(p, s, 1)
defer sg.Done()
}(c)
}
sg.Wait()
}
并發(fā)3
如果能提前知道要開幾個goroutine卤档，那就可以不用遞歸的方式創(chuàng)建goroutine了，代碼邏輯會更清晰易懂程剥。
func permutaionCal(left chan []byte, right chan []byte, s []byte) {
for v := range left {
prefixIncrement(v, s, right)
}
close(right)
}
func PermutaionChain(s []byte) {
leftmost := make(chan []byte)
left := leftmost
right := leftmost
for i := 0; i < len(s)-1; i++ {
right = make(chan []byte)
go permutaionCal(left, right, s)
left = right
}
go func(c chan []byte) {
for _, v := range s {
c <- []byte{v}
}
close(c)
}(leftmost)
for v := range right {
fmt.Println(v)
}
}
對比
benchmark 4個byte的全排列：
遞歸 5000 308919 ns/op 768 B/op 24 allocs/op
并發(fā)1 5000 382600 ns/op 1774 B/op 93 allocs/op
并發(fā)3 5000 310740 ns/op 1675 B/op 92 allocs/op
benchmark 7個byte的全排列：
遞歸 20 62281150 ns/op 161372 B/op 5040 allocs/op
并發(fā)1 20 71853908 ns/op 275384 B/op 18781 allocs/op
并發(fā)3 20 84848114 ns/op 275663 B/op 18780 allocs/op
遞歸版本最快劝枣，分配內(nèi)存最少，應(yīng)為中間結(jié)果都是寫入一個前綴slice的织鲸，通過cur下標(biāo)來標(biāo)記slice的結(jié)尾舔腾。并發(fā)版本要在不同的goroutine之間傳遞slice，分配的內(nèi)存相對多一些搂擦。在這個例子中稳诚，并發(fā)沒有表現(xiàn)出比單線程更快，原因可能是每個goroutine的計算過程較短瀑踢，不能充分發(fā)揮出多核的優(yōu)勢扳还，反而將時間浪費在了goroutine之間的消息傳遞上。
