[본 글 주소] http://cuimingda.com/2009/02/speed-up-your-javascript-part-3.html
재귀는 스크립트의 실행 속도를 늦추는 적 중 하나입니다. 재귀가 너무 많으면 브라우저가 죽거나 설명할 수 없이 갑자기 자동으로 종료될 때까지 브라우저가 점점 더 느려지므로 JavaScript에서 이러한 일련의 성능 문제를 해결해야 합니다. 이 시리즈의 두 번째 기사에서는 메모이제이션 기술을 사용하여 함수에서 너무 많은 재귀 호출을 대체하는 방법을 간략하게 소개했습니다. 메모이제이션은 이전 계산 결과를 캐시하여 이미 계산된 결과를 다시 계산할 필요가 없도록 하는 기술입니다. 재귀를 통해 계산을 수행하는 함수의 경우 메모이제이션은 매우 유용합니다. 현재 사용하고 있는 메모이저(memoizer)는 Crockford가 작성한 것으로 주로 정수를 반환하는 재귀 연산에 사용됩니다. 물론 모든 재귀 함수가 정수를 반환하는 것은 아니므로 더 많은 유형의 재귀 함수를 처리하려면 보다 일반적인 memoizer() 함수가 필요합니다.
function memoizer(fundamental, 캐시){ 캐시 = 캐시 || {} var shell = function(arg){ if (!(arg in 캐시)){ 캐시[arg] = 기본(shell, arg) } return 캐시[arg] ; }; return shell;} 이 버전의 함수는 Crockford가 작성한 것과 약간 다릅니다. 먼저, 매개변수의 순서가 바뀌어 첫 번째 매개변수로 원래 함수가 설정되고, 두 번째 매개변수는 캐시 객체로 설정되는데, 이는 모든 재귀 함수에 초기 정보가 포함되어 있지 않기 때문에 선택 사항입니다. 함수 내에서 캐시 개체의 유형을 배열에서 개체로 캐스팅하여 이 버전이 정수를 반환하지 않는 재귀 함수를 수용할 수 있도록 했습니다. 쉘 함수에서는 in 연산자를 사용하여 매개변수가 이미 캐시에 포함되어 있는지 확인합니다. 이 작성 방법은 유형이 정의되지 않았는지 테스트하는 것보다 더 안전합니다. 왜냐하면 정의되지 않은 것이 유효한 반환 값이기 때문입니다. 우리는 설명을 위해 이전에 언급한 피보나치 수열을 계속 사용합니다:
var fibonacci = memoizer(function (recur, n) { return recur(n - 1) + recur(n - 2); }, {"0": 0, "1" :1}); 마찬가지로 fibonacci(40) 함수를 실행하면 과장된 331,160,280번 대신 원래 함수가 40번만 호출됩니다. 메모 기능은 결과 집합이 엄격하게 정의된 재귀 알고리즘에 적합합니다. 그러나 실제로 메모이제이션 방법을 사용한 최적화에 적합하지 않은 재귀 알고리즘이 많이 있습니다.
학교의 교수님 중 한 분은 재귀가 사용된 모든 상황이 필요하다면 반복으로 대체될 수 있다고 항상 주장하셨습니다. 실제로 재귀와 반복은 특히 한쪽이 잘못되었을 때 서로를 보완하는 방법으로 자주 사용됩니다. 재귀적인 알고리즘을 반복적인 알고리즘으로 변환하는 기술 역시 개발 언어와 무관합니다. 그러나 실행 환경의 리소스가 매우 제한적이기 때문에 JavaScript의 중요성이 더 큽니다. 병합 정렬과 같은 일반적인 재귀 알고리즘을 검토해 보겠습니다. JavaScript에서 이 알고리즘을 구현하려면 다음 코드가 필요합니다.
function merge(left, right){ var result = [] while (left.length > 0 && right.length > 0) { if (left[0] < right[0]){ result.push(left.shift()) } else { result.push(right.shift()) } return result.concat(left ).concat (right);}//병합 정렬 알고리즘 function mergeSort(items){ if (items.length == 1) { return items; } var middle = Math.floor(items.length / 2) using recursion , left = items. Slice(0, middle), right = items.slice(middle); return merge(mergeSort(left), mergeSort(right));} mergeSort() 함수를 호출하여 배열을 처리하고, 정렬된 배열을 반환할 수 있습니다. mergeSort() 함수가 호출될 때마다 두 번의 재귀 호출이 발생한다는 점에 유의하십시오. 이 알고리즘은 각 결과가 한 번만 계산되고 사용되며 결과를 버퍼링해도 소용이 없기 때문에 메모이제이션을 사용하여 최적화할 수 없습니다. 100개 요소의 배열에 mergeSort() 함수를 사용하면 총 199번의 호출이 발생합니다. 1000개의 요소 배열은 1999개의 호출을 수행합니다. 이 경우 우리의 해결책은 재귀 알고리즘을 반복 알고리즘으로 변환하는 것입니다. 이는 일부 루프를 도입하는 것을 의미합니다(알고리즘에 대해서는 "목록 처리: 자연스럽게 다시 정렬" 기사를 참조할 수 있음).
// 반복 구현 사용 병합 정렬 알고리즘 function mergeSort(items){ if (items.length == 1) { return items; } var work = [] for (var i=0, len=items.length; i < len; i++){ work .push([items[i]]); } work.push([]); //항목 수가 홀수인 경우 (var lim=len; lim > 1; lim = (lim+1)/2 ) { for (var j=0,k=0; k < lim; j++, k+=2){ work[j] = merge(work[k], work[k+1]) } work[j] = [ ]; //항목 수가 홀수인 경우 } return work[0];}이 병합 정렬 알고리즘 구현은 정렬을 위해 재귀 대신 일련의 루프를 사용합니다. 병합 정렬은 먼저 배열을 하나의 요소만 포함하는 여러 배열로 분할하므로 이 방법은 재귀 함수를 암시적으로 사용하는 것보다 더 명시적으로 이 작업을 수행합니다. 작업 배열은 단일 요소 배열의 배열을 포함하도록 초기화됩니다. 루프가 실행될 때마다 두 배열이 병합되고 병합된 결과가 작업 배열에 다시 저장됩니다. 함수가 실행되면 작업 배열의 첫 번째 요소를 통해 정렬된 결과가 반환됩니다. 이 병합 정렬 구현에서는 재귀를 사용하지 않고 알고리즘도 구현됩니다. 그러나 이로 인해 많은 수의 루프가 발생하고 루프 수는 정렬할 배열의 요소 수에 따라 결정되므로 이 추가 오버헤드를 처리하기 위해 이전 기사에서 설명한 기술을 사용하여 수정해야 할 수도 있습니다. .
기본 원칙을 요약하면 재귀를 사용할 때마다 주의해야 합니다. 메모화와 반복은 재귀를 대체하는 두 가지 솔루션입니다. 물론 가장 직접적인 결과는 스크립트가 제어할 수 없게 되는 대화 상자를 피하는 것입니다.