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]

Cathycathyleen

why would dense be [3] instead of [undefined, 3, null]? 1 in sparse === true but 0 in sparse === false, so only the ones where you didn’t set values are really missing. if you want to do that, the answer is var dense = []; sparse.forEach(function(e) { dense.push(e) }), as this only loops over the existing items – Francisco

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]

Burlburlap

(a[i] !== undefined) is redundant as (a[i] != null) comprises both cases (null and undefined) – Amalburga

a[i] != null also matches all the other falsy stuff and I think needs to be corrected to !== , not removed. – Hardiman

a[i] != null does not “matches all the other falsy stuff”. It is try IFF a[i] is undefined or null. In this case if (a[i] !== undefined && a[i] !== null) is strictly equivalent to if (a[i] != null), and could be simplified. – Broddy

Answer 2

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.

Benildas

Answer 3

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]);

Baerl

No, those last two code snippets are not equivalent. The in operator checks whether a property exists whereas equality operators (==, !=, ===, !==) can tell you nothing about that. – Jutland

Your second code snippet will not do what the OP is after, in fact: it will give you [undefined, 3, null] for the array in the question. – Jutland

@TimDown I think you are refering to Charmander's first code snippet. – Cathycathyleen

@TimDown: I appear to have worded that ambiguously and I apologize. By "the above" I meant the original filter() example. I will correct it immediately. – Atlanta

@Ivan: The second last one then. Depends whether you count the one-liner using filter. – Jutland

@TimDown: In regards the second code snippet returning an incorrect value - it does not. The use of != as opposed to !== ensures that undefined is not included. – Atlanta

@Charmander the code snippet with if(i in sparse) returns [undefined, 3, null]. – Cathycathyleen

@Charmander: Yes, I specifically meant the one using the in operator. – Jutland

@TimDown: Yes, that's why I provided the alternative - I don't entirely agree that compacting a sparse array also means removing all undefined and null values within. – Atlanta

... but @Ivan, you are free to take that example out if you do not agree with that disagreement. – Atlanta

Answer 4

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

Horned

Answer 5

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.

Extraterrestrial

Answer 6

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");

Karlsbad