Теория: Set

Множество хоть и не используется так же широко, как массивы, но при этом в некоторых ситуациях являются очень полезными структурами данных. В этом уроке мы рассмотрим тип и структуру данных Set, который является реализацией математической структуры «множество».

Фильтрация

Предположим, что у нас есть один массив, в котором мы описываем стоп-слова. Это те слова, которые не должны попасть в выходной поток. Также есть массив с набором слов:

const stopWords = ['one', 'two', 'four']
const words = [
  'one', 'five', 'six', 'seven',
  'two', 'four', 'nine',
]

// Производим фильтрацию и исключаем те слова,
// которые находятся внутри стоп-слов — являются элементами списка
const result = words.filter(word => !stopWords.includes(word)) // Фильтруем то, что туда не входит

console.log(result)
// => [ 'five', 'six', 'seven', 'nine' ]

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

includes проверяет вхождение полным перебором массива. В итоге на каждой итерации filter будет срабатывать перебор массива stopWords.

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

• С использованием Map
• С использованием Set

Разберем их подробнее.

С использованием Map

Переделаем массив в Map, в котором ключ — это слово, а значение — это просто true:

const stopWords = { // or new Map()
  one: true,
  two: true,
  four: true,
}

const words = [
  'one', 'five', 'six', 'seven',
  'two', 'four', 'nine',
]

const result = words.filter(word => !stopWords[word])

console.log(result)
// [ 'five', 'six', 'seven', 'nine' ]

Здесь мы по сути используем объект JavaScript. В данном случае большой разницы нет. Остальное практически то же самое, только проверяем, входит ли значение в stopWords с помощью !stopWords [word]. И если у нас возвращается undefined, то отрицание возвращает нам истину, и слово туда не попадает.

Но есть еще один гораздо более интересный способ.

С использованием Set

По сути, в предыдущем примере мы использовали Map, как способ имитировать Set, то есть множество. Причем в нашем случае это множество неповторяющихся элементов.

И в JavaScript есть для этого специальный тип. Он работает практически так же, как и Map:

const stopWords = new Set(['one', 'two', 'four'])
const words = [
  'one', 'five', 'six', 'seven',
  'two', 'four', 'nine',
]

const result = words.filter(word => !stopWords.has(word))

console.log(result)
// [ 'five', 'six', 'seven', 'nine' ]

Здесь мы пишем new Set() и передаем в него массив. После этого формируется некоторая структура, в которой внутри эффективным образом разложены все элементы этого массива. Поэтому проверка на вхождение во множество не требует перебора всех элементов.

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

В итоге программа меняется в двух местах: в определении множества и в проверке через метод has(). Это интерфейсный метод объекта, который у нас получился после new Set(). В нем мы передаем слово, и делается очень быстрая проверка. В итоге мы получаем такой же результат, как и в предыдущих способах.

Интерфейс Set

Интерфейс у Set очень простой. Он принимает в конструкторе массив, который внутри себя раскладывает и сохраняет:

const set = new Set()

При этом у него есть возможность устанавливать и изменять массив в момент работы с ним:

set.add(5)
set.add('some text')

Здесь используется метод add() для добавления элемента.

Также у нас есть свойство size, которое позволяет проверить размер множества:

set.size // 2

Еще есть метод has(), который позволяет узнать, лежит ли что-то внутри или нет:

set.has(5) // true
set.has('some text') // true

И есть delete() для удаления. Метод принимает значение элемента, который нужно удалить:

set.delete(5)
set.has(5) // false

Обход

Set не является массивом, но его можно преобразовать в массив, используя такой подход:

const set = new Set([1, 2, 10, 10])

Array.from(set) // [ 1, 2, 10 ]

Здесь мы используем Array.from и передаем в него Set. На выходе у нас появляется массив.

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

Чтобы поработать с Set и обойти его, мы можем использовать следующие методы:

set.keys()
set.values()

// Здесь также можно использовать `forEach`, который есть и в `Map`
// Он позволяет проходить по значениям
set.forEach(value => console.log(value))

Выводы

В этом уроке мы рассмотрели тип и структуру данных Set, который является реализацией математической структуры «множество». Его интерфейс очень простой. Он принимает массив и раскладывает его на уникальные значения. Также у него есть возможность устанавливать и изменять массив в момент работы с ним, проверять размер элементов и узнавать, лежит ли что-то внутри.