Программирование на языке Ruby - Хэл Фултон

Математические множества можно, как мы видели, моделировать с помощью массивов. Но в последних версиях Ruby есть также класс Set, который хорошо поддерживает эту структуру.

Стеки и очереди — две весьма распространенные в информатике структуры данных. В первом издании этой книги им было уделено чрезмерно много внимания. Для тех, кого интересуют общие вопросы, я оставил кое-какой материал; для остальных есть немало великолепных книг по структурам данных и алгоритмам.

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

Граф — это обобщение понятия дерева. Граф представляет собой множество вершин, соединенных ребрами, причем с каждым ребром может быть связан вес или направление. Они полезны для решения многих задач, в том числе при анализе сетей и организации знаний.

Но самыми простыми структурами являются множества. С них мы и начнем.

9.1. Множества

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

Чтобы получить в свое распоряжение класс Set, достаточно написать:

require 'set'

При этом также добавляется метод to_set в модуль Enumerable, так что любой перечисляемый объект становится возможно преобразовать в множество.

Создать новое множество нетрудно. Метод [] работает почти так же, как для хэшей. Метод new принимает в качестве необязательных параметров перечисляемый объект и блок. Если блок задан, то он выступает в роли «препроцессора» для списка (подобно операции map).

s1 = Set[3,4,5]                 # В математике обозначается {3,4,5}.

arr = [3,4,5]

s2 = Set.new(arr)               # То же самое.

s3 = Set.new(arr) {|x| x.to_s } # Множество строк, а не чисел.

9.1.1. Простые операции над множествами

Для объединения множеств служит метод union (синонимы | и +):

x = Set[1,2,3]

y = Set[3,4,5]

а = x.union(y) # Set[1,2,3,4,5]

b = x | y      # То же самое.

с = x + y      # То же самое.

Пересечение множеств вычисляется методом intersection (синоним &):

x = Set[1,2,3]

y = Set[3,4,5]

а = x.intersection(y) # Set[3]

b = x & y # То же самое.

Унарный минус обозначает разность множеств; мы обсуждали эту операцию в разделе 8.1.9.

diff = Set[1,2,3] - Set[3,4,5] # Set[1,2]

Принадлежность элемента множеству проверяют методы member? или include?, как для массивов. Напомним, что порядок операндов противоположен принятому в математике.

Set[1,2,3].include?(2) # true

Set[1,2,3].include?(4) # false

Set[1,2,3].member?(4)  # false

Чтобы проверить, является ли множество пустым, мы вызываем метод empty?, как и в случае с массивами. Метод clear очищать множество, то есть удаляет из него все элементы.

s = Set[1,2,3,4,5,6]

s.empty? # false

s.clear

s.empty? # true

Можно проверить, является ли одно множество подмножеством, собственным подмножеством или надмножеством другого.

x = Set[3,4,5]

y = Set[3,4]

x.subset?(y)        # false

y.subset?(x)        # true

y.proper_subset?(x) # true

x.subset?(x)        # true

x.proper_subset?(x) # false

x.superset?(y)      # true

Метод add (синоним <<) добавляет в множество один элемент и обычно возвращает его в качестве значения. Метод add? возвращает nil, если такой элемент уже присутствовал в множестве. Метод merge полезен, если надо добавить сразу несколько элементов. Все они, конечно, могут изменить состояние вызывающего объекта. Метод replace работает так же, как в случае со строкой или массивом.

Наконец, два множества можно сравнить на равенство интуитивно очевидным способом:

Set[3,4,5] == Set[5,4,3] # true

9.1.2. Более сложные операции над множествами

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

s = Set[1,2,3,4,5]

s.each {|x| puts x; break } # Выводится: 5

Метод classify подобен методу partition, но с разбиением на несколько частей; он послужил источником идеи для реализации нашей версии метода classify в разделе 8.3.3.

files = Set.new(Dir ["*"])

hash = files.classify do |f|

 if File.size(f) <= 10_000

  :small

 elsif File.size(f) <= 10_000_000

  :medium

 else

  :large

 end

end

big_files = hash[:large] # big_files - это Set.

Метод divide аналогичен, но вызывает блок, чтобы выяснить «степень общности» элементов, и возвращает множество, состоящее из множеств.

Если «арность» (число аргументов) блока равна 1, то метод выполняет вызовы вида block.call(а) == block.call(b), чтобы определить, принадлежат ли а и b одному подмножеству. Если «арность» равна 2, для той же цели выполняются вызовы вида block.call(a,b).

Например, следующий блок (с «арностью» 1) разбивает множество на два подмножества, одно из которых содержит четные числа, а другое — нечетные:

require 'set'

numbers = Set[1,2,3,4,5,6,7,8,9,0]

set = numbers.divide{|i| i % 2}

p set # #<Set: {#<Set: {5, 1, 7, 3, 9}>, #<Set: {0, 6, 2, 8, 4}>}>

Вот еще один, несколько искусственный пример. Простыми числами-близнецами называются простые числа, отличающиеся на 2 (например, 11 и 13); все прочие называются одиночными (например, 23). Следующий код разбивает множество на группы, помещая числа-близнецы в одно и то же подмножество. В данном случае применяется блок с «арностью» 2:

primes = Set[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

set = primes.divide{|i,j| (i-j).abs == 2}

# set is: #<Set: {#<Set: {23}>, #<Set: {11, 13}>,

#         #<Set: {17, 19}>,     #<Set: {5, 7, 3}>,

#         #<Set: {2}>,          #<Set: {29, 31}>}>

# Более компактно: {{23},{11,13},{17,19},{5,7,3}, {2},{29,31}}

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

Важно понимать, что класс Set не всегда требует, чтобы параметр или операнд также был множеством (если вам это кажется странным, вспомните обсуждение «утипизации» в главе 1). На самом деле большая часть методов данного класса принимает в качестве параметра любой перечисляемый объект. Считайте, что так и задумано.

Есть и другие методы, которые применяются в частности к множествам (в том числе все методы из модуля Enumerable). Я не стану рассматривать здесь такие методы, как flatten. Дополнительную информацию можно найти на сайте http://ruby-doc.org/ или в любом другом справочном руководстве.

9.2. Стеки и очереди

Стеки и очереди — это первые из встретившихся нам структур, которые, строго говоря, не встроены в Ruby. Иными словами, в Ruby нет классов Stack и Queue, в отличие от Array и Hash (впрочем, класс Queue есть в библиотеке thread.rb, которую мы еще будем рассматривать).

И все же в некотором смысле они встроены в Ruby. Ведь класс Array реализует всё, что нужно для того, чтобы рассматривать его как стек или очередь. Стек организован по принципу «последним пришел, первым обслужен» (LIFO — last-in first-out). Традиционный пример — стопка подносов на подпружиненной подставке в кафетерии: подносы кладутся сверху и сверху же снимаются.

Над стеком можно выполнять ограниченный набор операций. Как минимум операции заталкивания (push) и выталкивания (pop), то есть помещения в стек и извлечения из него. Обычно также предоставляется способ проверить, пуст ли стек, и исследовать верхний элемент, не извлекая его из стека. Но никогда реализация не позволяет получить доступ к элементу в середине стека.

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

Но можно без труда определить класс Stack так, что к элементам можно будет обращаться только законно. И мы покажем, как это сделать.