2
\$\begingroup\$

I am writting a program to remove the duplicate values from an array, is any way to optimize code by removing one loop?

var arr=[10,20,30,20,40,10],
newarr=[];
var foo=function(ele, index, array){
     match=array[index];
  for(var m in newarr){
  if(newarr[m]==match)
    return true;  
  }
  newarr.push(match);
};
arr.forEach(foo);
console.log(newarr);
\$\endgroup\$
1

3 Answers 3

4
\$\begingroup\$

Yes, there is.

Your current solution has a O(n²) runtime complexity which is worse then necessary.

By sorting the array and then only marching once, comparing only neighboring elements, extracting unique elements costs only O(n * log(n)).

var arr=[10,20,30,20,40,10];

function uniqueBySorting(array) {
  var sortedArray = array.slice().sort(function(a, b) {
    return a > b ? 1 : 0;
  });
  var result = [];

  result.push(sortedArray[0]);
  for (var i = 1, length = sortedArray.length; i < length; i++) {
    if (sortedArray[i] !== sortedArray[i - 1]) {
      result.push(sortedArray[i]);
    }
  }
  return result;
}

console.log(uniqueBySorting(arr));

However, that comes at the cost of loosing the sort order, which might not be desired. If the sort order matters, use a hashed set for remembering which elements you already encountered instead of the inner loop, so you finally end up with a O(n) complexity.

var arr=[10,20,30,20,40,10];

function uniqueWithObjectHashSet(array) {
  var hashSet = {}, result = [];
  array.forEach(function(element) {
    if (!element in hashSet) {
      newarr.push(element);
      hashSet[element] = true;
    }
  });
  return result;
}

console.log(uniqueWithObjectHashSet(arr));

Inserting elements into a hash set and looking them up requires only constant time, opposed to the linear time required for iterating over the target array.

Technically JS does not have any native hashset implementation, but lucky for you most JS engines tend to implement objects as hashsets internally (unless the JIT can identify properties with constant names), so you can abuse that behavior.

See Hashset in Javascript for more information on the last point.

Comparison of the HashSet implementation (including @hindmost's variant) to previous solutions: http://jsperf.com/cr-57581/7

Not surprising, all versions with nested loops are left far behind. As of April 2015, the hashSet version using Array.prototype.forEach is by far the fastest algorithm in Firefox. In Chrome with V8 however, the sorting based solution is much faster, most likely due to a more efficient implementation of Array.prototype.sort.

\$\endgroup\$
3
  • \$\begingroup\$ Can write the code, this theory will easier to understand with some example. \$\endgroup\$
    – fruitjs
    Apr 28, 2015 at 7:37
  • \$\begingroup\$ @user3534656 Code samples for O(n*log(n)) and O(n) variants added. No guarantees on the runtime of the latter solution though, it depends too much on how much additional book keeping the corresponding JS engine performs. \$\endgroup\$
    – Ext3h
    Apr 28, 2015 at 9:36
  • \$\begingroup\$ The hash solution won't handle a number of cases such as "1" vs 1 or arrays or objects etc \$\endgroup\$
    – megawac
    Apr 29, 2015 at 17:36
1
\$\begingroup\$

As @Ext3h pointed, you can use a hash object storing unique values from the original array which you can use to determine whether to add the current value from the original array to the result array. In this case you will have plain loop with O(n) complexity (apart from time of hash access).

var hash = {}, newarr = [];
for (var i = 0; i < arr.length; i++) {
    var v = arr[i];
    if (v in hash) continue;
    newarr.push(v);
    hash[v] = true;
}
\$\endgroup\$
1
  • \$\begingroup\$ I linked a jsperf in my awnser, including your version using the native for loop, and a refined version of mine removing the unnecessary .toString(). The good new is: Both solutions are faster than any other non-ES6 solution. The surprising part is: For larger arrays, Array.forEach beats the native for loop by factor 2 in Firefox. In Chrome V8 however, the more efficient implementation of Array.sort makes the sorting version faster for about every reasonable input size. \$\endgroup\$
    – Ext3h
    Apr 29, 2015 at 8:14
0
\$\begingroup\$

With ES5 support (IE9 and higher), you can use .filter() to do it concisely:

var newArr = arr.filter(function(element, index, originalArray) {
    return originalArray.indexOf(element) === index;
});

Let's explain:

  • arr.filter - Takes a filter function and returns a new array with only the items for which the filter function returned true.
  • function(element, index, originalArray) { - The filter function takes 3 arguments, and the engine loops over the array and fills them automatically for each item. The first is the current element, the second is the current index, and the third is always the original array.
  • originalArray.indexOf(element) === index; - indexOf returns the first time the passed item is found in the array. So if that's not equal to the current index, there's a duplicate, and we return false (so the element won't be found in the new array)
\$\endgroup\$
2
  • \$\begingroup\$ I don't think the O(n) statement holds: Complexity of Array.indexOf in Javascript So using indexOf basically results in the same O(n²) complexity as the naive solution, just written in a shorter form. \$\endgroup\$
    – Ext3h
    Apr 28, 2015 at 8:41
  • \$\begingroup\$ @Ext3h You're right! I've forgotten that indexOf is another O(n). My bad. corrected. \$\endgroup\$ Apr 28, 2015 at 8:43

Not the answer you're looking for? Browse other questions tagged or ask your own question.