jashkenas/underscore — pull request #1722 by gitMbar (2014-07-07 04:36:33+00:00)
Title: uniq: Optimize time complexity for unsorted arrays

Underscore is a fantastic open source library adding key functionality to many other programs.
Because of its popularity, people who use this library expect the various functions to perform at optimal speed.

I propose a change to uniq which will bring the time complexity from polynomial to n*log(n) time.
Originally, the code contained a loop within a loop:
```sh
for (var i = 0, length = array.length; i < length; i++) {
var value = array[i];
if (iterator) value = iterator(value, i, array);
if (isSorted ? !i || seen !== value : !_.contains(seen, value)) {
if (isSorted) seen = value;
else seen.push(value);
result.push(array[i]);
}
}
```

The version on this branch uses the native sort function (which is either mergeSort or quickSort, depending on the browser) two times to bring down the time complexity. The first time, it will sort by value to line up repeated values. After the repeated values have been removed, it will use .sort on the stored indices to return the array to its original order.

```sh
if (!isSorted) {
for (var i = 0, length = array.length; i < length; i++){
if (iterator) tuples.push([iterator(array[i], i, array), i]);
else tuples.push([array[i], i]);
}
tuples.sort(function(a,b){ return a[0] > b[0] ? 1 : -1; });
}
for (var i = 0, length = array.length; i < length; i++) {
var value = isSorted ? array[i] : tuples[i][0];
if (!i || seen !== value) {
seen = value;
result.push(isSorted ? array[i] : tuples[i]);
}
}
if (!isSorted) {
result.sort(function(a,b){ return a[1] > b[1] ? 1 : -1; });
var length = result.length;
for (var i = 0; i < length; i++){
result.push(array[result[i][1]]);
}
result = result.slice(length);
}
```
The original code has been maintained as much as possible to minimize the extra length of the function.
In the future, a better programmer than I could probably make this code even shorter.

This code passes all of the built-in tests.