Memoize like a boss (part 2)

Memoization is fun and if you read my previous post you should have fair idea of how memoization can be easily implemented in JavaScript. Previous examples were using very simple function and now you might wonder how to deal with recursion and still get all the benefits. Last time around we end up with:

Function.prototype.memoized = function(a) {
if (typeof this.cache === "undefined") this.cache = [];
if (this.cache[a]) {
return this.cache[a];
} else {
this.cache[a] = this(a);
return this.cache[a];
}
}

Function.prototype.memoize = function() {
var t = this;
return function() {
return t.memoized.apply(t, arguments);
}
}

myTest = (function superLongCalculation(someArg) {
    return someArg * 3;
}).memoize();

console.log(myTest(2));

So to recap.. myTest function once called will call memoized method on original function object t:

t.memoized.apply(t, arguments);

memoized method will do the check if the value for argument ("2" in our example) has already been precalculated and if so will returned whatever is stored in cache. Otherwise will call original function, do the magic and return new value. If this doesn't quite make sense have a look at my original post where I went into details of my basic memoization implementation.

So now you might wonder what will happen if instead of something overly simple as above we will use recursive function to do the work. Calculating fibonacci numbers seems to be "Hello World" of memoization and so lets plug this thing into our memoization code:

Function.prototype.memoized = function(a) {
if (typeof this.cache === "undefined") this.cache = [];
if (this.cache[a]) {
return this.cache[a];
} else {
this.cache[a] = this(a);
return this.cache[a];
}
}

Function.prototype.memoize = function() {
var t = this;
return function() {
return t.memoized.apply(t, arguments);
}
}

myTest = (function fibonacci(n) {
return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}).memoize();

console.log(myTest(2));

Works like a charm. Returns correct values, however we can make it better. It still does unnecessary work and given our current code there is easy way to improve it.

Notice how the fibonacci function object itself is memoized, however internal calls to itself are not. This means that in this case we do half-assed optimization only and anything half-assed is not cool. Lucky for us the Function object has memoized method already that we can directly call as in the very first examples in part one:

Function.prototype.memoized = function(a) {
if (typeof this.cache === "undefined") this.cache = [];
if (this.cache[a]) {
return this.cache[a];
} else {
this.cache[a] = this(a);
return this.cache[a];
}
}

Function.prototype.memoize = function() {
var t = this;
return function() {
return t.memoized.apply(t, arguments); }

}

myTest = (function fibonacci(n) {
return n < 2 ? n : fibonacci.memoized(n - 1) + fibonacci.memoized(n - 2);
}).memoize();

console.log(myTest(2));

I also put few tests that are available here so you can see the difference. I also realise that there are other, more efficient ways of calculating fibonacci numbers, I believe however that examples above are simple enough to see how memoization can be used with recursive functions.

Memoize like a boss!

Concept of memoization is not new. There is like a billion articles on the topic. Out of many, Resig covered it in his Secrets of JS Ninja book and Stefanov in his JavaScript Patterns. Addy Osmani blogged about performance of different memoization techniques and if you've been leaving under a rock and you are not familiar with it google is your firiend. There is a lot of good stuff out there so make sure you check it out. Long story short memoization is a method of caching the results of a function, you know, to make it faster.

Imagine that superLongCalculation() function takes a parameter and returns value of some sort.

function superLongCalculation(someArg)
{
  // some complicated stuff is happening here with someArg provided and only when done return result

  return result;
}

Now, wouldn't it be nice if the function, after doing all the work could remember what the result is for this particular argument? Next time when its called with the same argument it should be able to look it up and return it right away, without recalculating same thing again. This is fairly simple to implement, just look at my attempt in JS below:

function superLongCalculation(someArg) {
    return someArg * 3;
}

Function.prototype.memoized = function(a) {

    if (typeof this.cache === "undefined") this.cache = [];
    
    if (this.cache[a]) {
        return this.cache[a];
    } else {
        this.cache[a] = this(a);
        return this.cache[a];
    }
}

console.log(superLongCalculation.memoized(2));

For the sake of example I keep it simple. Calculation is not all that complicated and code is pretty much self explanatory. We simply extending Function object with additional method. This memoized method, once called with argument, will check internal array if there is a precalculated value for the argument we passed. If so then will return this precalculated value. Otherwise will call original function (this(a)), this function will do very long calculations and the new value will be returned. To call it we simply use:

superLongCalculation.memoized(2)

Easy stuff yet very powerful. Yes, I know, extending native JS prototypes is a bad idea in general blah blah blah.. IMO it is useful in certain situation and as long as you understand what you doing and possible problems that come with it I see no issue.

