피보나치 수열을 계산하는 재귀 함수가 필요하다고 가정해 보겠습니다. 피보나치 수는 이전 두 피보나치 수의 합입니다. 처음 두 숫자는 0과 1입니다.
var fibonacci = function(n) {
n
for (var i = 0; i <= 10; i = 1) ) {
document.writeln('// ' i ': ' fibonacci(i))
}
// 0:0
// 1:1
/ / 2:1
// 3:2
// 4:3
// 5:5
// 6:8
// 7:13
// 8 : 21
// 9: 34
// 10: 55
이 방법은 작동하지만 불필요한 작업을 많이 수행합니다. 피보나치 함수는 453번 호출되었습니다. 우리는 이를 11번 호출했고 방금 계산되었을 수도 있는 값을 계산하기 위해 자체적으로 442번 호출했습니다. 이 함수를 메모리 가능하게 만들면 계산 복잡성을 크게 줄일 수 있습니다.
저장된 결과를 메모라는 배열에 저장합니다. 저장된 결과는 클로저에 숨겨질 수 있습니다. 함수가 호출되면 함수는 먼저 계산된 결과가 이미 알려져 있는지 확인하고, 그렇다면 저장된 결과를 즉시 반환합니다.
var fibonacci = function() {
var memo = [0, 1];
var fib = function (n) {
var result = memo[n]
if (typeof result !== 'number') {
결과 = fib(n - 2);
memo[n] = 결과;
}
return result;
return fib; ();
이 함수는 동일한 결과를 반환하지만 29번만 호출됩니다. 우리는 이를 11번 호출했고, 이전에 저장된 결과를 얻기 위해 자체적으로 18번 호출했습니다.
위 내용의 출처: http://demon.tw/programming/javascript-memoization.html
realazy는 블로그에서 JavaScript Memoization을 구현했습니다. 메모이제이션은 함수 반환 값의 캐시입니다. 함수 매개변수와 반환 결과를 일대일로 대응하는 해시 리스트 등 실제 위키에는 자세한 설명이 나와 있지만 구체적인 구현 문제에 대해서는 다루지 않겠습니다. 기사에는 매개변수와 문자가 직접 연결되는 등의 문제가 있습니다. 문자열이 쿼리 캐시 결과의 키로 사용됩니다. 매개변수에 객체나 배열이 포함되어 있으면 매개변수도 보장하기 어렵습니다. 1층 댓글에 언급된 [221,3], [22,13] 같은 거죠.
다시 작성해 보겠습니다. 먼저 해시 테이블을 사용하여 캐시된 데이터를 저장합니다.
var 캐시 = {}
return function(){
var key = []
for ( var i=0 , l =args.length; i < l; i )
key.push(arguments[i])
if( !(key in 캐시) )
cache[key ] = fn.apply (this, 인수);
return 캐시[key];
}
차이점은 배열을 직접 키이지만 함수에 주의하세요. 의 인수는 실제 배열이 아닌 js 인터프리터에 의해 구현된 특수 개체이므로 변환해야 합니다...
ps: 원래 매개 변수에는 메서드 이름과 컨텍스트 참조가 포함됩니다. fib.fib_memo = Memoize('fib_memo', fib)이지만 실제로는 이것을 사용하여 카레로 생성된 함수에서 상위 객체를 직접 참조할 수 있습니다. 더 복잡한 예는 John Resig의 makeClass를 참조하세요. 함수 참조를 직접 전달하도록 변경되었습니다: fib.fib_memo = Memoize(fib.fib_memo)
이렇게 작성하면 매개변수로 구성된 배열이 매우 안정적이지 않나요? 하지만 실제로 배열을 js 객체의 속성 이름으로 사용할 수 있는 이유는 배열이 문자열로 처리되기 때문입니다. 즉, 함수에 전달하는 매개변수가 다음과 같은 경우입니다. ,3), 캐시 객체는 다음과 같습니다: { “1,2,3″: somedata }. 매개변수에 객체가 있는 경우: (1,2,{i:”yy”}) 실제 키 값은 "1,2,[object Object]"이므로 실제로 배열을 문자열로 연결하는 방법과 다르지 않습니다...
예:
코드 복사
var obj = {}
obj[a] = "111"
obj[b] = "222" ;
for( var i in obj )
alert( i " = " obj[i] ); //"1,2,[object Object] = 222"만 나타납니다. obj[a] = "111"을 덮어썼습니다
매개변수를 키 이름으로 직접 사용하는 방법은 신뢰성이 없습니다... 다른 방법을 시도해 보세요:
코드 복사 코드는 다음과 같습니다. 다음과 같습니다:
function Memoize(fn){
var 캐시 = {}, args = []
return function(){
for( var i= 0, key = args.length; i < key; i ) {
if( 동등( args[i], 인수 ) )
return 캐시[i]
}
args[key ] = 인수;
cache[key] = fn.apply(this, 인수);
return 캐시[키];
}
위의 문제를 방지하려면 해시 키-값 쌍 인덱스를 사용하는 대신 함수의 매개변수와 결과가 각각 두 개의 목록에 캐시됩니다. 매번 비교를 위해 전체 매개변수 목록을 먼저 탐색하고 해당 키 이름/ID 번호를 확인합니다. 그런 다음 결과 목록에서 데이터를 가져옵니다. 배열을 비교하는 동일한 방법은 다음과 같습니다.
function equal( first , second ){
if( !first || !second || first.constructor != second.constructor )
return false
if( first.length && typeof first != "string" )
for(var i=0, l = ( first.length > second.length ) ? first.length : second.length; iif( !equal( first[i], second[i] ) ) return false
}
else if( typeof first == 'object' )
for(var n in first){
if( !equal ( 첫 번째[n] , 두 번째[n] ) ) return false
}
else
return ( 첫 번째 === 두 번째 )
true
}
thousand 매개변수의 내용이 아닌 메모리 참조를 비교하므로 인수와 인수의 배열을 비교하기 위해 ==를 직접 사용하지 마십시오.
이 방법은 매우 느리고, 동일한 방법은 실제로 거의 영향을 미치지 않습니다. 그러나 캐시된 결과의 수가 증가하면 매번 매개변수 목록을 순회하는 것은 매우 비효율적입니다(firefox3에서는 80보다 큰 피보나치 수열을 찾습니다). Safari 대비 약 40ms 소요3)
실제 응용 프로그램에서 매개 변수가 많이 변경되지 않거나 매개 변수를 허용하지 않는 경우 Oliver Steel의 "One-Line JavaScript Memoization" 기사를 참조하여 짧은 기능으로 문제를 해결할 수 있습니다. style. :
function Memoize(o, p ) {
var f = o[p], mf, value;
var s = function(v) {return o[p]=v||mf}
((mf = function() {
( s(function(){return value})).reset = mf.reset;
return value = f.apply(this,arguments) //매개변수를 허용하도록 수정되었습니다.
}).reset = s)()
}
예:
var fib = {
temp: function(n){
for(var i=0;i<10000;i )
n=n 2;
return n;
}
}
Memoize(fib,"temp") //fib.temp가 반환 값을 캐시하도록 합니다
fib.temp( 16); //실행 결과: 20006, was Cache
fib.temp(20); //실행 결과: 20006
fib.temp(10); //실행 결과: 20006
fib.temp .reset(); //캐시 재설정
fib.temp(10); //실행 결과: 20010
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
