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

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

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

Кроме того, треугольную матрицу можно реализовать в виде массива, содержащего массивы, размер которых увеличивается по мере увеличения номера строки. Примерно так мы и поступили в разделе 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