Removing duplicates from an array quickly

Question

Array.prototype.unique = function() { var a = [], // uniques get placed into here b = 0; // counter to test if value is already in array 'a' for ( i = 0; i < this.length; i++ ) { var current = this[i]; // get a value from the original array for ( j = 0; j < a.length; j++ ) { // loop and check if value is in new array if ( current != a[j] ) { b++; // if its not in the new array increase counter } } if ( b == a.length ) { // if the counter increased on all values // then its not in the new array yet a.push( current ); // put it in } b = 0; // reset counter } this.length = 0; // after new array is finished creating delete the original array for ( i = 0; i < a.length; i++ ) { this.push( a[i] ); // push all the new values into the original } return this; // return this to allow method chaining } 

I'm expecting this to be a slow checker especially because there is no sorting first. I'm interested in improving my sorting abilities etc so I thought I would get an early review.

Answer 1

You can use the indexOf function to check if a value exists in an array. This would simplify your code greatly:

Array.prototype.unique = function() { var a = []; for ( i = 0; i < this.length; i++ ) { var current = this[i]; if (a.indexOf(current) < 0) a.push(current); } this.length = 0; for ( i = 0; i < a.length; i++ ) { this.push( a[i] ); } return this; } 

At the end you are replacing the array's content. It would be better to not mutate the original array, but to return the new array instead with unique elements:

Array.prototype.unique = function() { var a = []; for ( i = 0; i < this.length; i++ ) { var current = this[i]; if (a.indexOf(current) < 0) a.push(current); } return a; } 

The name a is a very poor choice. unique would have been better.

You should declare the loop variable i using let, to limit its scope to the current block, so the code becomes:

Array.prototype.unique = function() { var unique = []; for (let i = 0; i < this.length; i++) { let current = this[i]; if (unique.indexOf(current) < 0) unique.push(current); } return unique; } 

Finally, there is a much more elegant solution to this problem, using the reduce function:

Array.prototype.unique = function() { return this.reduce(function(accum, current) { if (accum.indexOf(current) < 0) { accum.push(current); } return accum; }, []); } 

UPDATE(to answer your follow-up question)

If you want the function to take a parameter to decide whether it should modify the original array, you could try something like this:

Array.prototype.unique = function(mutate) { var unique = this.reduce(function(accum, current) { if (accum.indexOf(current) < 0) { accum.push(current); } return accum; }, []); if (mutate) { this.length = 0; for (let i = 0; i < unique.length; ++i) { this.push(unique[i]); } return this; } return unique; } 

Answer 2

In the case where there are a few duplicates, your algorithm has \$\mathcal{O}(n^2)\$ runtime.

If Javascript would have a widely available Set

Which it unfortunately does not yet have then one could do a really fast implementation like this:

Array.prototype.unique = function() { return [...(new Set(this))]; } 

This would have been \$\mathcal{O}(n\cdot \log (n))\$ for a binary tree implementation or \$\mathcal{O}(n)\$ for a hash-based implementation.

Sorting and ditching order

If you sort the array first (as you suggested), you can then iterate over the array and copy the first element and then any remaining elements that differ from the previous element. This algorithm will have \$\mathcal{O}(n\cdot \log (n))\$ runtime. The sorting dominates the run-time here. For small lists, the code by Janos is adequate. If you want performance for large lists you really do need the sort.

This solution will not preserve order of elements but will have faster run time for larger lists:

Array.prototype.unique = function() { var sorted = this; sorted.sort(); return sorted.filter(function(value, index, arr){ if(index < 1) return true; else return value != arr[index-1]; }); } 

Answer 3

Here's an approach that utilises the fact that an object can also be used as a hashmap. The value of a is not used for any thing else than determine uniqueness

Array.prototype.unique = function() { var existing = {}, result = [], current; for ( i = 0; i < this.length; i++) { current = this[i]; if(!existing.hasOwnProperty(current)) { result.push(current); existing[current] = true; //any value will do } } return result; } 

This works in \$\mathcal{O}(n)\$ since it makes it possible to create the resulting array, while iterating over the original array. An algorithm based on sorting would likely have \$\mathcal{O}(n\cdot \log (n))\$.

That however doesn't necessarily mean that this implementation is faster, since the cost of inserting a value into the "hash" might be high enough, for some n to make this implementation slower. The strength lies in the simplicity