начало набора.
Недостаток библиотеки generator заключается в том, что она реализована с помощью продолжений (continuation). Во всех имеющихся на сегодняшний день версиях Ruby это требует большого объема вычислений, поэтому, если итераций много, работа заметно замедляется.
8.4. Заключение
Мы подробно рассмотрели массивы, хэши и перечисляемые структуры в общем. Мы установили определенное сходство между массивами и хэшами, объясняемое тем, что в оба класса подмешан модуль Enumerable. Но есть и различия. Мы показали, как преобразовать массив в хэш и наоборот, а также узнали несколько интересных способов расширить стандартное поведение.
Мы изучили различные методы обхода структур, например each_slice и each_cons, а также выяснили, как работают энумераторы и генераторы.
В главе 9 мы продолжим изучение высокоуровневых структур данных. Не все они входят в ядро Ruby или в стандартные библиотеки. Речь пойдет о множествах, стеках, очередях, деревьях и графах.
Глава 9. Более сложные структуры данных
Графическое представление данных абстрагирует банки памяти любого компьютера. Невообразимая сложность. Лучи света, протянувшиеся в не-пространстве разума, скопления и созвездия данных. Как гаснущие огни большого города.
Есть, конечно, более сложные и интересные структуры данных, чем массивы и хэши. Некоторые из тех, с которыми мы познакомимся в этой главе, имеют прямую или косвенную поддержку в Ruby, другие приходится программировать самостоятельно. К счастью, 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?, как и
