Search and Don’t Replace


Earlier today a friend of mine, Marc Grabanski, pinged me with a question: What’s the optimal way, in JavaScript, to convert a query string like “foo=1&foo=2&foo=3&blah=a&blah=b” into one that looks like this: “foo=1,2,3&blah=a,b”. He had already come up with a solution of his own and was curious as to if it could be improved upon.

I pondered this for a moment and came up with a solution:

function compress(data){
    var q = {}, ret = “”;
    data.replace(/([^=&]+)=([^&]*)/g, function(m, key, value){
        q[key] = (q[key] ? q[key] + “,” : “”) + value;
    });
    for ( var key in q )
        ret = (ret ? ret + “&” : “”) + key + “=” + q[key];
    return ret;
}

Besides being 10 lines shorter than Mark’s solution it also didn’t require the use of any libraries (his required the use of jQuery). He was especially surprised at my result – and the replace technique that I used, in particular. I want to outline two quick tricks that I used that some may not be familiar with.

Array Joining Without an Array

One step to solving the above problem is to collect together the various values associated with a key – joining them with a ‘,’. At first glance the obvious solution might be to construct an array for each key, push each of the values on, and then .join() the array results into a string. However all of this is both costly (the overhead of creating all these extra arrays) and verbose.

The alternative is one that I use twice in the program:

q[key] = (q[key] ? q[key] + “,” : “”) + value;

The key part is that we’re concatenating the value onto the q[key] string adding in an extra “,” if there’s nothing in the string already: q[key] ? q[key] + "," : "". If no existing value is in the key we seed it with an empty string, otherwise we’re simply merging on to the already-existing value along with the needed “,”.

The end result is that we’re only ever dealing with strings and string operations (instead of arrays) but achieving the result of joining a set of values without using an array.

Search and Replace Without Replacing

The second, and arguably more interesting, aspect is in using the JavaScript string replace function as a means of traversing a string for values, rather than as an actual search-and-replace mechanism. The trick is two-fold: Passing in a function as the replace value argument to the .replace() method and, instead of returning a value, simply utilizing it as a means of searching.

Let’s examine this piece of code:

data.replace(/([^=&]+)=([^&]*)/g, function(m, key, value){});

The regular expression, itself, captures two things: A key in the query string and its associated value. This match is performed globally, locating all the key-value pairs within the query string.

The second argument to the replace method is a function. It’s not uncommon to utilize this function-as-an-argument technique when attempting to replace matches with complex values (that is values that are dependent upon their associated matches). The function is called every time a new match occurs and it receives a variable number of arguments. The first argument is always the entire matched portion of the string and all remaining arguments are each of the (...) capturing blocks, in order. The return value of the function is injected back into the string as its replacement. In this example we don’t return a value from the function therefore we end up injecting the serialized “undefined” value, repeatedly, back into the string.

We can see this behavior here:

“a b c”.replace(/a/, function(){});
// => "undefined b c"
 

Now that we’ve collected all of our key values pairs (to be re-serialized back into a query string) the final step isn’t really a step at all: We simply don’t save the search-and-replaced data query string (which, most likely, looks something like "undefined&undefined&undefined").

In this manner we can use a string’s replace method as our very-own string searching mechanism. The result is, not only, fast but also simple and effective. Another excellent tool in your JavaScript toolbox.


This topic will be discussed, in depth, in my work-in-progress book: Secrets of the JavaScript Ninja. To be released Fall 2008.

Posted: March 14th, 2008


If you particularly enjoy my work, I appreciate donations given with Gittip.

42 Comments (Show Comments)



Comments are closed.
Comments are automatically turned off two weeks after the original post. If you have a question concerning the content of this post, please feel free to contact me.


Secrets of the JavaScript Ninja

Secrets of the JS Ninja

Secret techniques of top JavaScript programmers. Published by Manning.

Ukiyo-e Database and Search

Ukiyo-e.org

Japanese woodblock print database and search engine.


John Resig Twitter Updates

@jeresig

Infrequent, short, updates and links.


via Ad Packs