JavaScript array deweighting, a commonplace problem, but this time is to unlock a variety of JavaScript array deweighting posture.

All of the following implementation algorithms are roughly tested using the following code:

const arr = [];
// Generate random numbers between [0, 100000]
for (let i = 0; i < 100000; i++) {
  arr.push(0 + Math.floor((100000 - 0 + 1) * Math.random()))
}

/ /... algorithm

console.time('test');
arr.unique();
console.timeEnd('test');
Copy the code

Double loop

Double loops are easier to reimplement. Implement a:

Array.prototype.unique = function () {
  const newArray = [];
  let isRepeat;
  for (let i = 0; i < this.length; i++) {
    isRepeat = false;
    for (let j = 0; j < newArray.length; j++) {
      if (this[i] === newArray[j]) {
        isRepeat = true;
        break; }}if(! isRepeat) { newArray.push(this[i]); }}return newArray;
}
Copy the code

To realize two:

Array.prototype.unique = function () {
  const newArray = [];
  let isRepeat;
  for (let i = 0; i < this.length; i++) {
    isRepeat = false;
    for (let j = i + 1; j < this.length; j++) {
      if (this[i] === this[j]) {
        isRepeat = true;
        break; }}if(! isRepeat) { newArray.push(this[i]); }}return newArray;
}
Copy the code

Based on the improved version of writing method of thought 2, three is achieved:

Array.prototype.unique = function () {
  const newArray = [];
  
  for (let i = 0; i < this.length; i++) {
    for (let j = i + 1; j < this.length; j++) {
      if (this[i] === this[j]) {
        j = ++i;
      }
    }
    newArray.push(this[i]);
  }
  return newArray;
}
Copy the code

The tested code was tested at the following time:

test1: 3688.440185546875ms
test2: 4641.60498046875ms
test3: 17684.365966796875ms
Copy the code

Array.prototype.indexOf()

Basic idea: If the index is not the first index, it is a duplicate value. Implement a:

  • Use the array.prototype.filter () filtering feature
  • Array.prototype.indexof () returns the first index value
  • Returns only the first occurrence of an element in the array
  • Anything that appears later will be filtered out
Array.prototype.unique = function () {
  return this.filter((item, index) = > {
    return this.indexOf(item) === index; })}Copy the code

To realize two:

let arr = [1.2.3.22.233.22.2.233.'a'.3.'b'.'a'];
Array.prototype.unique = function () {
  const newArray = [];
  this.forEach(item= > {
    if (newArray.indexOf(item) === - 1) { newArray.push(item); }});return newArray;
}
Copy the code

The tested code was tested at the following time:

test1: 4887.201904296875ms
test2: 3766.324951171875ms
Copy the code

Array.prototype.sort()

The basic idea: sort the array first, and then compare the elements. Implement a:

Array.prototype.unique = function () {
  const newArray = [];
  this.sort();
  for (let i = 0; i < this.length; i++) {
    if (this[i] ! = =this[i + 1]) {
      newArray.push(this[i]); }}return newArray;
}
Copy the code

The tested code was tested at the following time:

test: 4300.39990234375 msCopy the code

To realize two:

Array.prototype.unique = function () {
  const newArray = [];
  this.sort();
  for (let i = 0; i < this.length; i++) {
    if (this[i] ! == newArray[newArray.length -1]) {
      newArray.push(this[i]); }}return newArray;
}
Copy the code

The tested code was tested at the following time:

test1: 121.6259765625ms
test2: 123.02197265625ms
Copy the code

Array.prototype.includes()

Array.prototype.unique = function () {
  const newArray = [];
  this.forEach(item= > {
    if (!newArray.includes(item)) {
      newArray.push(item);
    }
  });
  return newArray;
}
Copy the code

The tested code was tested at the following time:

test: 4123.377197265625 msCopy the code

Array.prototype.reduce()

Array.prototype.unique = function () {
  return this.sort().reduce((init, current) = > {
    if(init.length === 0 || init[init.length - 1] !== current){
      init.push(current);
    }
    returninit; } []); }Copy the code

The tested code was tested at the following time:

test: 180.401123046875 msCopy the code

Object key-value pairs

Basic idea: the use of the key of the object can not be repeated to the characteristics of the deduplication. But note:

  • Cannot distinguish between an implicit type converted to the same value as a string, such as 1 and ‘1’
  • Cannot handle complex data types such as objects (because the object as the key becomes [object object])
  • Special data, such as ‘proto’, because the object’s proto property cannot be overridden

Solve the first and third problems to achieve the first:

Array.prototype.unique = function () {
  const newArray = [];
  const tmp = {};
  for (let i = 0; i < this.length; i++) {
    if(! tmp[typeof this[i] + this[i]]) {
      tmp[typeof this[i] + this[i]] = 1;
      newArray.push(this[i]); }}return newArray;
}
Copy the code

Solve the second problem to achieve the second:

Array.prototype.unique = function () {
  const newArray = [];
  const tmp = {};
  for (let i = 0; i < this.length; i++) {
    // Serialize using json.stringify ()
    if(! tmp[typeof this[i] + JSON.stringify(this[i])]) {
      // Serialize the object and use it as a key
      tmp[typeof this[i] + JSON.stringify(this[i])] = 1;
      newArray.push(this[i]); }}return newArray;
}
Copy the code

The tested code was tested at the following time:

test1: 113.849365234375ms
test2: 157.030029296875ms
Copy the code

Map

Implement a:

Array.prototype.unique = function () {
  const newArray = [];
  const tmp = new Map(a);for(let i = 0; i < this.length; i++){
        if(! tmp.get(this[i])){
            tmp.set(this[i], 1);
            newArray.push(this[i]); }}return newArray;
}
Copy the code

To realize two:

Array.prototype.unique = function () {
  const tmp = new Map(a);return this.filter(item= > {
    return! tmp.has(item) && tmp.set(item,1); })}Copy the code

The tested code was tested at the following time:

test1: 27.89697265625ms
test2: 21.945068359375ms
Copy the code

Set

Array.prototype.unique = function () {
  const set = new Set(this);
  return Array.from(set);
}
Copy the code
Array.prototype.unique = function () {
  return [...new Set(this)];
}
Copy the code

The tested code was tested at the following time:

test1: 36.8046875ms
test2: 31.98681640625ms
Copy the code

conclusion

In addition to consideration of time complexity, performance, and the data types of the elements of the array (for example, in the following example), choose which algorithm to use. For example:

const arr = [1.1.'1'.'1'.0.0.'0'.'0'.undefined.undefined.null.null.NaN.NaN, {}, {}, [], [], /a/, /a/];
Copy the code

After comprehensive consideration, the optimal algorithm of array deduplicating is realized by Map data structure.