이동이 재귀 피보나치에서 상대적으로 느린 것처럼 보이는 이유는 무엇입니까?

Question

저는 컴파일 된 언어와 해석 된 언어에 대한 간단한 재귀 fibonacci 함수를 비교해 보았습니다. https://github.com/drujensen/fib. 어디서나 최적화 기법을 사용하지 않기 때문에 상당히 공정한 것처럼 보입니다. Go의 능력을 사용하는 더 좋은 방법이 있다는 것을 알고 있지만 Go가 왜 다른 컴파일되고 정적으로 입력 된 언어보다 느린 것일까 궁금해했습니다. 11시에는 내 컴퓨터에서 Go와 매우 유사하게 보입니다.

Answer 1

이유는 재귀 계산의 조합 폭발입니다. Algorithms 101에서는 보통 Dru Jensen의 재귀 알고리즘이 피보나치 수를 계산하는 끔찍한 방법 인 이유를 설명합니다 : http://www.cs.toronto.edu/~gfb/csc104/2016W/Lectures/CSC104.2016W.Week-7.Lecture.Fibonacci.I.pdf. fib 프로 시저는 호출 될 때마다 자체를 두 번 호출합니다. 의도적으로 Go에는 꼬리 재귀가 없습니다 (Tail call). 의도적으로 Go는 각 goroutine에 대해 매우 작은 스택으로 시작합니다.이 스택은 폭발적으로 증가해야합니다. Go 프로그래머가이 알고리즘을 사용하고 싶지는 않습니다.이 알고리즘은 가장 느린 속도보다 느린 382,358,169 배, 가장 빠른 속도보다 느린 18,593,103,127 배이므로 성능을 희생시키는 최적화는 무의미합니다.

$ go test fib_test.go -bench=. 
BenchmarkDruJensen-8    1 9482482595 ns/op 
BenchmarkPeterSO1-8  50000000   24.8 ns/op 
BenchmarkPeterSO2-8  2000000000    0.51 ns/op 

fib_test.go : 여기

는 일부 이동 벤치 마크 결과입니다

package main 

import (
    "fmt" 
    "testing" 
) 

// Dru Jensen: https://github.com/drujensen/fib 
func fib(n uint64) uint64 { 
    if n <= 1 { 
     return 1 
    } else { 
     return fib(n-1) + fib(n-2) 
    } 
} 

func BenchmarkDruJensen(b *testing.B) { 
    for i := 0; i < b.N; i++ { 
     fib(46) 
    } 
} 

// PeterSO 
func fibonacci1(n int) uint64 { 
    f := uint64(0) 
    a, b := uint64(0), uint64(1) 
    for i := 0; i < n; i++ { 
     f, a, b = a, b, a+b 
     if a > b { 
      break 
     } 
    } 
    return f 
} 

func BenchmarkPeterSO1(b *testing.B) { 
    for i := 0; i < b.N; i++ { 
     fibonacci1(46) 
    } 
} 

var fibonaccis = []uint64{ 
    0, 
    1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 
    2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 
    317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 
    14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 
    267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 
    4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 
    53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 
    591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 
    6557470319842, 10610209857723, 17167680177565, 27777890035288, 
    44945570212853, 72723460248141, 117669030460994, 190392490709135, 
    308061521170129, 498454011879264, 806515533049393, 1304969544928657, 
    2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 
    14472334024676221, 23416728348467685, 37889062373143906, 
    61305790721611591, 99194853094755497, 160500643816367088, 
    259695496911122585, 420196140727489673, 679891637638612258, 
    1100087778366101931, 1779979416004714189, 2880067194370816120, 
    4660046610375530309, 7540113804746346429, 12200160415121876738, 
} 

// PeterSO 
func fibonacci2(n int) uint64 { 
    return fibonaccis[n] 
} 

func BenchmarkPeterSO2(b *testing.B) { 
    for i := 0; i < b.N; i++ { 
     fibonacci2(46) 
    } 
} 

Answer 2

TL; DR 내 결론까지 지금, 우리는 아마 반복에 찬성 재귀를 피해야 알고리즘은 주로 Go에 꼬리 호출 최적화가없는 한 주로 사용됩니다. 재귀를 사용하지 않는 경우, 이동 미친 듯이 빠른 :-)에게 것 같다

호기심 나는 베드로 버전 (BTW, 당신은 (46)의 정확한 피보나치를 얻을 수 i <= n에 i < n을 변경해야합니다) 또 다른 (간단) 반복 알고리즘을 비교

. 흥미롭게도, main.go 순서 문제, 컴파일 된 변종을 사용하지 않는 경우. 두 번째 함수 호출이 빠릅니다. 우리는이처럼 객관적인 결과를 얻을 수있는 벤치 마크를 사용해야합니다 : 변수 f를 사용하지만, 직접 X를 사용하지 않음으로써

go test -bench . 
BenchmarkFibIt-4  100000000    18.5 ns/op 
BenchmarkFibP-4   50000000    29.1 ns/op 
BenchmarkFib-4     1  12008314197 ns/op 

를, 그것은 조금 더 빨리 도착 ;-) 놀랍게도, 실행의 컴파일되지 않은 변종 main.go은 컴파일 된 것보다 거의 빠르며 때로는 더 빠릅니다!

필자의 결론은 Go에 꼬리 호출 최적화가없는 한 반복적 인 알고리즘을 우선적으로 사용하여 재귀를 피하는 것이 좋습니다.

main.go :

package main 

import (
    "fmt" 
    "log" 
    "time" 
) 

func fib(n int) uint64 { 
    if n <= 1 { 
     return 1 
    } 
    return fib(n-1) + fib(n-2) 
} 

func fibIt(n int) uint64 { 
    var x, y uint64 
    x, y = 0, 1 
    for i := 0; i < n; i++ { 
     // c <- x 
     x, y = y, x+y 
    } 
    return x 
} 

func fibP(n int) uint64 { 
    f := uint64(0) 
    a, b := uint64(0), uint64(1) 
    for i := 0; i <= n; i++ { 
     f, a, b = a, b, a+b 
     if a > b { 
      break 
     } 
    } 
    return f 
} 

func main() { 
    var start time.Time 
    var elapsed time.Duration 

    start = time.Now() 
    fibIt(46) 
    elapsed = time.Since(start) 
    fmt.Println("Iterative Fibonacci of 46 took", elapsed) 

    start = time.Now() 
    fibP(46) 
    elapsed = time.Since(start) 
    fmt.Println("Peter's Iterative Fibonacci of 46 took", elapsed) 

    start = time.Now() 
    fib(46) 
    elapsed = time.Since(start) 
    fmt.Println("Recursive Fibonacci of 46 took", elapsed) 
} 

main_test.go :

package main 

import (
    "testing" 
) 

func BenchmarkFibIt(b *testing.B) { 
    for i := 0; i < b.N; i++ { 
     fibIt(46) 
    } 
} 

func BenchmarkFibP(b *testing.B) { 
    for i := 0; i < b.N; i++ { 
     fibP(46) 
    } 
} 

func BenchmarkFib(b *testing.B) { 
    for i := 0; i < b.N; i++ { 
     fib(46) 
    } 
}