Sparse and Dense Arrays in JavaScript

Let's start with defining what dense and sparse arrays are. Let's assume we have an array with length 5. If the array is dense then the fact that it has length 5 means that the array actually contains five values in positions 0 through 4 of the array. These values may be undefined but they actually exist. If instead of being dense the array was sparse then that means that with length 5 the array contains fewer than 5 values. There is at least one position in the array (and possibly more than one) that don't exist at all.

Here are four arrays, two dense and two sparse so you can see the difference.

[1,2,3,4,5] // dense with actual values
[undefined,undefined,undefined,undefined,undefined] // dense with all values undefined
[,,3,,,] // sparse with one value
[,,,,,] // sparse with no values

Prior to the introduction of ECMAScript 5 it was not possible to distinguish between sparse and dense arrays in JavaScript. Using a for or while loop to process all the entries in the array is unable to distinguish between the second example above where we have a dense array with all values undefined and the fourth example where we have a sparse array with no values at all.

The new Array methods introduced in ES5 changed that. The forEach, map, filter, some, every,reduce and reduceRight methods only process those entries in an array that exist. Used with the dense array in the second example they would process all 5 entries whereas used with the sparse array in the fourth example they would recognise that there are no entries to process. This means that since these methods were introduced it is now possible to distinguish between sparse and dense arrays in JavaScript.

Now consider the following code:

Array.prototype.count = function() {
return this.reduce(function(a) {return a+1;}, 0);

Now this adds a count method to all our arrays that counts the number of entries that the array contains. Where the value returned by count() is the same as the length we have a dense array and where the count() is less than the length we have a sparse array. The length is 5 for all four of our examples above whereas the count() is 5, 5, 1, and 0 respectively.

So how do we distinguish between sparse and dense arrays when we are creating them? Lets take the second and fourth examples above but instead of a length of 5 we want a length of 500. Obviously we don't want to have to assign 500 individual values of undefined or even to have to type 500 commas (imagine if you counted wrong and had 499 or 501 instead of 500). Fortunately we don't have to do that as JavaScript provides an easy way to produce both of these arrays.

new Array(500):
Array.apply(null, Array(500));

The first of these creates a sparse array similar to the fourth of our above examples but with a length of 500 instead of 5. Using new Array with a single number as the parameter always creates a sparse array with the specified length but no entries. The second of these creates the second of our example arrays but with 500 undefined entries in it instead of 5. We always end up with a dense array when we use this variant. This means that we can create dense arrays of any length where the values in the array follow any sort of pattern at all by applying the map() method to this second variant to replace all the undefined values with ones defined via the pattern.


This article written by Stephen Chapman, Felgall Pty Ltd.

go to top

FaceBook Follow
Twitter Follow