Javascript - Quickly remove duplicates in object array

Question

I have 2 arrays with objects in them such as:

[{"Start": 1, "End": 2}, {"Start": 4, "End": 9}, {"Start": 12, "End": 16}, ... ]

I want to merge the 2 arrays while removing duplicates. Currently, I am doing the following:

array1.concat(array2);

Then I am doing a nested $.each loop, but as my arrays get larger and larger, this takes O(n^2) time to execute and is not scalable.

I presume there is a quicker way to do this, however, all of the examples I have found are working with strings or integers.

Any recommended algorithms or methods out there to make this faster?

They are not ordered arrays, but I could sort them if there is a way to make it faster via using 2 for loops with an incrementing index on each array. — Brandon
– Brandon, Commented Feb 1, 2013 at 16:24
You could get better performance by not using $.each as the array gets larger. — user400654
– user400654, Commented Feb 1, 2013 at 16:26
If the order does not matter, you are better of using objects {} then you could check the keys, which is just o(n). — Christoph
– Christoph, Commented Feb 1, 2013 at 16:26

Christoph · Accepted Answer · 2013-02-01 18:42:28Z

2

This answer bases on the assumption that the order does not matter and you can create unique keys from your objects.

You copy all n entries from the array a to an object c, creating a unique key, after that you copy all m entries from array b to that object (this will automatically eliminate the duplicates) and you are finished in O(n+m):

var a = [{"Start": 1, "End": 2}, {"Start": 4, "End": 9}];
var b = [{"Start": 4, "End": 9}, {"Start": 3, "End": 12}];

var c = {};
a.forEach(function(el){c[el.Start+".."+el.End] = el});
b.forEach(function(el){c[el.Start+".."+el.End] = el});

console.log(c);
// yields: {"1..2":{"Start": 1, "End": 2},"4..9":{"Start": 4, "End": 9},"3..12":{"Start": 3, "End": 12}}

This notation in this object is a bit redundant but you are extremely fast on merging the two arrays. Maybe this could be improved further.

edited Feb 1, 2013 at 18:42

answered Feb 1, 2013 at 16:45

Christoph

51.4k22 gold badges103 silver badges129 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Brandon Over a year ago

This was super fast. I tried the other listed algorithms and this one performed the quickest.

Halcyon · Accepted Answer · 2013-02-01 16:26:02Z

1

Sort the objects first, low to high. O(n log n) with quicksort.

Then you can make pruning algorithm that can take advantage of this sorting to loop through both arrays in one loop in O(2n).

The merge the original array and the pruned array.

Keep in mind though that objects in JavaScript have no order, you can't sort them. Convert to an array, keep references and sort that.

answered Feb 1, 2013 at 16:26

Halcyon

57.7k10 gold badges93 silver badges131 bronze badges

5 Comments

Felix Kling Over a year ago

Never heard of binary sort... do you mean quicksort? ;) en.wikipedia.org/wiki/Quicksort

Halcyon Over a year ago

Yes quicksort, I think this what most JavaScript implemenations use when you Array.sort

Christoph Over a year ago

Using objects would be superior, you could merge and eliminate duplicates in o(n) since the lookup is only o(1).

Halcyon Over a year ago

Objects use a HashMap, so O(log n) for a lookup I believe. OPs objects don't have a hash (although arguably - looking at the data - you could create one). This isn't always feasible though.

Christoph Over a year ago

Object Lookups are basically Dictionary lookups, using O(1).

Upgradingdave · Accepted Answer · 2013-02-01 16:36:54Z

I'm not as familiar with javascript, so not 100% sure this is doable (not sure about subtlties of comparing objects for equality, etc), but in java or other languages, something like this might work:

Iterate over first array.
For each element store into a "counter" hashmap where key is the object and value is the count.

After this first pass, you should have something like:

{{"Start": 1, "End": 2}:1, {"Start": 4, "End": 9}:1, {"Start": 12, "End": 16}:1, ... }

Then, iterate over the second array
For each element, lookup current element inside counter hashmap.
If the counter hashmap contains a key that matches the current element it's a duplicate
Otherwise, append to the first array.

Might be a tad faster than having to sort first (if it's possible to use objects as keys, that is)?

Collectives™ on Stack Overflow

Javascript - Quickly remove duplicates in object array

3 Answers 3

1 Comment

5 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related