Performance comparison of five array deduplication methods

Why write this article

When I interviewed an outsourcing programmer, I asked him to write a method of array de-duplication by hand. At that time, he used objects to save values and de-duplication through query.

I’m saying the table takes up space. Can I just operate on the array itself?

At that time, I thought of using indexOf and splice to operate arrays. When index was not equal to I, I used splice to delete elements. Later, I ran through the array and found that the execution time of the function was very long.

The method of deduplication is introduced

Outsourcing students write table query to heavy

// 
function unique1(arr) {
  let hash = {};
  let result = [];
  arr.forEach((num) => {
    if (!hash[num]) {
        hash[num] = 1; result.push(num); }});return result;
}
Copy the code

If the number traversed is not in the table, update the table and update the result array. Otherwise, skip

The advantage of this method is that it is more efficient, but the disadvantage is that it takes up more space. You can see that the extra space used is a query object and a new array

Set deduplication for ES6

function unique2(arr) {
  return Array.from(new Set(arr));
}
Copy the code

A new Set takes an array that needs to be duplicated. The Set automatically removes duplicate elements and returns the Set as an array.

The advantage of this method is higher efficiency, simple code, clear thinking, but the disadvantage is that there may be compatibility problems

Use filter to remove weight

function unique3(arr) {
  return arr.filter((num, index) => {
    return arr.indexOf(num) === index;
  });
}
Copy the code

Arr. IndexOf (num) = num (index); The principle is that indexOf returns the indexOf the first number found, assuming the array is [1, 1]. Using indexOf on the second 1 returns the index 0 of the first 1.

The advantage of this method is that operations on elements can be inserted at the time of de-weighting, which is highly extensible.

Returns a partial array after moving inside the array

function unique4(arr) {
  let right = arr.length - 1;
  for (let i = 0; i < arr.length; i++) {
    if (right <= i) {
      break;
    }
    if (arr.indexOf(arr[i]) !== i) {
      [arr[i], arr[right]] = [arr[right], arr[i]];
      right--;
      i--;
    }
  }
  return arr.slice(0, right);
}
Copy the code

If an element has appeared before, move the current element to the back of the list. Continue to iterate until all elements are iterated, and discard the elements that have been moved to the back.

This method uses less memory because it operates directly on arrays.

Use Reduce to remove weight

function unique5(arr) {
  return arr.reduce((pre, cur) => {
    if (pre.indexOf(cur) === -1) {
      pre.push(cur);
    }
    returnpre; } []); }Copy the code

Reduce is an iterative method of Array. The parameters are the return value of the last callback (pre), the current iterated element (cur), and the initial value. In this case, we pass an empty array as the initial value, and at each iteration, if we find no current element in Pre, we push the current element into Pre, and return pre to end the iteration.

It’s a fancy method.