documentcloud/underscore — pull request #1050 by ebobby (2013-04-04 20:35:47+00:00)
Title: _.uniq made O(N) for every case.

_.uniq uses an O(N^2) algorithm when the passed array is unsorted. This PR is an optimization to make that algorithm O(N) instead. So basically, there's no difference anymore if the array is sorted or unsorted.

I use a dictionary (object) lookup (O(1)) to check if an element is already inside the results array as opposed to another array and contains. So the memory requirements should be around the same. (One boolean object per entry in the dictionary though).

I ran tests in Chrome, Firefox and Safari and this implementation is roughly 2 orders of magnitude faster than the regular one.

http://jsperf.com/uniq-performance

Also, this works fine for undefined or null entries in the array.

```javascript
>_.myuniq([ null, null, undefined, undefined ]) => [null, undefined]
> a = {}
> a[undefined] = 1
> a[null] = 1
> a => Object {undefined: 1, null: 1}
> a[null] === 1 > true
```