The other side of the moon

I use Yahoo!'s yui libraries a lot in my DHTML applications. I've found the combination of YAHOO.util.Dom.getElementsByClassName with YAHOO.util.Event.addListener to be particularly convenient for event attachment. It almost allows you to do true class based object oriented programming, though there are probably better methods to do that.

In any case, I like yui, and I use yui, and while working on one of my apps, I saw performance problems trying to add a large number of event listeners to input elements by class name. My initial implementation was something like this:

for each className:
    YAHOO.util.Event.addListener(
        YAHOO.util.Dom.getElementsByClassName( className, 'input', container ),
        'eventname',
        eventHandler
    );

The obvious bottleneck here was that getElementsByClassName was calling container.getElementsByTagName('input') and iterating through the elements once for each className. An O(n²) algorithm.

Even if getElementsByClassName cached the result of getElementsByTagName, that would not have made much difference because
that call is lightening fast compared to the iteration (over about 1200 elements).

My solution was to create a map of classes to event handlers, and write my own function that ran through the element loop only once to attach all events.

It works something like this:

var classHandlers = {
    "class1":{"click":[c1ClickHandler1, c1ClickHandler2], "change":c1ChangeHandler1}
    "class2":{"click":c2ClickHandler},
    "class3":{"keyUp":c3KeyUpHandler}
};

addListenersByClassName( classHandlers, "input", "my_container" );

function addListenersByClassName( classHandlerMap, tagName, container )
{
    container = YAHOO.util.Dom.get(container);
    if(!container)
    return false;

    var els = container.getElementsByTagName(tagName);

    for(var i=els.length-1; i>=0; i--)
    {
        if(els[i].className)
        {
            var classes = els[i].className.split(/ +/);
            for(var j=classes.length-1; j>=0; j--)
            {
                if(classHandlerMap[classes[j]])
                {
                    var handlerMap = classHAndlerMap[classes[j]];
                    for(var ev in handlerMap)
                    {
                        var handlers = handlerMap[ev];
                        if(typeof(handlers) == "function")
                            handlers = [handlers];
                        for(var k=handlers.length-1; k>=0; k--)
                        {
                            YAHOO.util.Event.addListener(els[i], ev, handlers[k]);
                        }
                    }
                }
            }
        }
    }
}

On the face of it, this looks like an O(n³) algorithm, but if you consider that the average values of j and k are 1.2 and 1.1 respectively (for my application), this really just reduces to an O(n) algorithm.

I suspect that for most applications, j (number of events to handle per element) would never cross 2, and the value of k (number of handlers per event per element) would not cross 1.

I did see significant performance improvements with this, however, IE is still dead slow in iterating through a list of elements.