Чтение онлайн

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

(предыдущий); теоретически его можно было бы добавить, но не всегда он был бы применим. Метод устанавливает указатель в начало набора.

Недостаток библиотеки

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

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

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

Мы изучили различные методы обхода структур, например

и , а также выяснили, как работают энумераторы и генераторы.

В главе 9 мы продолжим изучение высокоуровневых структур данных. Не все они входят в ядро Ruby или в стандартные библиотеки. Речь пойдет о множествах, стеках, очередях, деревьях и графах.

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

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

, который хорошо поддерживает эту структуру.

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

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

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

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

Мы уже видели, что некоторые методы класса

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

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

, достаточно написать:

При этом также добавляется метод

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

Создать новое множество нетрудно. Метод

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

Для объединения множеств служит метод

(синонимы и ):

Пересечение множеств вычисляется методом

(синоним ):

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

Принадлежность элемента множеству проверяют методы

или , как для массивов. Напомним, что порядок операндов противоположен принятому в математике.