current community

your communities

more stack exchange communities

Stack Exchange Inbox Reputation and Badges
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 3 down vote favorite

I have two different arrays:

var array1 = [
    {id: "foo", name: "Foo Smith"},
    {id: "caa", name: "CAA"},
    {id: "bar", name: "Bar Jones"},
    {id: "baz", name: "Baz Apple"},
    {id: "boo", name: "Boo Ghost"},
    {id: "dah", name: "DAH-123"}
];

var array2 = [
    {name: "bar", key1: false, key2: false, key3: "abcdef", id: "abc123"},
    {name: "foo", key1: true, key2: false, key3: "abcdef", id: "def456"},
    {name: "dah", key1: false, key2: true, key3: "abcdef", id: "jkl012"},
    {name: "doo", key1: false, key2: false, key3: "ghijkl", id: "mno345"},
    {name: "laa", key1: false, key2: true, key3: "ghijkl", id: "pqr678"},
    {name: "boo", key1: true, key2: true, key3: "ghijkl", id: "ghi789"},
    {name: "fib", key1: true, key2: false, key3: "abcdef", id: "stu901"}
];

And the following requirements:

Requirements:

  • Get the intersection of array1 and array2 based off of matching array1['id'] to array2['name']
  • Output needs to look like array1 with the following requirements:
    • key1, key2 and key3 need to be merged into array1 for intersecting objects
    • id of array2 needs to be mapped to new_id in array1
  • If no intersecting object, then defaultOptions need to be applied to array1

So that the output should look like:

$scope.outputArray = [
    {id: "foo", name: "Foo Smith", key1: true, key2: false, key3: "abcdef", new_id: "def456"},
    {id: "caa", name: "CAA", key1: false, key2: false, key3: null},
    {id: "bar", name: "Bar Jones", key1: false, key2: false, key3: "abcdef", new_id: "abc123"},
    {id: "baz", name: "Baz Apple", key1: false, key2: false, key3: null},
    {id: "boo", name: "Boo Ghost", key1: true, key2: true, key3: "ghijkl", new_id: "ghi789"},
    {id: "dah", name: "DAH-123", key1: false, key2: true, key3: "abcdef", new_id: "jkl012"}
];

What works:

var defaultOptions = {
    key1: false,
    key2: false,
    key3: null
};

var intersection = _.intersection(_.pluck(array1, 'id'), _.pluck(array2, 'name'));
var intersectionArr1 = _.sortBy(_.filter(array1, function(person) {
    return intersection.indexOf(person.id) >= 0;
}), 'id');
var intersectionArr2 = _.sortBy(_.filter(array2, function(person) {
    return intersection.indexOf(person.name) >= 0;
}), 'name');

_.each(intersectionArr1, function(person, idx) {
    _.assign(person, _.pick(intersectionArr2[idx], ['key1', 'key2', 'key3']));
    _.defaults(person, { new_id: intersectionArr2[idx].id });
});

var diff = _.difference(_.pluck(array1, 'id'), _.pluck(array2, 'name'));
var leftoverArr1 = _.filter(array1, function(person) {
    return diff.indexOf(person.id) >=0;
});

_.each(leftoverArr1, function(person) {
    _.defaults(person, defaultOptions);
});

$scope.newOutputArray = array1;

and here is the CodePen.

While this works, I'm looking for speed improvements. Both array will eventually be very large 50-100K.

Any help would be greatly appreciated.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

When you merge two arrays, where the one array contains a key value, you can save a lot of time by indexing the keys. Consider an index on the array2 name column.

It is really easy to index the data using an Object with named properties:

var indexed = {};

_.each(array2, function(data) {
  indexed[data["name"]] = data;
});

Now, we have a fast way to find any data record in array2 for a given name.

Using that structure becomes easy again, by looping for each of the array1 values, and updating them based on the value that was indexed, if any. Loop for each record, search in the index, use the default if the index value was not found.

To make the code a bit more flexible, and because the "column" names change from id to new_id, it helps to have a structure containing this column mapping:

var mapCols = {
  key1: "key1",
  key2: "key2",
  key3: "key3",
  id: "new_id"
}

The mapCol indicates that key1 should become key1, and so on, but id should become new_id.

This allows us to then make the "simple" nested loops:

_.each(array1, function(person){
  var use = indexed[person["id"]] || defaultOptions;
  _.each(mapCols, function(key) {
    person[mapCols[key]] = use[key];
  });
});

You can see this running here in your forked code.

In theory, this will turn your code from an \$O(n \times m)\$ operation to become an \$O(n + m)\$ one, where \$n\$ and \$m\$ are the sizes of the two arrays.

share|improve this answer
    
I knew there had to be a faster way, but it was eluding me. Thank you @rolfl ... this works beautifully and I very much appreciate your help! –  JulieMarie Sep 15 at 1:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.