Is this the correct way to to calculate the final result ?

blov · 2017-06-08 03:00:09 · 798 次点击    
这是一个分享于 2017-06-08 03:00:09 的资源,其中的信息可能已经有所发展或是发生改变。

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:

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
}
dlq84:

true

is unecessary here,

    for { }

is valid Go

tiberiousr:

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...

Sythe2o0:

There are a few potential improvements.

  1. You can use goroutines to calculate fibonacci if you want, but you don't need to send the inputs through channels.

  2. 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.

  3. You're calculating fib(45) and fib(49) twice, when you could just use the same result twice

  4. 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.

  5. 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
rod1235:

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.


入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

798 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传