Разблокируйте несколько поз дедупликации массива JavaScript

внешний интерфейс алгоритм JavaScript

Дедупликация массива JavaScript, старомодный вопрос, но на этот раз, чтобы разблокировать различные позы дедупликации массива JavaScript.

Все следующие алгоритмы реализации грубо протестированы с использованием следующего кода:

const arr = [];
// 生成[0, 100000]之间的随机数
for (let i = 0; i < 100000; i++) {
  arr.push(0 + Math.floor((100000 - 0 + 1) * Math.random()))
}

// ...实现算法

console.time('test');
arr.unique();
console.timeEnd('test');

двойная петля

Дедупликацию двойного цикла реализовать проще.
Реализация первая:

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;
}

Реализация вторая:

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;
}

На основе улучшенной версии метода записи второй идеи реализуем третью:

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;
}

Время, проверенное тестовым кодом, выглядит следующим образом:

test1: 3688.440185546875ms
test2: 4641.60498046875ms
test3: 17684.365966796875ms

Array.prototype.indexOf()

Основная идея: если индекс не является первым индексом, это означает, что это повторяющееся значение.
Реализация первая:

  • Используйте функцию фильтра Array.prototype.filter()
  • Array.prototype.indexOf() возвращает первое значение индекса
  • Возвращает только первое вхождение элемента в массив
  • После этого будет отфильтровано
Array.prototype.unique = function () {
  return this.filter((item, index) => {
    return this.indexOf(item) === index;
  })
}

Реализация вторая:

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;
}

Время, проверенное тестовым кодом, выглядит следующим образом:

test1: 4887.201904296875ms
test2: 3766.324951171875ms

Array.prototype.sort()

Основная идея: сначала отсортируйте исходный массив, а затем сравните элементы.
Реализация первая:

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;
}

Время, проверенное тестовым кодом, выглядит следующим образом:

test: 4300.39990234375ms

Реализация вторая:

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;
}

Время, проверенное тестовым кодом, выглядит следующим образом:

test1: 121.6259765625ms
test2: 123.02197265625ms

Array.prototype.includes()

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

Время, проверенное тестовым кодом, выглядит следующим образом:

test: 4123.377197265625ms

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);
    }
    return init;
  }, []);
}

Время, проверенное тестовым кодом, выглядит следующим образом:

test: 180.401123046875ms

Пары ключ-значение объекта

Основные идеи: использование ключевых характеристик объекта нельзя повторять повторно.
Но нужно обратить внимание:

  • Невозможно различить значения, которые неявно преобразованы в строки, такие как 1 и '1'
  • Не может обрабатывать сложные типы данных, такие как объекты (поскольку объекты в качестве ключей становятся [object Object])
  • специальные данные, такие как 'proto', потому что объектprotoСвойство не может быть переопределено

Чтобы решить первую и третью проблемы, реализуйте одну:

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;
}

Чтобы решить вторую проблему, осознайте две:

Array.prototype.unique = function () {
  const newArray = [];
  const tmp = {};
  for (let i = 0; i < this.length; i++) {
    // 使用JSON.stringify()进行序列化
    if (!tmp[typeof this[i] + JSON.stringify(this[i])]) {
      // 将对象序列化之后作为key来使用
      tmp[typeof this[i] + JSON.stringify(this[i])] = 1;
      newArray.push(this[i]);
    }
  }
  return newArray;
}

Время, проверенное тестовым кодом, выглядит следующим образом:

test1: 113.849365234375ms
test2: 157.030029296875ms

Map

Реализация первая:

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

Реализация вторая:

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

Время, проверенное тестовым кодом, выглядит следующим образом:

test1: 27.89697265625ms
test2: 21.945068359375ms

Set

Array.prototype.unique = function () {
  const set = new Set(this);
  return Array.from(set);
}

Array.prototype.unique = function () {
  return [...new Set(this)];
}

Время, проверенное тестовым кодом, выглядит следующим образом:

test1: 36.8046875ms
test2: 31.98681640625ms

Суммировать

В дополнение к рассмотрению временной сложности и производительности следует также учитывать тип данных элементов массива (например, в следующем примере), чтобы взвесить и выбрать, какой алгоритм использовать, например:

const arr = [1, 1, '1', '1', 0, 0, '0', '0', undefined, undefined, null, null, NaN, NaN, {}, {}, [], [], /a/, /a/];

После всестороннего рассмотрения оптимальным алгоритмом дедупликации массива является алгоритм, реализованный структурой данных Map.

Категории