generic memoization approach in Javascript

Question

I understand that a number of generic memoized approaches rely on stringifying the argument list and using that as a key. E.g. as in:

Function.prototype.memoized = function() {
    this._values = this.values || {};
    var fn = this;
    return function() {
        var key = JSON.stringify( Array.prototype.slice.call(arguments) );
        if (fn._values[key]===undefined) {
            fn._values[key]=fn.apply(this, arguments);
        }
        return fn._values[key];
    };
};

This obviously fails when one tries to memoize a "member function" since one would have to also JSON-stringify the context as well, i.e. treat it as an implicitly passed parameter. But that wouldn't work very well when the context is the global object or something equally deep or subject to change in various ways not related with the function itself.

But even if we stick to non-"member functions" it may not always be possible to complete strigify the passed arguments list, right?

Three questions:

do I understand correctly that memoizing member functions in a generic way is non-sensical?
do I understand correctly that memoizing even non-member functions in a generic way is also impossible due to the inability / impracticability to fully stringify any conceivable argument list?
if 2 holds, then why do so many books and blogs try to define a generic memoize function in Function.prototype ? What's the point?

What do you mean "stringify the context"? If you mean the state of the object, then it is non-sensical. Memoization specifically works on arguments. — Mike Cluck
– Mike Cluck, Commented Feb 12, 2016 at 16:13
As for your second point, it's true that not all possible values can be stringified correctly but most of them can. However, memoization works by creating a unique identifier for a set of arguments. Stringifying is a common method for this but as long as you can create a unique identifier, you can memoize it. — Mike Cluck
– Mike Cluck, Commented Feb 12, 2016 at 16:16

score 1 · Accepted Answer · 2016-06-04 01:27:02Z

Methods are functions with this as a source of side effects. As you might know functions with side effects can't be memoized, since these effects don't depend on the method's argument list on which memoization relies on.

But there is a workaround of course. Instead of serializing the whole object (referenced by this), we can manually specify those properties of which the method is dependent:

function memoize(f, deps) {
  let cache = {};

  return function(...args) {
    let key = JSON.stringify([deps(), args]), v;
    return cache[key] || (v = f.apply(this, args), cache[key] = v, v);
  };
}

function Person(firstName, lastName) {
  this.firstName = firstName;
  this.lastName = lastName;

  this.fullName = memoize(
    function(title) { // memoized function
      console.log('memoizing...');
      return title + ' ' + this.firstName + ' ' + this.lastName;
    },
    function() { // dependencies
      return [this.firstName, this.lastName];
    }.bind(this));
}

let person = new Person('Jane', 'Doe');

// initial call
console.log(person.fullName('Ms.')); // memoizing...Ms. Jane Doe

// successive call
console.log(person.fullName('Ms.')); // Ms. Jane Doe

This is just a proof of concept, not a fully optimized and tested solution. All the credit goes to In Lehman's Terms

To your questions:

If a method is very expensive regarding its computation and thus justifies the effort, which entails the manual definition of its implicit dependencies (by this), then no, it may be useful
Yes, sometimes it is impossible, but why give up an almost generic solution entirely?
Dunno! Lemmings? :D

Collectives™ on Stack Overflow

generic memoization approach in Javascript

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related