Поговорим о наборах

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

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

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

Что такое набор?

set - это структура данных, которая содержит любое количество неупорядоченных уникальных значений. Вы можете думать о set как о списке / коллекции элементов. Если вы знакомы с arrays, вы можете подумать: «О! Прямо как массив! » В некотором смысле да, это похоже на массив, но есть несколько отличий, которые мы обсудим позже в этом посте.

Когда я сказал уникальный, я имел в виду, что set не допускает дублирования элементов. Чтобы погрузиться немного глубже, предположим, что у нас есть список чисел: 1, 2, 3, 4. Если бы мы работали с set и хотели бы добавить в этот список, он не добавил бы число 1, 2, 3, or 4 снова, потому что они уже существуют в списке.

На каких языках используются наборы?

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

C++
"Джава"
Питон
C # /. NET
"Рубин"
JavaScript
"Быстрый"

Теперь имейте в виду, что могут быть другие языки программирования, которые используют эту структуру данных, поэтому, если вас интересует конкретный язык, которого нет в списке выше, просто зайдите в свой веб-браузер и выполните поиск!

Наборы против массивов

Ранее я упоминал о том, что set чем-то похож на array, поэтому давайте продолжим и обсудим некоторые из самых больших сходств и различий.

Сходства

Оба sets и arrays представляют собой набор / список элементов.
У нас есть возможность добавлять и удалять элементы из обеих структур данных.
Мы можем искать в каждом типе определенный элемент.

Примечание. Существуют и другие похожие методы, которые можно использовать как для sets, так и для arrays, но я не собираюсь обсуждать каждый из них. Не стесняйтесь ссылаться на мой список источников в конце статьи или потратьте некоторое время на поиск в Google, Bing и т. Д. Самостоятельно.

Отличия

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

Когда бы вы использовали набор?

Вы можете использовать set, когда ваша конечная цель - создать список / коллекцию, включающую только уникальные значения. Во многих языках, таких как Ruby и JavaScript, вы даже можете взять array, из которого хотите удалить дубликаты, и превратить его в набор. Затем вы можете взять этот набор и превратить его обратно в массив без этих дублированных элементов, если array - это то, что вам нужно в качестве конечного продукта.

На многих языках поиск чего-либо в set выполняется быстрее, чем в array. Например, в Ruby использование .include?() на set в 11 раз быстрее, чем использование .include?() на array. Я считаю, что это очень важно, и это отличный пример использования sets для больших наборов данных.

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

Из своего исследования я заметил, что Ruby, C # /. NET и Java имеют SortedSet. Если вам интересно, есть ли это на другом языке, просто поищите!

Последние мысли

В этой статье мы рассмотрели, что такое set, как он сравнивается с массивом и когда его использовать. Мне лично очень нравится идея sets, но я еще не реализовал ее самостоятельно, кроме интервью, о котором я говорил в начале этого поста.

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

Поговорим о наборах