Optimizing a nested for loop over JS array of objects

Question

NOTE: I'm bringing this question up in code review rather than stack overflow since I already have a working solution. I just am looking for ways to do it better.

I have two arrays. One is an array of simple strings (i.e. A1), while the other is an array of objects (i.e. A2). I need to pluck only those objects from A2, that have relevant keys present in A1.

Here is my implementation using a double for loop. It works, but is not elegant or efficient, I feel. How do I make this run better? Use of ext libraries such as underscore JS is allowed.

var A1  = ["1","2","3","4"];

var A2 = [
    {label:"one", value:"1"},
    {label:"two", value:"2"},
    {label:"three", value:"3"},
    {label:"four", value:"4"},
    {label:"five", value:"5"},
    {label:"six", value:"6"},
];

       var result = [];

       for(var i=0; i<A2.length; i++){
           for(var j=0; j<A1.length; j++ ){
               if(A1[i] == A2[j].value){
                   result.push( A2[j]);
               }
           }
       }   

The output of the above is :

result = [
    {label:"one", value:"1"},
    {label:"two", value:"2"},
    {label:"three", value:"3"},
    {label:"four", value:"4"},
]

Answer 1

As others have already mentioned, Array.prototype.filter() might be the simplest approach (or Array.prototype.reduce() could also be used but would require more conditional logic). It would typically be slower than the nested for loops because it would be adding additional function calls, but for small data sets it typically wouldn't be noticeable. For example, I did a search on Google for "jsperf filter nested loop" and found this jsPerf test.

Using Array.prototype.filter() on A2, pass a callback function that returns true when the value at property value is included in A1 by checking A1.indexOf() for a value greater than -1.

var result = A2.filter(function(o) {
    return A1.indexOf(o.value) > -1;
});

This can be simplified to a single line using an ES-6 arrow function and Array.prototype.includes() (Not supported by IE):

var result = A2.filter(o => A1.includes(o.value));

If you wanted to use Underscore.js, _.filter() and _.includes() could be used to filter out any object in A2 without a value for the value property contained in A1. Expand the snippet below for a demonstration.

var A1  = ["1","2","3","4"];

var A2 = [
    {label:"one", value:"1"},
    {label:"two", value:"2"},
    {label:"three", value:"3"},
    {label:"four", value:"4"},
    {label:"five", value:"5"},
    {label:"six", value:"6"},
];
var result = _.filter(A2, function(o) { return _.includes(A1, o.value);});
console.log('result', result);

<script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.8.3/underscore-min.js"></script>

There is an Underscore helper _.pluck() but that is used to collect a value from each item in a collection at a given property (similar to Array.prototype.map().

Lodash also has the same helpers: _.filter() and _.includes().

var A1  = ["1","2","3","4"];

var A2 = [
    {label:"one", value:"1"},
    {label:"two", value:"2"},
    {label:"three", value:"3"},
    {label:"four", value:"4"},
    {label:"five", value:"5"},
    {label:"six", value:"6"},
];
var result = _.filter(A2, function(o) { return _.includes(A1, o.value);});
console.log('result', result);

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js"></script>

Though some question whether libraries like lodash and underscore are really needed anymore. For a discussion on that, check out this article.

Answer 2

You can use some built in functions instead of the for loops.

var result = A2.filter(e => A1.includes(e.value));

I can't say if this is much faster, since those functions still loop through the arrays. You'll have to time this with some large input to test.

Be aware that Internet Explorer doesn't support .includes or arrow functions. IE friendly version:

var result = A2.filter(function(e) {return A1.indexOf(e.value) !== -1});

Answer 3

If you find yourself repeatedly searching an array for a string, a good idea is to convert the array to an object whose keys are those strings. Searching an array is \$O(n)\$, so your full algorithm is \$O(n^2)\$, but looking up a key in an object is \$O(1)\$.

var map_A1 = _.object(A1, _.times(A1.length, _.constant(true)));
var result = A2.filter(obj => map_A1[obj.value]);

Answer 4

The elegant way I'have found is to use filter function on array. Here is an es6 syntax

var result = A2.filter(e => {return A1.includes(e.value)});

Or with plain javascript:

 var result = A2.filter(function(e){
    return A1.includes(e.value);
});

Which produce the same result.

Answer 5

One of the more basic ways to streamline this is to create variables outside your loops for the A1.length and A2.length, presuming they don't change. It's a small alteration to your code, but prevents JS from having to do any overhead to count the array elements again every time you loop.

You also don't have to worry about including a library or compatibility issues, but who cares about IE anyway. ;-)