Как использовать Set для повышения производительности вашего кода

JavaScript

Переводчик: Front-end Xiaozhi

оригинал:medium.com/@like ET Cam два часа…

Ставь лайк и смотри, поиск в WeChat【Переезд в мир】Обратите внимание на этого человека, который не имеет большого фабричного прошлого, но имеет восходящий и позитивный настрой. эта статьяGitHub GitHub.com/QQ449245884…Он был включен, статьи были классифицированы, и многие мои документы и учебные материалы были систематизированы.

Все говорили, что нет проекта для написания резюме, поэтому я помог вам найти проект, и это было с бонусом.【Учебник по строительству】.

Я уверен, что многие разработчики придерживаются базовых глобальных объектов: чисел, строк, объектов, массивов и логических значений. Для многих случаев использования они необходимы. Но если вы хотите сделать свой код максимально быстрым и расширяемым, этих примитивных типов не всегда достаточно.

В этой статье мы обсудимSetКак объекты делают код быстрее —   Особенно расширяемый.Arrayа такжеSetСуществует много совпадений в том, как все работает. но использоватьSetбыло бы лучше, чемArrayВыгоднее запускать код быстрее.

Чем отличается Сет

Самое принципиальное отличие состоит в том, что массив — это индексированная коллекция, а это значит, что значения данных в массиве отсортированы по индексу.

const arr = [A, B, C, D];
console.log(arr.indexOf(A)); // Result: 0
console.log(arr.indexOf(C)); // Result: 2

Напротив,setпредставляет собой набор ключей.setВместо индексов используйте ключи для сортировки данных.setЭлементы повторяются в порядке вставки, они не могут содержать повторяющихся данных. другими словами,setКаждый элемент должен быть уникальным.

Каковы основные преимущества

setЕсть несколько преимуществ перед массивами, особенно с точки зрения времени выполнения:

  • Просмотр элементов:использоватьindexOf()илиincludes()Проверка существования элемента в массиве выполняется медленно.

  • удалить элемент:существуетSet, может основываться наvalueчтобы удалить элемент. В массивах эквивалентным методом является использование индексации на основе элементов.splice(). Как и в предыдущем пункте, полагаться на индекс медленно.

  • сохранить NaN: нельзя использоватьindexOf()илиincludes()найти значениеNaN,а такжеSetЭто значение можно сохранить.

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

временная сложность?

Временная сложность метода поиска элементов массива равна0(N). Другими словами, время выполнения растет с той же скоростью, что и размер данных.

Напротив,SetВременная сложность поиска, удаления и вставки элементов метода составляет всегоO(1), что означает, что размер данных на самом деле не имеет ничего общего со временем выполнения этих методов.

Насколько быстр Сет?

Хотя время выполнения может сильно различаться в зависимости от используемой системы, размера предоставляемых данных и других переменных, я надеюсь, что результаты моего теста дадут вам реальное представление оSetскорость. Я поделюсь тремя простыми тестами и результатами, которые я получил.

Подготовьтесь к тесту

Прежде чем запускать какие-либо тесты, создайте массив и набор, каждый из которых содержит 1 миллион элементов. Для простоты я начну с0начать, считать999999.

let arr = [], set = new Set(), n = 1000000;
for (let i = 0; i < n; i++) {
  arr.push(i);
  set.add(i);
}

Тест 1: Найдите элемент

Мы ищем номера123123

let result;
console.time('Array'); 
result = arr.indexOf(123123) !== -1; 
console.timeEnd('Array');
console.time('Set'); 
result = set.has(123123); 
console.timeEnd('Set');
  • Array: 0.173ms
  • Set: 0.023ms

SetБыстрее7.54раз

Тест 2: Добавление элементов

console.time('Array'); 
arr.push(n);
console.timeEnd('Array');
console.time('Set'); 
set.add(n);
console.timeEnd('Set');
  • Array: 0.018ms
  • Set: 0.003ms

SetБыстрее6.73раз

