Освоение структур данных в Ruby — наборы

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

Мы можем определить множества, используя нотацию множеств:

S = { 1, 2, 3 }

Обычный способ описания множеств — их операции и свойства:

Пустой

Множество без элементов является пустым множеством.

{} => true

Равный

Два множества равны, если они содержат одни и те же члены. (Помните, что в случае наборов порядок не имеет значения.)

{1, 2, 3} = {3, 2, 1} => true

Подмножество

Множество «а» является подмножеством «b», если «b» содержит все элементы, присутствующие в «а».

{3, 4} C {2, 3, 4} => true

Союз

Объединение множеств «a» и «b» дает множество «c», содержащее все элементы из «a» и «b».

{1, 2, 3} U {4, 5, 6} => { 1, 2, 3, 4, 5, 6 }

Пересекать

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

{1, 2, 3} N {2, 3, 4} => { 2, 3 }

Разница

Разность между двумя множествами — это множество, содержащее все элементы первого множества, кроме тех, которые присутствуют во втором.

{1, 2, 3} - {2, 3, 4} => { 1 }

Характеристики

• Пересечение множества с пустым множеством и есть пустое множество.
• Объединение множества «а» и пустого множества есть множество «а».
• Пересечение множества с самим собой является исходным множеством.
• Объединение множества с самим собой есть исходное множество.

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

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

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

• Большинство операций требуют (потенциально) пересечения двух наборов О (я).
• Мы должны гарантировать отсутствие обмана, который конвертировать традиционные операции O(1), такие как вставки, в операции O(n).

Устанавливает интерфейс

Далее следует краткое описание метода множеств и их сложности.

Имена методов, резюме и сложность.

Детали реализации

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

Мы также могли бы использовать хеш-таблицы, которые дали бы нам лучшую производительность вставки/удаления за счет немного более медленного полного сканирования. Как и в большинстве вещей в CS, все дело в компромиссах. Однако в целом односвязные списки лучше работают для небольших наборов.

Инициализировать

Единственное, что делает этот метод, — это инициализирует внутреннюю память набора. Сложность этого метода в том, О (1).

def initialize
  @list = LinkedList.new
end

Вставлять

Этот метод вставляет новый элемент в набор. Поскольку наборы не могут содержать дубликатов, первое, что делает этот метод, — это проверка того, не существует ли элемент уже. Если это не так, он вставляет новый член, иначе ничего не делает.

Так как мы должны проверить, есть ли член уже там, сложность этого метода На)

def insert member
  return if contains? member
  @list.insert member
end

Удалять

Этот метод удаляет элемент из текущего набора или ничего не делает, если элемент не существует.

Поскольку нам, возможно, придется пройтись по всему списку, сложность этого метода На).

def remove member
  node = @list.find { |nd| nd.value == member }
  @list.remove node if node
end

Союз

Этот метод возвращает набор, содержащий все элементы текущего и другого набора.

Эта операция включает в себя обход двух наборов, поэтому ее сложность О (я).

def union other
  res = Set.new
  @list.each { |nd| res.insert(nd.value) }
  other.each { |nd| res.insert(nd.value) }
  res
end

Пересекать

Этот метод возвращает пересечение текущего набора с другим набором.

Поскольку эта операция включает в себя обход двух наборов, ее сложность составляет О (я).

def intersect other
  res = Set.new
  @list.each do |nd|
    res.insert(nd.value) if other.contains?(nd.value)
  end
  res
end

Диф

Этот метод возвращает набор, содержащий все элементы, присутствующие в текущем наборе, но не в другом.

Как и при объединении пересечений, эта операция требует обхода двух множеств, что делает ее О (я).

def diff other
  res = Set.new
  @list.each do |nd|
    res.insert(nd.value) unless other.contains?(nd.value)
  end
  res
end

Содержит

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

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

def contains? member
  @list.find_first { |nd| nd.data == member }
end

Подмножество

Этот метод возвращает true, если текущий набор является подмножеством другого набора, и false в противном случае.

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

Если предыдущее условие неверно, вместо этого мы должны пойти по медленному пути и пройтись по всем элементам в текущем наборе.

Потенциально нам, возможно, придется пройти два подхода; поэтому сложность этого метода О (я).

def subset? other
  return false if self.count > other.count
  @list.each do |nd|
    return false unless other.contains(nd.value)
  end
  true
end

Равный

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

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

def equal? other
  return false if self.count != other.count
  subset? other
end

Считать

Этот метод возвращает количество элементов в текущем наборе. Сложность этого метода в том, О (1).

def count
  @list.length
end

Каждый

Этот метод просматривает элементы в текущем наборе, возвращая их по одному за раз. Сложность этого метода в том, На).

def each
  return nil unless block_given?
  current = @list.head
  while current
    yield current&.data
    current = current.next
  end
end

Распечатать

Этот метод печатает содержимое текущего набора. Сложность этого метода в том, На).

def print
  @list.print
end

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

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

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

Конечно, о наборах можно рассказать намного больше, но это краткое введение. Надеюсь, тебе понравилось!

В следующий раз, [Graphs] Следите за обновлениями!

Как обычно, вы можете получить исходный код отсюда.

Спасибо за чтение!. Надеюсь увидеть вас в следующий раз.

PS: если вы являетесь участником программы Kindle Unlimited, вы можете прочитать немного отполированную версию этой серии бесплатно на вашем устройстве Kindle.

Структуры данных с нуля — Ruby Edition.