package main
import ( "fmt" )
func fib(a int64) int64 { if a < 2 { return a } return fib(a-1) + fib(a-2) }
func main() {
n1 := make(chan int64)
s1 := make(chan int64)
n2 := make(chan int64)
s2 := make(chan int64)
n3 := make(chan int64)
s3 := make(chan int64)
n4 := make(chan int64)
s4 := make(chan int64)
go func() {
x := 49
n1 <- int64(x)
}()
go func() {
x := <-n1
s1 <- fib(x)
}()
go func() {
x := 49
n2 <- int64(x)
}()
go func() {
x := <-n2
s2 <- fib(x)
}()
go func() {
x := 45
n3 <- int64(x)
}()
go func() {
x := <-n3
s3 <- fib(x)
}()
go func() {
x := 45
n4 <- int64(x)
}()
go func() {
x := <-n4
s4 <- fib(x)
}()
fmt.Println("Total fib sum ", <-s1+<-s2+<-s3+<-s4) // waits all the goroutines to finish
Is there a much more simple solution ?
评论:
tiberiousr:
dlq84:Calculating fibonacci numbers is not complex, why would you need all those goroutines?
Also, you should probably use math/big because fibonacci numbers increase exponentially.
func Fibonacci() <-chan *big.Int { c := make(chan *big.Int, 1) go func() { a, b := big.NewInt(0), big.NewInt(1) for { a.Add(a, b) a, b = b, a c <- a } close(c) }() return c }
tiberiousr:true
is unecessary here,
for { }
is valid Go
Sythe2o0:Good point, I wrote that function a couple of years ago when I was first learning. I should probably refactor some of that old code...
rod1235:There are a few potential improvements.
You can use goroutines to calculate fibonacci if you want, but you don't need to send the inputs through channels.
You're using extra lines to initialize variables you don't need to-- if you write a number in Go, Go will infer its type based on its context.
You're calculating fib(45) and fib(49) twice, when you could just use the same result twice
fib(45) is part of the result of fib(49), so by calculating both separately you're using a lot of extra time for duplicate work.
As otherwise mentioned, using big ints will be needed at some point.
This code incorporates the first three of the mentioned improvements:
package main import ( "fmt" ) func fib(a int64) int64 { if a < 2 { return a } return fib(a-1) + fib(a-2) } func main() { s1 := make(chan int64) s3 := make(chan int64) go func() { s1 <- fib(49) }() go func() { s3 <- fib(45) }() fmt.Println("Total fib sum ", 2*(<-s1+<-s3)) }
For the fourth improvement, a common strategy is to use memoization when you know you're going to be calculating the same expensive operations many times:
var ( fibMemo = map[int64]int64{ 0: 0, 1: 1, } ) func fib(a int64) int64 { if _, ok := fibMemo[a]; !ok { fibMemo[a] = fib(a-1) + fib(a-2) } return fibMemo[a] }
... but you'll want to use a sync.Map or a slice with defined bounds and null values if you are going to be doing this concurrently, not that that matters anymore, as once you've calculated fib(49) you'll know fib(45).
If we benchmark these two approaches, memoization turns the problem from completely impractical to very quick:
BenchmarkFib1-8 1 53478058800 ns/op BenchmarkFib2-8 50000 27901 ns/op
I was trying to port an haskell and scala code and doing some benchmarks Thank you all for the enlightment :) Now i know how to pass the result of an external funtion to a goroutine. Thank you so much.
