JavaScript

Что такое множество?

Это набор уникальных значений  —  ни одно из них не возникает дважды или более раз. Это единственное ограничение, которое делает множество значений множеством.¹

Какие операции мы на нем выполняем? Наиболее распространенные операции с элементом:

  • Добавление.
  • Удаление.
  • Проверка существования во множестве.

Массивы, объекты и множества ES6

В JavaScript до ES6 в качестве множеств использовали массивы и простые объекты. Сравним основные операции на них и множествах ES6:

Массивы:

let setA = ['a','b','c','d'];

// Удаление элемента 'd'
// Асимптотическое время выполнения: O(|setA|)
setA = setA.filter(element => element !== 'd');

// Добавление элемента 'e' в setA
// Асимптотическое время выполнения: O(|setA|)
setA = setA.filter(element => element !== 'e').push('e');

// Проверка, существует ли элемент 'b' в setA
// Асимптотическое время выполнения: O(|setA|)
console.log(setA.includes('b'));

Объекты:

let e = 'd'; // элемент для добавления
let setA = {'a': true, 'b': true, 'c': true, 'd': true};

// Удаление элемента 'd'
// Асимптотическое время выполнения: O(1)
setA = delete setA['d'];

// Добавление элемента 'e' к setA
// Асимптотическое время выполнения: O(1)
setA[e] = true;

// Проверка, существует ли элемент 'b' в setA
// Асимптотическое время выполнения: O(1)
console.log('b' in setA);

Множества ES6:

let e = 'd'; // элемент для добавления
let setA = new Set(['a', 'b', 'c']);

// Удаление элемента 'd'
// Асимптотическое время выполнения: O(1)
setA.delete('d');

// Добавление элемента 'e' к setA
// Асимптотическое время выполнения: O(1)
setA.add(e);

// Проверка, существует ли элемент 'b' в setA
// Асимптотическое время выполнения: O(1)
console.log(setA.has('b'));

Множества лаконичнее, но оправдывает ли это более сложную структуру данных?

Вот аргумент: для массивов надо вручную применять свойство уникальности, для объектов  —  структуру {‘element’: true,…}. Такой подход порождает ошибки, потому что необходимо обеспечить сохранение этого свойства в каждой части кода, которая взаимодействует со множеством.

Еще одним недостатком простых объектов является хранение только лишь строк. Однако это можно преодолеть, усложнив структуру данных. Но есть другие причины использовать множества ES6…

Сложные операции

При работе со множествами велика вероятность, что рано или поздно вы столкнетесь с ситуацией, в которой понадобятся более продвинутые операции, например:

  • Пересечение множеств A и B.
  • Объединение множеств А и B.
  • Является ли A подмножеством B.

С массивами и объектами они могут быть довольно сложными и медленными.

Массивы:

let setA = ['a', 'b', 'c', 'd'];
let setB = ['b', 'c', 'f'];
let setC = ['b', 'c'];

// Пересечение множеств setA и setB
// Асимптотическое время выполнения: O(|setA| * |setB|)
function intersection(setA, setB) {
  return setA.filter(element => setB.includes(element));
}

// Объединение множеств setA и setB
// Асимптотическое время выполнения: O(|setB| * max(|setA|, |setB|))
function union(setA, setB) {
  let intersectionSet = intersection(setA, setB);
  return [
    ...setA,
    ...setB.filter(element => !intersectionSet.includes(element))
  ];
};

// Отношение подмножества
// Асимптотическое время выполнения: O(|setA| * |setB|)
function isSubsetOf(setA, setB) {
  return setA.every(element => setB.includes(element));
}

console.log('intersection', intersection(setA, setB)); // [ 'b', 'c' ]
console.log('union', union(setA, setB)); // [ 'a', 'b', 'c', 'd', 'f' ]
console.log('is setA subset of setB', isSubsetOf(setA, setB)); // false
console.log('is setB subset of setA', isSubsetOf(setB, setA)); // false
console.log('is setC subset of setA', isSubsetOf(setC, setA)); // true
console.log('is setC subset of setB', isSubsetOf(setC, setB)); // true
console.log('is setA subset of setC', isSubsetOf(setA, setC)); // false
console.log('is setB subset of setC', isSubsetOf(setB, setC)); // false

