Condensing a sparse array in Javascript?

Question

I have an array of elements where the entries are sparse. How can I easily condense the sparse array into a dense array so that I don't have to keep checking for null and undefined values every time I loop through the data?

Here is some example data:

var sparse = [];
sparse[1] = undefined;
sparse[5] = 3;
sparse[10] = null;

var dense = sparseToDenseArray(sparse);
// dense should be [3]

Answer 1

In vanilla JS, works on all browsers:

function filt(a) { 
 var b = []; 
 for(var i = 0;i < a.length;i++) { 
  if (a[i] !== undefined && a[i] !== null) { 
   b.push(a[i]); 
  }
 } 
 return b; 
}

> filt([1,undefined,3])
[1, 3]

Answer 2

You can use filter() which is compatible with Firefox, Chrome, IE 9, Opera, and Safari web browsers.

According to David Flanagan, in Javascript: The Definitive Guide, an easy way of transforming a sparse array to a dense array is to use a filter on it like so:

var dense = sparse.filter(function (x) { return x !== undefined && x != null; });

This works since filter() skips missing elements and only returns true if x is not undefined or null.

If filter() is not supported, this will compact a sparse array:

var compacted = [];

for(var i = 0; i < sparse.length; i++)
    if(i in sparse)
        compacted.push(sparse[i]);

An exact equivalent of the filter() example is:

var compacted = [];

for(var i = 0; i < sparse.length; i++)
    if(sparse[i] != null)
        compacted.push(sparse[i]);

Answer 3

If you want to include underscore.js in your code, you can use the compact function on your array.

Answer 4

In ES2017 (ES8) this is as easy as Object.values(sparseArray)

For example:

const sparseArray = [, , 'foo', 'bar', , 'baz', ,];
const compactArray = Object.values(sparseArray);
console.log(compactArray);

Note though that this method only removes gaps, shifting down the indexes of existing array elements as required. It does not remove elements explicitly set to undefined or null.

Answer 5

I can't believe there is so limited answers in here. First of all i think there are better, faster solutions to condensing a sparse array. I guess a sparse array doesn't mean an array with holes of undefined items (What exactly is a dense array?). A sparse array should be an array where actually there are no keys exists other than the keys which belong to the existing but sparse values. So if we iterate over the keys we should be doing our job more efficiently and faster.

Ok i compiled a test below to show you the performance of several methods to condense a sparse array.

var ts = 0,
    te = 0,
sparse = new Array(10000000),
 dense = [];
[sparse[2499999], sparse[4999999], sparse[9999999]] = ["first one", "middle one", "last one"];

ts = performance.now();
dense = Object.keys(sparse).map(k => sparse[k]);
te = performance.now();
console.log(dense, "Okeys and map resulted in :" +(te-ts)+ "msecs");

dense = [];

ts = performance.now();
for (var key in sparse) dense.push(sparse[key]);
te = performance.now();
console.log(dense, "for in loop resulted in :" +(te-ts)+ "msecs");

dense = [];

ts = performance.now();
dense = sparse.filter(function (x) { return x !== undefined && x !== null; });
te = performance.now();
console.log(dense, "Array filter resulted in :" +(te-ts)+ "msecs");

dense = [];

ts = performance.now();
for (var i = 0, len = sparse.length; i < len; i++) sparse[i] !== undefined &&
                                                   sparse[i] !== null      &&
                                                   dense.push(sparse[i]);
te = performance.now();
console.log(dense, "For loop resulted in :" +(te-ts)+ "msecs");

Answer 6

filter is a JavaScript extension to the ECMA-262 standard; as such it may not be present in other implementations of the standard. You can work around this by inserting the following code at the beginning of your scripts, allowing use of filter in ECMA-262 implementations which do not natively support it. Reference : MDN.

A cross browser solution using filter

if (!Array.prototype.filter) {  // Add the filter method to the 'Array prototype' if it's not available
    Array.prototype.filter = function(fun /*, thisp*/) {
        var len = this.length >>> 0;
        if (typeof fun != "function") {
            throw new TypeError();
        }

        var res = [];
        var thisp = arguments[1]; 
        for (var i = 0; i < len; i++) {
            if (i in this) {
                var val = this[i];
                if (fun.call(thisp, val, i, this)) {
                    res.push(val);
                }
            }
        }
        return res;
    };
}

var sparse = [];
sparse[1] = undefined;
sparse[5] = 3;
sparse[10] = null;

dense=sparse.filter(function(a){ //Call the `filter` method
    return a!== undefined && a != null;
});

DEMO.