귀속 최적화
주말에 틈이 나면 처음부터 부드러운 신이 쓴 es6를 처음부터 다시 한 번 봤는데 많은 것들이 대추를 통째로 삼키고 많은 개념들이 이해가 안 되는 것을 발견했다.특히 함수의 확장 모듈은 이전에 마지막을 보지 못했고 귀속미 호출에 대해 개념이 명확하지 않았다.
이전에 쓴 권한 구조는 많은tree의 귀속 반복과 관련된다. 귀속 소모 성능, 귀속 플러그인 등급이 너무 많으면 창고가 넘치기 쉽다. 이 문제는 모두가 알고 있기 때문에 귀속 호출을 어떻게 처리하는가가 매우 중요하다. 이 마지막 호출 최적화는 바로 이 문제를 해결하는 것이다.
꼬리 호출의 개념에 관하여 완일봉의 문서를 직접 인용하거나 ES6 문서를 직접 볼 수 있다http://es6.ruanyifeng.com/#docs/function
곱하기
1. 귀속
const { log } = console
//
// ： O(n)
function getJc(n){
if(n===1) return 1
return n * getJc(n-1)
}
log(' ',getJc(4))
2. 귀속 최적화
// ： O(1)
function getJc1(n,x){
if(n===1) return x
return getJc1(n-1, x * n)
}
log(' ',getJc1(6,1))
3. 순환
// ： ， ，
function getJc2(n){
if( n <= 2 ) return n
let cj = 1
let n1 = 1
for( let i = 1; i <= n; i++ ){
n1 = cj
cj = n1 * i
}
return cj
}
log(' ',getJc2(6))
4. 코리화
// ，
function currying(fn, n) {
return function (m) {
return fn.call(this, m, n);
};
}
function tailFactorial(n, total) {
if (n === 1) return total;
return tailFactorial(n - 1, n * total);
}
const factorial = currying(tailFactorial, 1);
factorial(5) // 120
2. 피보나치 수열
1. 귀속
const { log } = console
//
// ：
function Fibonacci (n) {
if ( n <= 1 ) {return 1};
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
log(' ',Fibonacci(9))
2. 귀속 꼬리 호출 최적화
// ： ： ， ，
// ：
function Fibonacci1 (n,x=1,y=1) {
if ( n <= 1 ) {return y};
return Fibonacci1(n - 1,y,x+y);
}
log(' ',Fibonacci1(9))
3. 순환
// ： ： ， ； ： ，
function Fibonacci2 (n) {
if ( n <= 2 ) {return n};
let n1 = 1,n2 = 1, sum = 0
for(let i = 2; i <= n; i++){
sum = n1 + n2
n1 = n2
n2 = sum
}
return sum;
}
log(' ',Fibonacci2(80))
4.귀속➕캐시
// ： ➕
function memozi(fn){
let obj = {}
return function(n){
if(!obj[n]){
return obj[n] = fn(n)
}else{
return obj[n]
}
}
}
const Fibonacci3 = memozi ( function(n) {
if ( n <= 2 ) {return n};
return Fibonacci3(n-1) + Fibonacci3(n-2);
})
log(' ➕ ',Fibonacci3(80))
다음은 응우옌 일봉의 《ECMAScript 6 입문》에서 인용한다.http://es6.ruanyifeng.com/#docs/function
1. 꼬리 호출은 무엇입니까?
테일 콜(Tail Call)은 함수식 프로그래밍의 중요한 개념으로 그 자체가 매우 간단해서 한 마디로 명확하게 말할 수 있다. 즉, 어떤 함수의 마지막 단계는 다른 함수를 호출하는 것이다.
function f(x){
return g(x);
}
위 코드에서 함수 f의 마지막 단계는 함수 g를 호출하는 것이다. 이를 끝 호출이라고 한다.
다음 세 가지 상황은 모두 미호출에 속하지 않는다.
//
function f(x){
let y = g(x);
return y;
}
//
function f(x){
return g(x) + 1;
}
//
function f(x){
g(x);
}
//
function f(x){
g(x);
return undefined;
}
위 코드에서 상황은 첫째, 함수 g를 호출한 후에 값을 부여하는 조작이 있기 때문에 꼬리 호출에 속하지 않는다. 설령 의미가 완전히 같다고 해도.상황2는 한 줄에 써도 호출 후 조작에 속한다.
꼬리 호출이 반드시 함수 꼬리에 나타나는 것은 아니며, 마지막 단계만 조작하면 된다
function f(x) {
if (x > 0) {
return m(x)
}
return n(x);
}
위 코드에서 함수 m와 n은 모두 꼬리 호출에 속한다. 왜냐하면 그들은 모두 함수 f의 마지막 조작이기 때문이다.
2. 마지막 호출 최적화
꼬리 호출이 다른 호출과 다른 이유는 특수한 호출 위치에 있다.
우리는 함수 호출이 메모리에 '호출 기록', 즉 '호출 프레임' (call frame) 을 형성하여 호출 위치와 내부 변수 등의 정보를 저장하는 것을 안다.함수 A의 내부에서 함수 B를 호출하면 A의 호출 프레임 위에 B의 호출 프레임이 형성된다.B의 실행이 끝나면 결과가 A로 되돌아와야 B의 호출 프레임이 사라집니다.함수 B 내부에서 함수 C를 호출하면 C의 호출 프레임이 하나 더 있습니다.모든 호출 프레임은 호출 창고 (call stack) 를 형성합니다.
꼬리 호출은 함수의 마지막 작업이기 때문에 외부 함수의 호출 프레임을 보존할 필요가 없다. 호출 위치, 내부 변수 등 정보가 다시 사용되지 않기 때문에 내부 함수의 호출 프레임을 직접 사용하여 외부 함수의 호출 프레임을 대체하면 된다.
function f() {
let m = 1;
let n = 2;
return g(m + n);
}
f();
//
function f() {
return g(3);
}
f();
//
g(3);
위 코드에서 함수 g가 꼬리 호출이 아니라면 함수 f는 내부 변수 m와 n의 값, g의 호출 위치 등 정보를 저장해야 한다.그러나 g를 호출하면 함수 f가 끝나기 때문에 마지막 단계까지 실행하면 f(x)의 호출 프레임을 완전히 삭제하고 g(3)의 호출 프레임만 보존할 수 있다.
이를 "Tail call optimization"(Tail call optimization)이라고 하며, 내부 함수의 호출 프레임만 유지합니다.만약 모든 함수가 꼬리 호출이라면, 실행할 때마다 호출 프레임이 하나밖에 없기 때문에 메모리를 크게 절약할 수 있다.이것이 바로'꼬리 호출 최적화'의 의미다.
외부 함수의 내부 변수를 더 이상 사용하지 않아야 내부 함수의 호출 프레임이 외부 함수의 호출 프레임을 대체할 수 있으며, 그렇지 않으면 '꼬리 호출 최적화' 를 할 수 없습니다.
function addOne(a){
var one = 1;
function inner(b){
return b + one;
}
return inner(a);
}
위의 함수는 끝 호출 최적화를 하지 않습니다. 왜냐하면 내부 함수 inner는 외부 함수addOne의 내부 변수 원을 사용했기 때문입니다.
귀속
함수 호출 자체를 귀속이라고 한다.만약 꼬리가 자신을 호출한다면 꼬리귀속이라고 부른다.
반복은 수천 개의 호출 프레임을 동시에 저장해야 하기 때문에 '창고 넘침' 오류가 발생하기 쉽다.그러나 꼬리 귀속에 있어 하나의 호출 프레임만 존재하기 때문에 '창고 넘침' 오류가 영원히 발생하지 않습니다.
function factorial(n) {
if (n === 1) return 1;
return n * factorial(n - 1);
}
factorial(5) // 120
위 코드는 하나의 곱셈 함수로 n의 곱셈을 계산하려면 최대 n개의 호출 기록, 복잡도 O(n)를 저장해야 한다.
만약 끝귀환으로 바꾸면 호출 기록 하나만 보존합니다. 복잡도 O (1).
function factorial(n, total) {
if (n === 1) return total;
return factorial(n - 1, n * total);
}
factorial(5, 1) // 120
또 하나의 유명한 예는 바로 Fibonacci 수열을 계산하는 것이다. 또한 꼬리 귀속 최적화의 중요성을 충분히 설명할 수 있다.
꼬리가 아닌 Fibonacci 수열은 다음과 같습니다.
function Fibonacci (n) {
if ( n <= 1 ) {return 1};
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
Fibonacci(10) // 89
Fibonacci(100) //
Fibonacci(500) //
마지막 귀속 최적화된 Fibonacci 수열은 다음과 같다.
function Fibonacci2 (n , ac1 = 1 , ac2 = 1) {
if( n <= 1 ) {return ac2};
return Fibonacci2 (n - 1, ac2, ac1 + ac2);
}
Fibonacci2(100) // 573147844013817200000
Fibonacci2(1000) // 7.0330367711422765e+208
Fibonacci2(10000) // Infinity
이를 통해 알 수 있듯이'꼬리 호출 최적화'는 귀속 조작에 큰 의미를 가지기 때문에 일부 함수식 프로그래밍 언어는 이를 언어 규격에 썼다.ES6도 마찬가지로 처음으로 모든 ECMAScript의 실현은 반드시'꼬리 호출 최적화'를 배치해야 한다고 명확하게 규정했다.이것은 ES6에서 꼬리 귀속을 사용하기만 하면 창고 넘침(또는 층층이 귀속으로 인한 시간 초과)이 발생하지 않고 메모리를 상대적으로 절약할 수 있다는 것이다.
4. 귀속 함수의 개작
꼬리 귀속의 실현은 왕왕 귀속 함수를 고쳐 마지막 단계에서 자신만 호출할 수 있도록 해야 한다.이 점을 해내는 방법은 모든 내부 변수를 함수의 매개 변수로 바꾸는 것이다.예를 들어 위의 예에서 곱셈 함수factorial은 중간 변수 토탈을 사용해야 한다. 그러면 이 중간 변수를 함수의 매개 변수로 바꾸자.이렇게 하는 단점은 바로 직관적이지 않아서 첫눈에 보기 힘들다는 것이다. 왜 5의 곱셈을 계산하려면 두 개의 매개 변수 5와 1을 전달해야 합니까?
두 가지 방법으로 이 문제를 해결할 수 있다.방법은 첫째, 꼬리 귀속 함수 외에 정상적인 형식의 함수를 제공하는 것이다.
function tailFactorial(n, total) {
if (n === 1) return total;
return tailFactorial(n - 1, n * total);
}
function factorial(n) {
return tailFactorial(n, 1);
}
factorial(5) // 120
위 코드는 정상적인 형식의 곱셈 함수factorial을 통해 곱셈 함수tailFactorial을 호출하면 훨씬 정상적으로 보인다.
함수식 프로그래밍에는 코리화(currying)라는 개념이 있는데, 다중 매개 변수의 함수를 단일 매개 변수의 형식으로 바꾸는 것을 의미한다.이곳에서도 코리화를 사용할 수 있다.
function currying(fn, n) {
return function (m) {
return fn.call(this, m, n);
};
}
function tailFactorial(n, total) {
if (n === 1) return total;
return tailFactorial(n - 1, n * total);
}
const factorial = currying(tailFactorial, 1);
factorial(5) // 120
위 코드는 코리화를 통해 꼬리 귀속 함수tailFactorial을 하나의 매개 변수만 받아들이는factorial로 변경합니다.
두 번째 방법은 ES6의 함수 기본값을 사용하는 것이 훨씬 간단하다.
function factorial(n, total = 1) {
if (n === 1) return total;
return factorial(n - 1, n * total);
}
factorial(5) // 120
위 코드에서 인자 토탈은 기본값 1이 있기 때문에 호출할 때 이 값을 제공하지 않습니다.
총괄적으로 말하면 귀속은 본질적으로 일종의 순환 조작이다.순수한 함수식 프로그래밍 언어는 순환 조작 명령이 없고 모든 순환은 귀속으로 이루어진다. 이것이 바로 왜 귀속이 이런 언어에 매우 중요한가 하는 것이다.'꼬리 호출 최적화'를 지원하는 다른 언어(예를 들어 Lua, ES6)는 순환이 귀환으로 대체될 수 있다는 것만 알고 귀환을 사용하면 꼬리 귀환을 사용하는 것이 가장 좋다.
5. 엄격한 모델
ES6의 End-Call 최적화는 엄격한 모드에서만 실행되며 일반 모드는 유효하지 않습니다.
이것은 정상적인 모드에서 함수 내부에 두 개의 변수가 있어 함수의 호출 창고를 추적할 수 있기 때문이다.
마지막 호출 최적화가 발생하면 함수의 호출 창고가 바뀌기 때문에 위의 두 변수는 진실되지 않습니다.엄격한 모드에서 이 두 변수를 사용하지 않기 때문에, 마지막 호출 모드는 엄격한 모드에서만 적용됩니다.
function restricted() {
'use strict';
restricted.caller; //
restricted.arguments; //
}
restricted();
6. 꼬리 귀속 최적화의 실현
꼬리 귀속 최적화는 엄격한 모델에서만 효력이 발생한다. 그러면 정상적인 모델에서나 이 기능을 지원하지 않는 환경에서도 꼬리 귀속 최적화를 사용할 방법이 없을까?대답은 할 수 있다. 바로 자신이 미귀환 최적화를 실현하는 것이다.
그것의 원리는 매우 간단하다.미귀환이 최적화를 필요로 하는 이유는 호출 창고가 너무 많아서 넘쳐나기 때문이다. 그러면 호출 창고를 줄이면 넘치지 않는다.어떻게 하면 호출 창고를 줄일 수 있습니까?바로'순환'을 채택하여'귀속'을 바꾸는 것이다.
다음은 정상적인 귀속 함수다.
function sum(x, y) {
if (y > 0) {
return sum(x + 1, y - 1);
} else {
return x;
}
}
sum(1, 100000)
// Uncaught RangeError: Maximum call stack size exceeded(…)
위 코드에서sum는 귀속 함수이고 매개 변수 x는 누적된 값이며 매개 변수 y는 귀속 횟수를 제어한다.만약sum귀환을 100000회 지정하면 오류가 발생하고 호출 창고의 최대 횟수를 초과합니다.
번지점프 함수 (trampoline) 는 귀속 집행을 순환 집행으로 바꿀 수 있다.
function trampoline(f) {
while (f && f instanceof Function) {
f = f();
}
return f;
}
위에는 번지점프 함수의 실현이고 하나의 함수 f를 매개 변수로 받아들인다.f가 실행된 후에 함수를 되돌리기만 하면 계속 실행합니다.이것은 함수를 되돌려주고 이 함수를 실행하는 것이지 함수에서 함수를 호출하는 것이 아니다. 그러면 귀속 집행을 피할 수 있고 호출 창고가 너무 큰 문제를 없앨 수 있다.
그리고 해야 할 일은 원래의 귀속 함수를 한 걸음 한 걸음 다른 함수로 바꾸는 것이다.
function sum(x, y) {
if (y > 0) {
return sum.bind(null, x + 1, y - 1);
} else {
return x;
}
}
위 코드에서sum 함수는 실행할 때마다 자신의 다른 버전으로 되돌아옵니다.
현재, 번지점프 함수를 사용하여sum를 실행하면 호출 창고 넘침이 발생하지 않습니다.
trampoline(sum(1, 100000))
// 100001
번지점프 함수는 진정한 꼬리 귀속 최적화가 아니다. 아래의 실현이야말로.
function tco(f) {
var value;
var active = false;
var accumulated = [];
return function accumulator() {
accumulated.push(arguments);
if (!active) {
active = true;
while (accumulated.length) {
value = f.apply(this, accumulated.shift());
}
active = false;
return value;
}
};
}
var sum = tco(function(x, y) {
if (y > 0) {
return sum(x + 1, y - 1)
}
else {
return x
}
});
sum(1, 100000)
// 100001
위 코드에서 tco 함수는 꼬리 귀속 최적화의 실현이고 그 오묘함은 상태 변수active에 있다.기본적으로 이 변수는 활성화되지 않습니다.일단 미귀환 최적화 과정에 들어가면 이 변수는 활성화된다.그리고 매 라운드에sum가 되돌아오는 것은undefined이기 때문에 되돌아오는 집행을 피한다.accumulated 수조는 매 라운드sum가 실행하는 매개 변수를 저장하고 항상 값이 있기 때문에 accumulator 함수 내부의while 순환이 항상 실행될 수 있음을 보장한다.이렇게 하면 교묘하게'귀속'을'순환'으로 바꾸었고 뒷바퀴의 매개 변수는 앞바퀴의 매개 변수를 대체하여 호출 창고가 한 층밖에 없다는 것을 보장한다.
이상은 응우옌 이펑의 《ECMAScript 6 입문》에서 인용하였다.http://es6.ruanyifeng.com/#docs/function
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
