7
\$\begingroup\$

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.

\$\endgroup\$

closed as off-topic by Jamal Jul 8 '17 at 5:35

This question appears to be off-topic. The users who voted to close gave this specific reason:

If this question can be reworded to fit the rules in the help center, please edit the question.

4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ 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! \$\endgroup\$ – JulieMarie Sep 15 '15 at 1:29

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