Memoizáció - emlékező függvények

Memoizáció

A számítástudományokban a memoizáció egy optimalizációs technika, melyet elsősorban arra használnak, hogy felgyorsítsák a számítógép programokat azáltal, hogy a függvényhívások nem ismétlik meg a már korábban feldolgozott bemenetek eredményeinek újbóli kiszámítását.

Forrás: Wikipédia

Faktoriális számítás (1)

1 function factorial(n) {
2   return n < 2 ? n : n * factorial(n - 1);
3 }
  • Cél: építsünk a korábban kiszámoltakra, így a további függvényhívások esetén nem kell előről kezdeni a számolást.
  • Megvalósítás:
    1. Megnézzük el van-e már tárolva a kalkulált eredmény a függvény egy tulajdonságában vagy closure-ben
    2. Kiszámítjuk és tároljuk eredményt

Faktoriális számítás (2)

 1 function factorial(n) {
 2   factorial = function (n) {
 3     var cache = factorial.cache;
 4     if (cache[n] === undefined) {
 5      cache[n] = n * factorial(n - 1);
 6     }
 7     return factorial.cache[n];
 8   }
 9   factorial.cache = [0, 1];
10   factorial.next = function () {
11    return factorial(factorial.cache.length);
12   }
13   return factorial(n);
14 }

RangeSum (1)

Egy sorozat egy darabjának elemeinek összegét számolja ki (például az első 5 elem összege).

 1 function RangeSum(data) {
 2   this._data = data || [];
 3 }
 4 RangeSum.prototype = {
 5   push : function () {
 6     // ...
 7   },
 8   concat : function () {
 9     // ...
10   },
11   sum : function (start, end) {
12     // ...
13   }
14 }

RangeSum (2)

 1 sum: function (start, end) {
 2   function sum(start, end) {
 3     var data = this._data
 4       , l = data.length
 5       , cache = sum.cache
 6       , i = cache.length;
 7     start = Math.min(Math.max(0, start || 0), l - 1);
 8     end = Math.max(start, Math.min(l, end || l));
 9     for (; i <= end; i += 1) {
10       cache[i] = cache[i - 1] + data[i - 1];
11     }
12     return cache[end] - cache[start];
13   }
14   sum.cache = [0];
15   this.sum = sum;
16   return this.sum(start, end);
17 }

Automatikus memoizáció

Underscore.js

 1 var hasOwnProperty = Object.prototype.hasOwnProperty;
 2   , _ = _ || {};
 3 _.identity = function(value) {
 4   return value;
 5 }
 6 _.memoize = function(func, hasher) {
 7   var memo = {};
 8   hasher || (hasher = _.identity);
 9   return function() {
10     var key = hasher.apply(this, arguments);
11     return hasOwnProperty.call(memo, key) ? memo[key] :
12       (memo[key] = func.apply(this, arguments));
13   };
14 }
15 
16 fib = _.memoize(fib);

Demo, kérdések