Ok, then I stumbled upon Secrets of JS Ninja by Resig. He further extended the method allowing memoization to be called directly on a function. Real brainfuck if you ask me. And very interesting one. It allows retrieving cached results directly out of a function:

  superLongCalculation(2)

To implement this we need to go a bit further however. The code I managed to put together is below and explanation of bits and pieces will follow:

Function.prototype.memoized = function(a) {
  
    if (typeof this.cache === "undefined")  this.cache = [];
    if (this.cache[a]) {
        return this.cache[a];
    } else {
        this.cache[a] = this(a);
        return this.cache[a];
    }
}

Function.prototype.memoize=function() {
  var t=this;
  return function() {
   return t.memoized.apply(t,arguments);
  }
}

myTest = (function superLongCalculation(someArg) {
    return someArg * 3;
}).memoize();

console.log(myTest(2));

memoized function stays as it is. As previously it takes parameter and checks cache for precalculated values.

So lets start with figuring out what each bit is doing:

myTest = (function superLongCalculation(someArg) {
    return someArg * 3;
}).memoize();

We simply creating a function here:

(function superLongCalculation(someArg) {
    return someArg * 3;
})

It takes argument, multiplies by 3 and returns. This is in fact Function object and as such has memoize method we attached to Function prototype:

Function.prototype.memoize=function() {
  var t=this;
  return function() {
   return t.memoized.apply(t,arguments);
  }
}

Further we have a call to memoize method:

.memoize();

This call will give us back another method that will do stuff later. So to sum it up from now on, when we call myTest, in fact we will call:

function() {
   return t.memoized.apply(t,arguments);
};

This method has access to function object we created earlier (t) and in turn calls memoized method on this very object. Everyone's following? Right, so now at some point in our program we get to call myTest and spit out result to console:

console.log(myTest(2));

So now myTest(2) calls:

function() {
   return t.memoized.apply(t,arguments);
}

t (via closure) refers to function object we created earlier. On this object we call memoized method with "2" passed as parameter. memoized method checks if value is in cache, if so returns it, otherwise calls original method and then returns the result. And so we have basic memoization implemented now.

Now, that was the easy part and it gets a bit more involving when you try to make superLongCalculations recursive. If anyone actually read this post I might put together few more examples with fibonacci numbers or something later, for today its enough however.

AngularJs custom directive trouble

So I decided to build very simple directive in AngularJs. Came up with this simple code:

<!doctype html>
<html>
  <head>
    <script src="https://ajax.googleapis.com/ajax/libs/angularjs/1.2.0/angular.js"></script>

    <script>

var app = angular.module('myApp', []);

      app.directive("taWithMessage",function() {
    return {
    template: "<p><h2>sample</h2></p>",
    replace: true
    };
   });

    </script>

  </head>
  <body>

    <div ng-app="myApp">

<div ta-with-message></div>

    </div>

  </body>
</html>

.. ran it and BOOM! Got this:

To make it more interesting replacing:

template: "<p><h2>sample</h2></p>",

with

template: "<p><span>sample</span></p>",

or:

template: "<div><h2>sample</h2></div>",

Worked just fine. It obviously didn't have anything to do with display of the element as div s well as p are both block, yet div works fine, p didn't. 

Then I started debugging and after a while I realised what a dummy I've been. Given original code, the browser was interpreting it as:

<p></p><h2>sample</h2><p></p>

This excerpt from specs should clarify what the issue was:

A p element's end tag may be omitted if the p element is immediately followed by an address, article, aside, blockquote, div, dl, fieldset, footer, form, h1, h2, h3, h4, h5, h6, header, hgroup, hr, main, nav,ol, p, pre, section, table, or ul, element, or if there is no more content in the parent element and the parent element is not an a element.

If you ever read the HTML specs you already know that some elements do not need to have closing end tags. I was well aware of this yet at this point didn't realised that was the issue. 

Decided to dig further into AngularJs source itself to see what exactly is going on in there and as it turned out innerHTML is the culprit:

AngularJs nicely passes template code to JQLite (highlighted in yellow below) and JQLite at some point runs it via innerHTML. This spits out modified as per above specs code. Then as shown below, AngularJs checks if the code is valid, so have one root only:

One root meaning:

<div><p>something</p><p>something else</p></div>

Rather than:

<p>something</p><p>something else</p>

As the code JQLite spits out is:

<p></p><h2>sample</h2><p></p>

It fails the check and Angular throws Error.

All this Googling and head scratching could be avoided if I only remembered the basic specs. Shame on me.. =/

