Editing Comparison of memoization implementations

This edit will create a new revision.

Your details (optional)

Name

Email (won’t be displayed; might be used for Gravatar)

URL

Test case details

Title *

Published (uncheck if you want to fiddle around before making the page public)

Description (in case you feel further explanation is needed)(Markdown syntax is allowed)

Are you a spammer? (just answer the question)

Preparation code

Preparation code HTML (this will be inserted in the <body> of a valid HTML5 document in standards mode) (useful when testing DOM operations or including libraries)

<script>
  //memo6 - by @madrobby/thomas fuchs
  
  Function.prototype.cached = function(){
    var self = this, cache = {};
    return function(arg){
      if(arg in cache) {
        //console.log('Cache hit for '+arg);
        return cache[arg];
      } else {
        //console.log('Cache miss for '+arg);
        return cache[arg] = self(arg);
      }
    }
  }
  
  
  //memo1
  //underscore.js implem
  
  //_.identity
  function identity(value) {
      return value;
  };
  
  //_.memoize
  function memoize1(func, hasher) {
      var memo = {};
      hasher || (hasher = identity);
      return function() {
        var key = hasher.apply(this, arguments);
        return hasOwnProperty.call(memo, key) ? memo[key] : (memo[key] = func.apply(this, arguments));
      };
    };
  
  
  //memoize.js - by @addyosmani
  // with tweaks from @philogb, @mathias, @DmitryBaranovsk, @JamieMason
  function memoize2(func) {
       "use strict";
       var cache = (func.memoize = func.memoize || {}),
           stringifyJson = JSON.stringify,
           sliceArray = Array.prototype.slice;
        return function () {
            var hash = stringifyJson(sliceArray.call(arguments));
            return (hash in cache) ? cache[hash] : cache[hash] = func.apply(this, arguments);
        };
    }; 
  
  //memo3 - unscriptables implem.
  function memoize3(func, context) {
      function memoizeArg (argPos) {
          var cache = {};
          return function () {
              if (argPos == 0) {
                  if (!(arguments[argPos] in cache)) {
                      cache[arguments[argPos]] = func.apply(context, arguments);
                  }
                  return cache[arguments[argPos]];
              }
              else {
                  if (!(arguments[argPos] in cache)) {
                      cache[arguments[argPos]] = memoizeArg(argPos - 1);
                  }
                  return cache[arguments[argPos]].apply(this, arguments);
              }
          }
      }
      // JScript doesn't grok the arity property, but uses length instead
      var arity = func.arity || func.length;
      return memoizeArg(arity - 1);
  }
  
  //memo4 - by stevenlevithan
  function memoize4(functor, expiration) {
  	var memo = {};
  	return function () {
  		var key = Array.prototype.join.call(arguments, "§");
  		if (key in memo)
  			return memo[key];
  		if (expiration)
  			setTimeout(function () {delete memo[key];}, expiration);
  		return memo[key] = functor.apply(this, arguments);
  	};
  }
  
  
  //memo5 - @gbradley
  
  function memoize5(fn){
  var lookup={};
  return function(){
  	var args=[].slice.call(arguments);
  	var key=JSON.stringify(args);
  	var result=lookup[key];
  	if (!result){
  		result=fn.apply(this,args);
  		lookup[key]=result;
  		}
  	return result;
  	};
  }
  
  // memo5 - @medikoo
  // https://github.com/medikoo/es5-ext/blob/master/lib/Function/memoize.js
  
  var memoize7 = (function () {
  	var isArray = Array.isArray
  	  , slice   = Array.prototype.slice
  
  	  , resolve;
  
  	resolve = function (args) {
  		return this.map(function (r, i) {
  			return r ? r(args[i]) : args[i];
  		}).concat(slice.call(args, this.length));
  	};
  
  	return function (fn, length, resolvers) {
  		var cache, resolver;
  		cache = [];
  		if (isArray(length)) {
  			resolvers = length;
  			length = fn.length;
  		} else if (length == null) {
  			length = fn.length;
  		}
  
  		resolver = resolvers ? resolve.bind(resolvers) : null;
  
  		return function () {
  			var limit, i, index, args, current, found;
  
  			args = resolver ? resolver(arguments) : arguments;
  			i = 0;
  			index = limit = (length === true) ? args.length: length;
  			current = cache;
  
  			if (limit === 0) {
  				found = current.hasOwnProperty(0);
  			} else {
  				while (i !== limit) {
  					if (!current[index]) {
  						current = (current[index] = [[args[i]], []]);
  						index = 0;
  					} else if (
  						(index = (current = current[index])[0].indexOf(args[i])) === -1) {
  						index = current[0].push(args[i]) - 1;
  						found = false;
  					} else {
  						found = current[1].hasOwnProperty(index);
  					}
  					current = current[1];
  					++i;
  				}
  			}
  			if (found) {
  				return current[index];
  			}
  			return current[index] = fn.apply(this, args);
  		};
  	};
  }());

function memoize8 (fn, cache) {
    cache = memoed._cache = cache || {}
    function memoed () {
      var args = JSON.stringify(Array.prototype.slice(arguments))
      if (!(args in cache)) cache[args] = fn.apply(this, arguments)
      return cache[args]
    }
    return memoed
  }
  
  var fib, fiborg;
  fiborg = fib = function (x) {
      if(x < 2) return 1; else return fib(x-1) + fib(x-2);
  }
  
</script>

Include JavaScript libraries as follows: <script src="//cdn.ext/library.js"></script>

Define setup for all tests (variables, functions, arrays or other objects that will be used in the tests) (runs before each clocked test loop, outside of the timed code region) (e.g. define local test variables, reset global variables, clear canvas, etc.) (see FAQ)

Define teardown for all tests (runs after each clocked test loop, outside of the timed code region) (see FAQ)

Code snippets to compare

Test 1

Title

Async (check if this is an asynchronous test)

Code

fib = memoize1(fiborg);
fib(20);

Test 2

Title

Async (check if this is an asynchronous test)

Code

fib = memoize2(fiborg);
fib(20);

Test 3

Title

Async (check if this is an asynchronous test)

Code

fib = memoize3(fiborg);
fib(20);

Test 4

Title

Async (check if this is an asynchronous test)

Code

fib = memoize4(fiborg, 1000);
fib(20);

Test 5

Title

Async (check if this is an asynchronous test)

Code

fib = memoize5(fiborg);
fib(20);

Test 6

Title

Async (check if this is an asynchronous test)

Code

fib = fiborg.cached();
fib(20);

Test 7

Title

Async (check if this is an asynchronous test)

Code

fib = memoize7(fiborg);
fib(20);