저는 컴파일 된 언어와 해석 된 언어에 대한 간단한 재귀 fibonacci 함수를 비교해 보았습니다. https://github.com/drujensen/fib. 어디서나 최적화 기법을 사용하지 않기 때문에 상당히 공정한 것처럼 보입니다. Go의 능력을 사용하는 더 좋은 방법이 있다는 것을 알고 있지만 Go가 왜 다른 컴파일되고 정적으로 입력 된 언어보다 느린 것일까 궁금해했습니다. 11시에는 내 컴퓨터에서 Go와 매우 유사하게 보입니다.이동이 재귀 피보나치에서 상대적으로 느린 것처럼 보이는 이유는 무엇입니까?
답변
이유는 재귀 계산의 조합 폭발입니다. 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)
}
}
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)
}
}
- 1. CALayer의 이동이 UIView보다 느린 이유는 무엇입니까?
- 2. 피보나치에서 재귀 호출 수를 계산하십시오.
- 3. 계산식이있는 PSeq.map이 멈춘 것처럼 보이는 이유는 무엇입니까?
- 4. Squeak 인터페이스가 낡은 것처럼 보이는 이유는 무엇입니까?
- 5. 초기 페이지로드시 require.js가 모든 모듈을로드하는 것처럼 보이는 이유는 무엇입니까?
- 6. androidbutton이 너비가 압축 된 것처럼 보이는 이유는 무엇입니까?
- 7. asp.net의 flush가 workig가 아닌 것처럼 보이는 이유는 무엇입니까?
- 8. firebase 콜렉션이 null 행으로 시작하는 것처럼 보이는 이유는 무엇입니까?
- 9. 내 셀이 내 UITableView에서 비어있는 것처럼 보이는 이유는 무엇입니까?
- 10. 명명 된 매개 변수가 PHP에서 작동하는 것처럼 보이는 이유는 무엇입니까?
- 11. IceFaces가 내 요청을 먹는 것처럼 보이는 이유는 무엇입니까?
- 12. 파일이 iPhone 시뮬레이터에 현지화 된 것처럼 보이는 이유는 무엇입니까?
- 13. 이 요소는 위치가 고정되었을 때 스크롤하는 것처럼 보이는 이유는 무엇입니까?
- 14. 내 안드로이드 프로젝트가 죽은 것처럼 보이는 이유는 무엇입니까?
- 15. SharePoint Navigation에서 메모리가 새 것처럼 보이는 이유는 무엇입니까?
- 16. "__declspec (dllimport)"이 쓸모없는 것처럼 보이는 이유는 무엇입니까?
- 17. .Net Dictionary가 정렬 된 것처럼 보이는 이유는 무엇입니까?
- 18. 내 세션 변수가 ASP.NET에서 비어있는 것처럼 보이는 이유는 무엇입니까?
- 19. Leopard에서 만든 대화 상자가 Tiger에서 끔찍한 것처럼 보이는 이유는 무엇입니까?
- 20. 새로 생성 된 객체가 같은 것처럼 보이는 이유는 무엇입니까?
- 21. autoResizeColumn() 루프가 Google Apps Script를 고정하고있는 것처럼 보이는 이유는 무엇입니까?
- 22. 루프가 인덱스 1에서 시작하는 것처럼 보이는 이유는 무엇입니까?
- 23. 메뉴에서 보이는 것처럼
- 24. 모듈이없는 것처럼 보이는 예외를 지정하는 방법은 무엇입니까?
- 25. UIScrollview에있는 UIButton의 이동이 느린 속도로 느려집니다.
- 26. Direct3DCreate9가 느린 이유는 무엇입니까?
- 27. ODBC가 느린 이유는 무엇입니까?
- 28. 이 예제에서 emplace_back으로 이동이 필요한 이유는 무엇입니까?
- 29. RSpec - 갇혀있는 것처럼 보이는 테스트
- 30. 나는 상대적으로 느린 절차 (적절하게 느린 이름)가 GHCi
이것은 질문으로 문제를 해결하기 위해 보이지 않는 다른 언어로 (상대 "왜 * 이동 상대적으로 * 느리다" 연결된 레포에서) –
C, C++, Swift 등은 실제로 꼬리 재귀를 가지고 있으므로 같은 시간 범위에 있음을 의미합니다. 이것은 Go가 오늘까지 그것을 가지고 있지 않은 이유에 대한 질문으로 이어질 것입니다. Ardan Labs는 앞으로 꼬리 전화 최적화가있을 수 있음을 언급합니다. https://www.goinggo.net/2013/09/recursion-and-tail-calls-in-go_26.html –