Программирование на языке Ruby
вернуться

Фултон Хэл
Шрифт:

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

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
. Дополнительную информацию можно найти на сайтеили в любом другом справочном руководстве.

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

Стеки и очереди — это первые из встретившихся нам структур, которые, строго говоря, не встроены в Ruby. Иными словами, в Ruby нет классов

Stack
и
Queue
, в отличие от
Array
и
Hash
(впрочем, класс
Queue
есть в библиотеке
thread.rb
, которую мы еще будем рассматривать).

И все же в некотором смысле они встроены в Ruby. Ведь класс

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

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

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