Объекты:

let setA = { 'a': true, 'b': true, 'c': true, 'd': true };
let setB = { 'b': true, 'c': true, 'f': true };
let setC = { 'b': true, 'c': true };

// Пересечение множеств setA и setB.
// Асимптотическое время выполнения: O(|setA| * |setB|)
function intersection(setA, setB) {
  let intersectionSet = {};
  Object.keys(setA).filter(element => element in setB).forEach(element =>
    intersectionSet[element] = true
  );
  return intersectionSet;
}

// Объединение множеств setA и setB
// Асимптотическое время выполнения: O(|setB| * max(|setA|, |setB|))
function union(setA, setB) {
  return { ...setA, ...setB };
};

// Отношение подмножества
// Асимптотическое время выполнения: O(|setA| * |setB|)
function isSubsetOf(setA, setB) {
  return Object.keys(setA).every(element => element in setB);
}

console.log('intersection', intersection(setA, setB)); // { b: true, c: true }
console.log('union', union(setA, setB)); // { a: true, b: true, c: true, d: true, f: true }
console.log('is setA subset of setB', isSubsetOf(setA, setB)); // false
console.log('is setB subset of setA', isSubsetOf(setB, setA)); // false
console.log('is setC subset of setA', isSubsetOf(setC, setA)); // true
console.log('is setC subset of setB', isSubsetOf(setC, setB)); // true
console.log('is setA subset of setC', isSubsetOf(setA, setC)); // false
console.log('is setB subset of setC', isSubsetOf(setB, setC)); // false

Связь с массивами

Раскроем полезную связь между множествами и массивами. Их можно преобразовывать друг в друга:

let arr = ['a', 'b', 'c'];

// преобразование массива во множество ES6
let es6Set = new Set(arr);

// преобразование множества в массив
arr = [...es6Set];

console.log(arr) // ['a', 'b', 'c']

Используя это, можно объединить простоту массивов со скоростью множеств ES6:

let setA = new Set(['a', 'b', 'c', 'd']);
let setB = new Set(['b', 'c', 'f']);
let setC = new Set(['b', 'c']);

// Пересечение множеств setA и setB
// Асимптотическое время выполнения: O(min(|setA|, |setB|))
function intersection(setA, setB) {
  let smallerSet = setA.size > setB.size ? setB : setA;
  let largerSet = setA.size > setB.size ? setA : setB;
  return new Set([...smallerSet].filter(element => largerSet.has(element)))
}

// Объединение множеств setA и setB
// Асимптотическое время выполнения: O(|setA| + |setB|)
function union(setA, setB) {
  return new Set([...setA, ...setB]);
};

// Отношение подмножества
// Асимптотическое время выполнения: O(|setA|)
function isSubsetOf(setA, setB) {
  return [...setA].every(element => setB.has(element));
}

console.log('intersection', intersection(setA, setB));
console.log('union', union(setA, setB));
console.log('is setA subset of setB', isSubsetOf(setA, setB));
console.log('is setB subset of setA', isSubsetOf(setB, setA));
console.log('is setC subset of setA', isSubsetOf(setC, setA));
console.log('is setC subset of setB', isSubsetOf(setC, setB));
console.log('is setA subset of setC', isSubsetOf(setA, setC));
console.log('is setB subset of setC', isSubsetOf(setB, setC));

Заключение

Множества ES6 сочетают в себе простоту массивов и скорость объектов и являются хорошим выбором для представления множествв JavaScript. Лёгкое преобразование в массивы и наоборот позволяет сочетать лучшее. Также они автоматически применяют свойство уникальности, что делает код надёжнее.

Множества не следует применять везде, но если нужно, чтобы массивы вели себя как множества, то преобразование можно легко совершить. Подробнее в документации.

¹В математике это ограничение не действует, но для прикладной информатики оно имеет большой смысл в отношении производительности. Большинство реализаций следуют этому определению.

Читайте также:

Читайте нас в Telegram, VK и Яндекс.Дзен

Перевод статьи Johannes Baum: Why You Should Use ES6 Sets in JavaScript

Предыдущая статьяВсё, что вы хотели знать об отладке в IntelliJ IDEA
Следующая статьяДизайн физического движка