(Mis)adventures with Zepto

I was blessed with a task of developing mobile version of existing site. “Easy” I thought as the site had decent HTML, CSS and decent JS code. After all I developed it ;). Module pattern kept things separated nicely, namespacing was in place and all the files in production were concatenated into one and minimized.

Then someone very smart suggested that as mobile site will not be Javascript heavy I should dump jQuery and go with lighter option Zepto. And so I did.

For those not familiar with Zepto, according to their website its:

Zepto is a minimalist JavaScript library for modern browsers with a largely jQuery-compatible API. If you use jQuery, you already know how to use Zepto.

Minimalist, sure, less than 10kb gzipped and largely compatible with jQuery. As I was writing JS from scratch it seemed like a great idea. Todays mobile browsers are quite capable anyway and I could do without fadeOut's and such.

Right, so I started developing. Code I developed for desktop version had bits that I could reuse in mobile site. Things like Cookies management, form validation and all this sort of stuff could (should) be reused and so I decided to put these bits into Common.js. In production, this Common.js file would be concatenated with desktop JS or mobile JS source depending on what device would make request. So far so good. Brilliant.

Only then I realized that these bits of code, sometimes contain functionality that is supported by jQuery, but not by its lighter brother (sister?) Zepto.

As you might expect effects like:

$("div p").fadeOut(3000)

Will not work. To be honest there was no need for that. Most of these can be done with CSS transitions anyway so it’s not a biggy. But then I noticed few other things didn't quite behave as expected. This was a bit worrying as not being familiar with Zepto I couldn't pick these up just by looking at the code. E.g. using some of the selectors was causing trouble:

$("div p:even")

As useful as this construct is with Zepto it will fail. There are few other, sometimes subtle differences. If you ever tried to clone element, jQuery provides very convenient “clone” method. In Zepto it seems to work just fine until you realize that it doesn't take optional argument that specifies if the event handlers should also be cloned. Element itself will be cloned, but you will have to attach events yourself somehow (or deal with these higher in DOM somewhere).

All in all Zepto is really nice and does most of the stuff. However if you have existing code that might not be worthwhile spending time modifying it just so it works with Zepto. There is always a risk that something might not work as expected and the behavior of “clone” method is the best example. After all, jQuery 2 is around 30kb gzipped and in most cases size is not so much of an issue. If it is however make sure you test everything when migrating to Zepto to avoid painful surprises.

By value or reference?

In JavaScript writing functions is easy. No need to declare return type, no need for argument types, In fact you don't even need to declare arguments! One might argue if all this freedom is actually a good thing. Freedom or not, it is important to understand the JS very basics and understand if what we pass into functions is passed by value or reference.

If you are familiar with Java the behaviour in JS will make sense to you. For all those confused however about how arguments are passed into functions I put together quick example that I hope is self explanatory. Consider the code:

var a = 100,
    b = "Homer",
    c = {
        firstName: "Homer"
    },
    d = {
        firstName: "Homer"
    },
    e = {
        firstName: "Homer"
    },
    f = {
        firstName: "Homer"
    }

function changeName(a1, a2, a3, a4, a5, a6) {
    a1 = 200;
    a2 = "Bart";
    a3.firstName = "Bart";
    a4 = {
        firstName: "Bart"
    };
    delete a5.firstName;
    delete a6;
}

changeName(a, b, c, d, e, f);

// output

console.log("a1:"+a); // 100
console.log("a2:"+b); // Homer
console.log("a3:"+c.firstName); // Bart
console.log("a4:"+d.firstName); // Homer
console.log("a5:"+e.firstName); // undefined
console.log("a6:"+f); // object

Ok, a and b are primitive types and these are obviously passed by value. References to objects are also passed by value. Confused? Let me explain..

Lets start with c, its a3 inside of function. Its an objects reference passed into a function. Inside we modify its property and it does modify original object c that a3 references.

Now d, a4 argument inside the function. Again reference to object with firstName property "Homer" is passed (by value) into a function as a4 argument. Inside the function we assign other object to a4 argument. From now on a4 is a reference to different object. Modify it all you want, d from outside won't be touched.

e and f are straightforward really. In case of a5 reference to firstName is deleted and in case of a6 the a6 reference pointing to original object is deleted. Original object stays however and can be accessed by still existing reference f from outside of function.

Understanding of all this is pretty fundamental I believe and getting it wrong might result in bugs and confusion. Luckily for us all its also fairly easy concept to grasp and as easy to experiment with.

jQuery and Array-like objects in JavaScript

