N-е число Фибоначчи в Go с использованием рекурсии и параллелизма - PullRequest
Новая
       29

N-е число Фибоначчи в Go с использованием рекурсии и параллелизма

0 голосов
/ 05 ноября 2018

Java-код, который я пытаюсь перевести. Я пытался реализовать этот Java-метод получения n-го числа Фибоначчи в Go , но я не могу получить мой код за номером 35 Фибоначчи, прежде чем он падает. Этот метод должен быть очень неэффективным, но не настолько неэффективным, что он не завершится. 

package main

import (
    "fmt"
    "time"
)

type Fibonacci struct {
    num    float64
    answer float64
}

func newFibonacci(n float64) *Fibonacci {

    f := new(Fibonacci)
    f.num = n
    c1 := make(chan float64)
    c2 := make(chan float64)

    if f.num <= 1 {
        f.answer = n
    } else {
        go func() {
            fib1 := newFibonacci(n - 1)
            c2 <- fib1.answer
        }()
        go func() {
            fib2 := newFibonacci(n - 2)
            c1 <- fib2.answer   
        }()

        f.answer = <-c2 + <-c1
    }
    close(c1)
    close(c2)

    return f
}

func main() {

    numbers := []float64{30, 35, 36, 37, 38, 39, 40}
    for _, value := range numbers{
        start := time.Now()
        fmt.Println("getting the ", value, " fibonacci number")
        f := newFibonacci(value)
        fmt.Println(f.answer)
        end := time.Now()
        totalTime := end.Sub(start)
        fmt.Println("Fibonacci number: ", value, " took ", totalTime, "\n")
    }

}

Ответы [ 2 ]

0 голосов
/ 05 ноября 2018

Ваша программа создает экспоненциальное количество подпрограмм го. Это связано с задержкой переключения контекста. Попробуйте запустить его для ограниченного числа подпрограмм го. Посмотрите следующий код, где я запускаю его для ограниченного числа подпрограмм го: 

package main

import (
    "fmt"
    "time"
)

type Fibonacci struct {
    num    float64
    answer float64
}

type goRoutineManager struct {
    goRoutineCnt chan bool
}

func (g *goRoutineManager) Run(f func()) {
    select {
    case g.goRoutineCnt <- true:
        go func() {
            f()
            <-g.goRoutineCnt
        }()
    default:
        f()
    }
}

func NewGoRoutineManager(goRoutineLimit int) *goRoutineManager {
    return &goRoutineManager{
        goRoutineCnt: make(chan bool, goRoutineLimit),
    }
}

func newFibonacci(n float64, gm *goRoutineManager) *Fibonacci {

    f := new(Fibonacci)
    f.num = n
    c1 := make(chan float64, 1)
    c2 := make(chan float64, 1)

    if f.num <= 1 {
        f.answer = n
    } else {

        gm.Run(func() {
            fib1 := newFibonacci(n-1, gm)
            c2 <- fib1.answer
        })

        gm.Run(func() {
            fib2 := newFibonacci(n-2, gm)
            c1 <- fib2.answer
        })

        f.answer = <-c2 + <-c1
    }
    close(c1)
    close(c2)

    return f
}

func main() {

    numbers := []float64{30, 35, 36, 37, 38, 39, 40} //{30, 35, 36, 37, 38, 39, 40}
    for _, value := range numbers {
        start := time.Now()
        fmt.Println("getting the ", value, " fibonacci number")

        gm := NewGoRoutineManager(3)

        f := newFibonacci(value, gm)
        fmt.Println(f.answer)

        end := time.Now()
        totalTime := end.Sub(start)
        fmt.Println("Fibonacci number: ", value, " took ", totalTime, "\n")
    }

}
0 голосов
/ 05 ноября 2018

Я предлагаю вам посчитать, сколько у вас фактически запущено программ.

Ваш первый звонок порождает две горутины. Каждый из них порождает еще две горутины. Общее количество порожденных goroutines будет 2^1 + 2^2 + 2^3 + ... + 2^n. Хотя многие из них выйдут до того, как вы достигнете числа, указанного ниже, это все равно лот горутин.

Sum

...