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

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

Иногда бывает нужен массив, в котором определена лишь небольшая часть элементов, а остальные не определены вовсе или (даже чаще) равны 0. Подобная разреженная матрица потребляет так много памяти зря, что были найдены способы более изощренной ее реализации.

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

С другой стороны, присваивание значения элементу массива, лежащему за текущей правой границей, приводит к созданию всех промежуточных элементов, причем они получают значение nil. Например, если определены элементы от 0 до 9 и затем производится присваивание элементу 1000, то создаются также элементы с индексами от 10 до 999, равные nil. Если это неприемлемо, надо поискать альтернативу.

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

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

В последних версиях Ruby стандартная библиотека содержит класс Set. Если вам приходится часто иметь дело с множествами, подумайте об использовании объектов Setвместо массивов. Этот класс рассмотрен в главе 9.

Массив нельзя назвать идеальным средством для представления множества, поскольку он может содержать дубликаты. Если вы хотите трактовать массив как множество, то дубликаты можно удалить (с помощью метода uniqили uniq!).

Над множествами производятся две основные операции: объединение и пересечение. Для этого применяются операторы |(или) и &(и) соответственно. Поскольку множество по определению не содержит дубликатов, то повторяющиеся элементы удаляются (вопреки ожиданиям тех, кому доводилось работать с объединением и пересечением массивов в других языках).

а = [1, 2, 3, 4, 5]

b = [3, 4, 5, 6, 7]

с = a | b # [1, 2, 3, 4, 5, 6, 7]

d = а & b # [3,4,5]

# Дубликаты удаляются...

e = [1, 2, 2, 3, 4]

f = [2, 2, 3, 4, 5]

g = e & f # [2; 3, 4]

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

Метод -соответствует операции «разность множеств»; результатом является множество, куда входят те элементы первого множества, которые не являются элементами второго (см. раздел 8.1.12).

а = [1, 2, 3, 4, 5]

b = [4, 5, 6, 7]

с = а - b # [1, 2, 3]

# Отметим, что наличие элементов 6 and 7 не отражается на результате.

Для «аккумулирования» множеств можно применять оператор |=; как и следовало ожидать, а |= b— то же самое, что а = а | b. Аналогичным образом оператор &=последовательно «сужает» множество.

Для массивов не определена операция ИСКЛЮЧАЮЩЕЕ ИЛИ, но мы можем без труда реализовать ее. В терминах теории множеств она соответствует выборке тех элементов, которые входят в объединение двух множеств, но не входят в их пересечение.

class Array

def ^(other)

(self | other) - (self & other)

end

end

x = [1, 2, 3, 4, 5]

y = [3, 4, 5, 6, 7]

z = x ^ y # [1, 2, 6, 7]

Чтобы проверить, входит ли некий элемент в множество, пользуйтесь методом include?или member?(синоним, подмешанный из модуля Comparable):

x = [1, 2, 3]

if x.include? 2

puts "yes" # Печатается "yes"

else

puts "no"

end

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

Многим это безразлично. Но привыкшие к языку Pascal или Python (или впитавшие математический формализм с молоком матери) хотели бы, чтобы было по-другому. Такую возможность мы реализуем в следующем фрагменте:

class Object

def in(other)

other.include? self

end

end

x = [1, 2, 3]

if 2.in x

puts "yes" # Печатается "yes"

else

puts "no"

end

Лично я отправил запрос на изменение Ruby (RCR 241) с предложением ввести в язык оператор in. Он должен походить на одноименный оператор в языках Pascal, Python и даже SQL.

У этой идеи есть свои достоинства (к тому же in— уже зарезервированное слово), но единодушного одобрения она не получила. Может быть, оператор in появится в Ruby, а может, и нет.

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

class Array

def subset?(other)

self.each do |x|

if !(other.include? x)

return false

end

end

true

end

def superset?(other)

other.subset?(self)

end

end

a = [1, 2, 3, 4]

b = [2, 3]

с = [2, 3, 4, 5]

flag1 = c.subset? a # false

flag2 = b.subset? a # true

flag3 = c.superset? b # true

Обратите внимание: мы выбрали «естественный» порядок, то есть задаем вопрос x.subset?у— «является ли xподмножеством у?», а не наоборот.

Для распознавания пустого множества достаточно проверить, пуст ли массив. Это делает метод empty?.

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

universe = [1, 2, 3, 4, 5, 6]

а = [2, 3]

b = universe - а # Дополнение а = [1, 4, 5, 6]

Если считаете необходимым, можете определить и унарный оператор (например, -или ~для выполнения этой операции.

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