재귀 GO 대 스칼라

Question

다음 스칼라 코드는 1.5 분 안에 완료되지만 GO 코드는 2.5 분 안에 완료됩니다.
최대 fib (40)까지 모두 2 초가 소요됩니다. 그 차이가 fib (50)에 나타난다
나는 네이티브가되어 가고 있다는 인상을 받았고, 스칼라가 빠르다.

스칼라

def fib(n:Int):Long = { 
    n match { 
     case 0 => 0 
     case 1 => 1 
     case _ => fib(n-1) + fib(n-2) 
    } 
} 

는

func fib(n int) (ret int) { 
    if n > 1 { 
     return fib(n-1) + fib(n-2) 
    } 
    return n 
} 

스칼라 최적화를 GO?
골란 한계?

"내 다른 자동차는 캐드 러입니다."라는 질문은 "스칼라가 어떻게이 특정 마이크로 벤치 마크에서보다 빠르다"는 질문에 "

피보나치를 잊어 버리면 재귀가 필요한 기능이 있다고 말할 수 있습니다.
재귀 상황에서 스칼라가 우월합니까?

아마 내부 컴파일러 구현 또는 심지어 스칼라 특정 최적화.
아는 경우 답변하십시오.

이동 루프 실행에 15,000,000,000는 재귀 꼬리 아닙니다 때문에 스칼라 솔루션 스택을 소모합니다

func fib(n int) (two int) { 
    one := 0 
    two = 1 
    for i := 1; i != n; i++ { 
     one, two = two, (one + two) 
    } 
    return 
} 

Answer 1

초 12 (추가는 재귀 호출 후 발생)하지만 작성해서는 안 쓰레기는 전혀 없습니다.

사용중인 핫스팟 컴파일러 (아마도 서버)가이 코드 패턴에 대해 Go 컴파일러보다 더 나은 컴파일러 일 가능성이 큽니다.

정말 호기심이 있다면 download a debug build of the JVM, and have it print out the assembly code 수 있습니다.

Answer 2

이동의 경우 재귀가 아닌 반복을 사용하십시오. 재귀는 명시 적 스택의 반복으로 대체 될 수 있습니다. 함수 호출과 호출 스택 관리의 오버 헤드를 피할 수 있습니다.

package main 

import "fmt" 

func fib(n int) (f int64) { 
    if n < 0 { 
     n = 0 
    } 
    a, b := int64(0), int64(1) 
    for i := 0; i < n; i++ { 
     f = a 
     a, b = b, a+b 
    } 
    return 
} 

func main() { 
    n := 1000 
    fmt.Println(n, fib(n)) 
} 

출력 :

$ time .fib 
1000 8261794739546030242 
real 0m0.001s 
user 0m0.000s 
sys 0m0.000s 

적절한 알고리즘을 사용하여 예를 들어, 반복을 사용하고, 1000 (50)로부터 n 증가는 거의없고 시간이 소요된다. 기하 급수적 인 시간 복잡성을 피하십시오. 성능이 중요 할 때 피보나치 수에 대해 재귀를 사용하지 마십시오.

참조 :

Recursive Algorithms in Computer Science Courses: Fibonacci Numbers and Binomial Coefficients

우리는 분기 재귀 기능의 계산 비 효율성이 적절하게 교육 과정의 첫 3 년 컴퓨터 과학 과정에 대한 거의 모든 교과서에 포함되지 않았 음을 관찰합니다. 피보나치 수와 이항 계수는 분기 된 재귀 함수의 예로는 으로 자주 사용되었습니다.그러나, 그들의 기하 급수적 인 시간 복잡성은 드물게 주장되었고 전혀 교과서에서 증명되지 않았습니다. 대안 선형 시간 반복 솔루션은 거의 언급되지 않았다. . 우리는 이러한 재귀 함수 에 지수 적 시간 복잡도가 있다는 간단한 증명을 제공합니다.

재귀는 하나의 재귀 호출을 만드는 정의 및 알고리즘에 대한 효율적인 기술이지만 두 개 이상의 재귀 호출을 만드는 경우 매우 비효율적 일 수 있습니다. 따라서 재귀 접근법은 효율적인 계산 도구가 아닌 개념 도구로 자주 더 유용합니다. 이 백서에 제시된 증거는 오타와 대학교의 학생 (1 년차 학생 )에게 (5 년에 걸쳐) 성공적으로 가르쳐졌습니다. 문제 해결 및 정의 도구로서의 재귀는 컴퓨터 과학 과정의 두 번째 부분에서 다룰 것을 제안합니다. 그러나 반복적 프로그래밍은 프로그램이 잘 마스터되고 스택 작업을 잘 이해 한 후에 코스가 끝날 때 연기됩니다 (또는 두 번째 컴퓨터 과학 과정이 시작될 때 이 더 좋음).