JavaScript with its closures, prototypal inheritance etc. is not the easiest language to learn. Knowing certain topics is very important in effective writing and debugging JS code. I believe that Array-like objects is one of those concepts that everyone should get familiar with. Where can we find such thing? arguments accessible inside of functions is one example. jQuery returns such animal when you call $(“someSelector”). It looks like Array, behaves (in some cases) like Array, but its not Array. Try:

var a={},b=$(“div”), c=[],d=new Array();

a instanceof Array // outputs false (duh..)
b instanceof Array // outputs false
c instanceof Array // outputs true
d instanceof Array // outputs true

c and d are arrays, a and b not so much though. a is self explanatory, its an object literal. b is Array-like object jQuery returns.

As a is furthest from what Array should look like lets try to make it closer to what arrays are. Start from beginning and attach few properties to it e.g.:

a={ 1:”first”, 2:”second”};

Now calling (e.g. in Chrome dev tools):

a

Will output:

Object {1: "first", 2: "second"}

And calling:

a[1] // outputs first

a[2] // outputs second

However:

a.length

Outputs:

undefined

And for a good reason. It is still plain object and length property doesn't exists. Ok, so lets fake it till we make it and lets add:

a.length=2;

Now calling a from console will output:

Object {1: "first", 2: "second", length: 2}

True Arrays also have number of methods so lets add some and see what happens:

a.push=function() {}

Outputs:

Object {1: "first", 2: "second", length: 2, push: function}

Not much change. The trick lies in splice method. Simply add:

a.splice=function() {}

and voila! Calling a will output:

[undefined × 1, "first"]

Now, look at our original object. Its missing “0” element hence undefined in output above. Also “second” is missing as our length was set to 2 only.

Now, can we make it even more Array-like? Sure we can! Our splice and push implementations are empty so lets fill one in, e.g.:

a.push=function(el) {
// here you can extend implementation or not, then we call Arrays push
Array.prototype.push.call(this,el);
}

Now try:

a.push(“third”);

And call:

a

Result will be:

[undefined × 1, "first", "third"]

Calling a.length will return:

3

So third element was added to our fake array. Even length property increased by one. Hows that for array? :)

All good. We got ourselves Array-Like object. a instanceof Array will still return false, but its close.

As you see jQuery isn't using any sort of black magic, and I hope this gives you better understanding of Array-like objects that you often see in JavaScript. This is only the beginning however and if you are brave and want to learn more there is no better way then try it for yourself e.g. play around with a.__proto__=[].__proto__ and var b={};b.__proto__.{}.__proto__ and such. Or try removing splice from jQuery Array-like object or .. ok I better stop now but TRY, all these are fun too!

Testing window.scroll with QUnit/Jasmine

So you have to write set of tests for your code. Lets say it modifies evilGlobal variable when window is scrolled past certain point, e.g.:

var evilGlobal=false;

$(window).on("scroll.singleJob", function(e) {

if (window.scrollY > 100) 

{

evilGlobal = true;

 }

});

Say you using either QUnit or Jasmine (I will provide examples for both) to write your tests and so you got yourself nice fixture setup:

<div style="padding-top: 0px;height: 20000px;">

        Very tall content

</div>

HTML seems straightforward so you put your test together in no time. Using QUnit it might look something like:

test("sets evil to true", function() {

window.scroll(0, 1000);

ok(evilGlobal, "test 1 was great success!!!");

});

Jasmine version:

it("sets evil to true", function() {

window.scroll(0, 1000);

expect(evilGlobal).toBeTruthy();

});

You run the test and it fails miserably. You called window.scroll(0,1000) but the callback will not be executed immediately. It will be put in tasks queue that every browser maintains (I wrote a post on tasks queues a while ago). As Javascript is single threaded the callback will have to wait till current thread is finished. So as our thread continues, the ok assertion that follows will be executed before the callback will have a chance to modify our evil variable. The interesting part is that the browser will however change the window.scrollY position and so if you call window.scrollY you will get 1000. 

Knowing that, the solution is simple. Simply trigger the handler manually and as we already using jQuery, trigger method will do the trick. QUnit code:

test("sets evil to true", function() {

window.scroll(0, 1000);

 $(window).trigger("scroll");

ok(evilGlobal, "test 1 was great success!!!");

});

Jasmine version:

it("sets evil to true", function() {

window.scroll(0, 1000);

 $(window).trigger("scroll");

expect(evilGlobal).toBeTruthy();

});

Why does it work? As the scrollY of the window is already updated all we need is to execute our callback. Trigger function of jQuery is called synchronously setting our variable to true so its ready for our assertion.