Artful Code

HTML has no useful, built-in form widget for selecting from a large number of options. Some libraries offer Javascript-powered alternatives, but few of these are built to deal with more than a few hundred options.

The problem

I recently worked on a project with a backend using the Django admin library. It is a wonderful tool, but the filter interface is not equipped to deal with the thousands of options that were being populated in this particular form entry (a necessary parameter of the project.)

The Django filter interface would take 30 seconds or more to load the multi-select’s data on each form load, even on speedy computers. Moreover, the search filter breaks up queries at spaces, then performs a substring search for each token for every option in the select. Suffice it to say that this locked up more than a few browsers in our testing.

The solution

My first thought was to create my own search using a ternary tree or trie to index the data, but building these structures turned out to be extremely slow implemented in Javascript, taking even more time than the Django filter to initialize.

I ended up trying what seemed like a foolish idea. Create one large string to search by joining all of the options’ labels together (and delimiting with pipes). I assumed this would take a huge amount of memory, but in fact it took less than Javascript trees and was much faster than operating directly on DOM nodes. By delimiting the strings, a bounded regular expression could be used to perform reasonably fast searches of the data. There would be the need to identify the options to which the strings originated, for which I created a simple hash mapping option label to value.

This solution has two main problems – it assumes that all entries in the select box have both a unique label and a unique value, and no label can have a pipe in it. However, assuming that these conditions are met, this solution seems to work pretty speedily, and without overtaxing the browser.

The code

This code is implemented as a jQuery plugin. It hides the select and changes made to the widget automatically update the select. A search box and two lists are inserted into the document; the user enters a partial match in the search box and hits return. The first list is populated with the search results. Double-clicking on a result copies it into the second list.

Items that are already selected are automatically put into the second list. Regular expressions are permitted, and must be surrounded by forward slashes.

This module has been lightly tested in Firefox 2 and 3, Safari (latest), Opera (latest), and IE 7. A few concessions in favor of efficiency have been made at the expense of clarity (mainly for IE, which seems to have the slowest Javascript engine), primarily in the SelectMap constructor. jQuery’s each method and string concatenation proved to be too much for IE, so they were replaced with a for loop over the select node’s legacy options array. Iterative string building was replaced with Array.join, which is faster (but more expensive in memory) in IE.

To use it:

$(function() {
    var select = new BigSelect('target_id');
    // or...
    $('#target_id').bigSelect();
});

The code is available here. You can see a live example here.