Тест 3. Удаление элементов

Наконец, чтобы удалить элемент, поскольку у массивов нет встроенных методов, сначала создайте вспомогательную функцию:

const deleteFromArr = (arr, item) => {
  let index = arr.indexOf(item);
  return index !== -1 && arr.splice(index, 1);
};

Вот проверенный код:

console.time('Array'); 
deleteFromArr(arr, n);
console.timeEnd('Array');
console.time('Set'); 
set.delete(n);
console.timeEnd('Set');
  • Array: 1.122ms
  • Set: 0.015ms

SetБыстрее74.13раз

В целом мы видим, что использованиеSetЗначительно улучшенное время выполнения. увидеть ещеSetПолезные практические примеры.

Случай 1: Удалить повторяющиеся значения из массива

Если вы хотите быстро удалить повторяющиеся значения из массива, вы можете преобразовать его вSet. Это, безусловно, самый чистый способ фильтрации уникальных значений:

const duplicateCollection = ['A', 'B', 'B', 'C', 'D', 'B', 'C'];
// 将数组转换为 Set
let uniqueCollection = new Set(duplicateCollection);
console.log(uniqueCollection) // Result: Set(4) {"A", "B", "C", "D"}
// 值保存在数组中
let uniqueCollection = [...new Set(duplicateCollection)];
console.log(uniqueCollection) // Result: ["A", "B", "C", "D"]

Случай 2: Google Вопросы для интервью

вопрос:

Дан неупорядоченный массив целых чисел и переменныхsum, если в массиве есть любые два элемента и их сумма равнаsumзначение, возвратtrue. В противном случае вернитеfalse. Например, массив[3,5,1,4]а такжеsum = 9, функция должна вернутьtrue,потому что4 + 5 = 9.

отвечать

Хороший способ решить эту проблему — перебрать массив, создавSetСохраните относительную разницу.

когда мы встретимся3, мы можем положить6добавить вSet, потому что мы знаем, что нам нужно найти9а также. Затем всякий раз, когда мы касаемся нового значения в массиве, мы можем проверить, находится ли оно вSetсередина. при встрече5, добавьте 4 к набору. Наконец, когда мы наконец встретимся4, ты сможешьSetнайди, верниtrue.

const findSum = (arr, val) => {
  let searchValues = new Set();
  searchValues.add(val - arr[0]);
  for (let i = 1, length = arr.length; i < length; i++) {
    let searchVal = val - arr[i];
    if (searchValues.has(arr[i])) {
      return true;
    } else {
      searchValues.add(searchVal);
    }
  };
  return false;
};

Краткая версия:

const findSum = (arr, sum) =>
  arr.some((set => n => set.has(n) || !set.add(sum - n))(new Set));

потому чтоSet.prototype.has()Только временная сложностьO(1), поэтому использование наборов вместо массивов приводит к линейному времени выполнения для всего решения.O(N).

При использованииArray.prototype.indexOf()илиArray.prototype.includes()Их временная сложность O (N), общее время выполнения будетO(N²)Сколько!

Ошибки, которые могут существовать после развертывания кода, не могут быть известны в режиме реального времени.Чтобы решить эти ошибки впоследствии, много времени тратится на отладку журнала.Кстати, я рекомендую всем полезный инструмент мониторинга ошибок.Fundebug.

общаться с

Статья постоянно обновляется каждую неделю. Вы можете выполнить поиск «Big Move to the World» в WeChat, чтобы прочитать и обновить ее как можно скорее (на одну или две статьи раньше, чем в блоге). Эта статья находится на GitHub.GitHub.com/QQ449245884…Он был включен, и многие мои документы были разобраны. Добро пожаловать в Звезду и совершенство. Вы можете обратиться в тестовый центр для ознакомления во время собеседования. Кроме того, обратите внимание на паблик-аккаунт и ответьте в фоновом режиме.Благосостояние, вы можете увидеть преимущества, вы знаете.

Категории