Finding unique items in the array

Question

I was reading this code where author claims that its the fastest implementation which I doubt, hence I decided to write my version of the same problem.

'use strict';
module.exports = function unique(arr) {
 if (!Array.isArray(arr)) {
 throw new TypeError('array-unique expects an array.');
 }
 return arr.filter(function(element, index) {
 return arr.indexOf(element) === index;
 });
};

The above code looks readable to me but I don't about its performance(I think mine should be faster).

Answer 1

Your implementation is elegant, clean, easy to read.

The other is less so, but there is a significant difference between the two: your version returns a new array of unique values, the other removes duplicate values, modifying the input array.

Both algorithms are \$O(n^2)\$. Your implementation includes one redundant comparison per element: when the indexOf call reaches the current element, it compares it to itself, which is a redundant comparison for your ultimate intent of finding unique values. The other implementation optimized this with the var j = i + 1; step: it compares the current element to all subsequent element, never to itself.

In the end, the performance difference will come down to the implementation of splice and new array creation of the given JavaScript engine. I don't think such comparison will be very useful, except in very rare extreme cases. Also keep in mind that premature optimization is the root of all evil. And once again, there's also the matter of the different behavior of the implementations (return new unique array or mutate the parameter in-place), which makes comparisons problematic.

For what it's worth, in cases when an \$O(n^2)\$ solution to this problem is good enough (as opposed to an \$O(n)\$ solution using \$O(n)\$ extra space), I would go for your version, because it's intuitively easier to read.

• CodeYogi: Just out of curiosity redundant comparison with single element is that bad?
• janos: It's good to avoid redundant operations when possible, but not at all cost. Sometimes eliminating a redundant operation takes significant effort and the result is significantly more complex and hard to read.
• CodeYogi: As you know I have been greatly benefited by your answers, can you please recommend me some books which helped you most or you think may help me. I know its off topic but I am leaving it on you :)
• janos: Glad to help! Code Complete (2nd edition) by Steve McConnell is my bible =) It's a big book, if you're a bit impatient, then start with chapters 33, 3, 5, 6, 7, 20, 23, and then the rest.
• CodeYogi: Looking after my own solution after months, is it a good idea to pass a comparator function which checks equality of custom object on some key?