Текст книги "Программирование на языке Ruby"
Автор книги: Хэл Фултон
Жанр:
Программирование
сообщить о нарушении
Текущая страница: 23 (всего у книги 56 страниц) [доступный отрывок для чтения: 23 страниц]
8.3. Перечисляемые структуры в общем
Что делает набор перечисляемым? Вообще-то сам тот факт, что это набор. Модуль Enumerable требует, чтобы был определен стандартный итератор each. Последовательность обхода не имеет значения, так как даже неупорядоченные наборы, например хэш, могут обладать итераторами.
Кроме того, если предполагается пользоваться методами min, max и sort, то для набора должен быть определен метод сравнения (<=>). Все это достаточно очевидно.
Итак, перечисляемая структура представляет собой набор, в котором можно производить поиск, который можно обойти и, быть может, отсортировать. В любой определенный пользователем набор, не являющийся подклассом существующего системного класса, имеет смысл подмешивать модуль Enumerable.
Имейте в виду – все сказанное о какой-то одной перечисляемой структуре относится ко всем. В качестве примеров таких структур можно назвать массив, хэш, дерево и т.д.
Конечно, у каждой структуры есть свои нюансы. Массив – это упорядоченный набор отдельных элементов, а хэш – неупорядоченный набор пар ключ-значение. Понятно, что в каких-то отношениях они будут вести себя по-разному.
Многие методы, с которыми мы познакомились при изучении массивов и хэшей (например, map и find), на самом деле определены в модуле Enumerable. Часто было трудно решить, как подать материал. Любая путаница или неточность – моя вина!..
Массив – наиболее часто употребляемый набор, подмешивающий этот модуль. Поэтому по умолчанию я буду пользоваться в примерах именно массивами.
8.3.1. Метод injectМетод inject пришел в Ruby из языка Smalltalk (впервые он появился в версии Ruby 1.8). Его поведение интересно, хотя с первого раза понять его нелегко.
Он отражает тот факт, что мы часто хотим обойти список и по ходу «аккумулировать» некоторый результат. Конечно, самый естественный пример – суммирование чисел в списке. Но и для других операций обычно есть некий «аккумулятор» (которому присваивается начальное значение) и применяемая функция (в Ruby она представлена блоком).
В качестве тривиального примера рассмотрим массив чисел, которые нужно просуммировать:
nums = [3,5,7,9,11,13]
sum = nums.inject(0) {|x,n| x+n }
Обратите внимание, что начальное значение аккумулятора равно 0 («нейтральный элемент» для операции сложения). Затем блок получает текущее значение аккумулятора и значение текущего элемента списка. Действие блока заключается в прибавлении нового значения к текущей сумме.
Ясно, что этот код эквивалентен следующему:
sum = 0
nums.each {|n| sum += n }
В данном случае уровень абстракции лишь немногим выше. Если идея метода inject не укладывается у вас в голове, не пользуйтесь им. Но если удалось преодолеть первоначальное непонимание, то вы сможете найти ему новые элегантные применения.
Начальное значение аккумулятора задавать необязательно. Если оно опущено, то в качестве такового используется значение первого элемента, который при последующих итерациях пропускается,
sum = nums.inject {|x,n| x+n }
# To же самое, что:
sum = nums[0]
nums[1..-1].each {|n| sum + = n }
Другой похожий пример – вычисление произведения чисел. В данном случае аккумулятору следует присвоить начальное значение 1 (нейтральный элемент для операции умножения).
prod = nums.inject(1) {|x,n| x*n }
# или
prod = nums.inject {|x,n| x*n }
В следующем немного более сложном примере мы находим самое длинное слово в списке:
words = %w[ alpha beta gamma delta epsilon eta theta ]
longest_word = words.inject do |best,w|
w.length > best.length ? w : best
end
# Возвращается значение "epsilon".
Кванторы any? и all? появились в версии Ruby 1.8, чтобы было проще проверять некоторые свойства набора. Оба квантора принимают в качестве параметр блок (который должен возвращать значение true или false).
Nums = [1,3,5,8,9]
# Есть ли среди чисел четные?
flag1 = nums.any? {|x| x % 2 == 0 } # true
# Все ли числа четные?
flag2 = nums.all? {|x| x % 2 == 0 } # false
Если блок не задан, то просто проверяется значение истинности каждого элемента. Иными словами, неявно добавляется блок {|x| x }.
flag1 = list.all? # list не содержит ни одного false или nil.
flag1 = list.any? # list содержит хотя бы одно истинное значение
# не nil и не false).
Как говорится, «в мире есть два сорта людей: те, что делят людей по сортам, и те, что не делят». Метод partition относится не к людям (хотя мы можем представить их в Ruby как объекты), но тоже делит набор на две части.
Если при вызове partition задан блок, то он вычисляется для каждого элемента набора. В результате создаются два массива: в первый попадают элементы, для которых блок вернул значение true, во второй – все остальные. Метод возвращает массив, двумя элементами которого являются эти массивы.
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
odd_even = nums.partition {|x| x % 2 == 1 }
# [[1,3,5,7,9],[2,3,4,6,8]]
under5 = nums.partition {|x| x < 5 }
# [[1,2,3,4],[5,6,7,8,9]]
squares = nums.partition {|x| Math.sqrt(x).to_i**2 == x }
# [[1,4,9], [2,3,5,6,7,8]]
Если нужно разбить набор больше чем на две группы, придется написать собственный метод. Я назвал его classify по аналогии с методом из класса Set.
module Enumerable
def classify(&block)
hash = {}
self.each do |x|
result = block.call(x)
(hashfresult] ||= []) << x
end
hash
end
end
nums = [1,2,3,4,5,6,7,8,9]
mod3 = nums.classify {|x| x % 3 }
# { 0=>[3,6,9], 1=>[1,4,7], 2=>[2,5,8] }
words = %w( area arboreal brick estrous clear donor ether filial
patina ]
vowels = words.classify {|x| x.count("aeiou") }
# {1=>["brick"], 2=>["clear", "donor", "ether"],
# 3=>["area", "estrous", "filial", "patina"], 4=>["arboreal"]}
initials = words.classify {|x| x[0..0] }
# {"a"=>["area", "arboreal"], "b"=>["brick"], "c"=>["clear"],
# "d"=>["donor"], "p"=>["patina"], "e"=>["estrous", "ether"],
# "f"=>["filial"]}
До сих пор мы обходили список по одному элементу за раз. Но иногда желательно на каждой итерации анализировать по два, три или более элементов.
Итератор each_slice принимает в качестве параметра число n, равное числу просматриваемых на каждой итерации элементов. (Для работы с ним нужна библиотека enumerator.) Если не осталось достаточного количества элементов, размер последнего фрагмента будет меньше.
require 'enumerator'
arr = [1,2,3,4,5,6,7,8,9,10]
arr.each_slice(3) do |triple|
puts triple.join(",")
end
# Выводится:
# 1,2,3
# 4,5,6
# 7,8,9
# 10
Имеется также итератор each_cons, который позволяет обходить набор методом «скользящего окна» заданного размера. (Если название кажется вам странным, знайте, что это наследие языка Lisp.) В таком случае фрагменты всегда будут иметь одинаковый размер.
require 'enumerator'
arr = [1,2,3,4,5,6,7,8,9,10]
arr.each_cons(3) do |triple|
puts triple.join(",")
end
# Выводится:
# 1,2,3
# 2,3,4
# 3,4,5
# 4,5,6
# 5,6,7
# 6,7,8
# 7,8,9
# 8,9,10
Каждая перечисляемая структура теоретически может быть тривиально преобразована в массив (методом to_a). Например, такое преобразование для хэша дает вложенный массив пар:
hash = {1=>2, 3=>4, 5=>6}
arr = hash.to_a # [[5, 6], [1, 2], [3, 4]]
Синонимом to_a является метод entries.
Если была затребована библиотека set, становится доступен также метод to_set. Дополнительная информация о множествах приведена в разделе 9.1.
require 'set'
hash = {1=>2, 3=>4, 5=>6}
set = hash.to_set # #
Объект класса Enumerator – по существу, обертка, превращающая итераторный метод в полноценный объект Enumerable. Обернутый таким способом итератор приобретает все методы и свойства, присущие перечисляемым структурам.
В следующем искусственном примере в классе Foo есть итератор и больше ничего. Да и сам-то итератор не делает ничего полезного, только четыре раза вызывает yield. Чтобы подчеркнуть особенность его работы, итератор назван every, а не each.
require 'enumerator'
class Foo
def every
yield 3
yield 2
yield 1
yield 4
end
end
foo = Foo.new
# Передается объект и имя итератора...
enum = Enumerable::Enumerator, new(foo, :every)
enum.each {|x| p x } # Печатаются элементы
array = enum.to_a # [3,2,1,4]
sorted = enum.sort # [1,2,3,4]
Преобразование выглядит загадочно, но, по сути, это не что иное как:
enum = []
foo.every {|x| enum << x }
В примере выше enum – настоящий массив, а не просто объект Enumerator. Как следствие, несмотря на некоторые тонкие различия, это еще один способ преобразовать объект в перечисляемую структуру Enumerable.
Если затребована библиотека enumerator, то в классе object появляется метод enum_for. Поэтому создание объекта в первом примере можно записать компактнее:
enum = fоо.enum_for(:every)
Мы уже видели, как итераторы each_slice и each_cons позволяют осуществлять обход с группировкой. Оказывается, что есть специальные методы enum_slice и enum_cons, которые создают из таких итераторов объекты-энумераторы (по существу, трансформируя имя итератора в each). Имейте в виду, что методы Enumerable::Enumerator.new и enum_for могут принимать необязательный список аргументов в качестве последнего параметра. Ниже мы воспользовались этим для передачи итератору «размера окна»:
array = [5,3,1,2]
discrete = array.enum_slice(2)
# To же, что Enumerable::Enumerator.new(array,:each_slice,2)
overlap = array.enum_cons(2)
# To же, что Enumerable::Enumerator.new(array,:each_cons,2)
discrete.each {|x| puts x.join(",") }
# Выводится:
# 5,3
# 1,2
overlap.each {|x| puts x.join(",") )
# Выводится:
# 5,3
# 3,1
# 1,2
Идея генератора довольно интересна. Обычный итератор в Ruby является внутренним, он запускает некоторый алгоритм, повторно вызывая блок кода.
Но бывают также и внешние итераторы. В этом случае алгоритм запускается самой программой, а итератор поставляет данные «по запросу», а не в соответствии с собственным «графиком».
В качестве аналогии можно рассмотреть метод getline, который выступает в роли внешнего итератора для объекта класса IO. Вы сами вызываете его в удобные моменты времени, а он возвращает прочитанные данные. Сравните это с поведением итератора each_line, который последовательно передает программе прочитанные строки.
Иногда внутренние итераторы не вполне подходят. Они позволяют решить задачу, но не лучшим способом. Внешний итератор был бы удобнее.
Библиотека generator позволяет преобразовать внутренний итератор во внешний. Она предоставляет такие же методы next, rewind и end?, как в классе IO. Вот пример:
require 'generator'
array = [7,8,9,10,11,12]
gen = Generator.new(array)
what = gen.current # 7
where = gen.index # 0 (то же, что pos)
while gen.end? and gen.current <11
gen.next
end
puts gen.current # 11
puts gen.next # 11
puts gen.index # 4 (index – то же, что pos)
puts gen.next? # true (next? – то же, что end?)
puts gen.next # 12
puts gen.next? # false
Обратите внимание, как мы «читаем» набор по одному элементу в одном или нескольких циклах. Метод end? обнаруживает конец набора; если вы проигнорируете его «совет», генератор возбудит исключение EOFError. Синонимом end? служит next?.
Метод index (синоним pos) сообщает индекс или позицию в наборе. Естественно, индексация начинается с нуля, как в случае с массивом или смещением от начала файла.
Методы current и next, возможно, интуитивно неочевидны. Представьте себе, что в начале выполняется операция «получить»; тогда текущий (current) элемент оказывается таким же, как следующий (next). Ясно, что метод next продвигает указатель на следующую позицию, a current – нет.
Поскольку для многих наборов возможно только продвижение в прямом направлении, то и генератор ведет себя так же. Не существует метода prev (предыдущий); теоретически его можно было бы добавить, но не всегда он был бы применим. Метод rewind устанавливает указатель в начало набора.
Недостаток библиотеки 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 } # Множество строк, а не чисел.
Для объединения множеств служит метод 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?, как и в случае с массивами. Метод clear очищать множество, то есть удаляет из него все элементы.
s = Set[1,2,3,4,5,6]
s.empty? # false
s.clear
s.empty? # true
Можно проверить, является ли одно множество подмножеством, собственным подмножеством или надмножеством другого.
x = Set[3,4,5]
y = Set[3,4]
x.subset?(y) # false
y.subset?(x) # true
y.proper_subset?(x) # true
x.subset?(x) # true
x.proper_subset?(x) # false
x.superset?(y) # true
Метод add (синоним <<) добавляет в множество один элемент и обычно возвращает его в качестве значения. Метод add? возвращает nil, если такой элемент уже присутствовал в множестве. Метод merge полезен, если надо добавить сразу несколько элементов. Все они, конечно, могут изменить состояние вызывающего объекта. Метод replace работает так же, как в случае со строкой или массивом.
Наконец, два множества можно сравнить на равенство интуитивно очевидным способом:
Set[3,4,5] == Set[5,4,3] # true
Разумеется, можно обойти множество, но (как и для хэшей) не ожидайте какого-то определенного порядка появления элементов, потому что множества по сути своей неупорядочены, и 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 # #
Вот еще один, несколько искусственный пример. Простыми числами-близнецами называются простые числа, отличающиеся на 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: #
# #
# #
# Более компактно: {{23},{11,13},{17,19},{5,7,3}, {2},{29,31}}
На мой взгляд, этот метод труден для понимания; я рекомендую пользоваться методом classify, более простым и интуитивно очевидным.
Важно понимать, что класс Set не всегда требует, чтобы параметр или операнд также был множеством (если вам это кажется странным, вспомните обсуждение «утипизации» в главе 1). На самом деле большая часть методов данного класса принимает в качестве параметра любой перечисляемый объект. Считайте, что так и задумано.
Есть и другие методы, которые применяются в частности к множествам (в том числе все методы из модуля Enumerable). Я не стану рассматривать здесь такие методы, как flatten. Дополнительную информацию можно найти на сайте http://ruby-doc.org/ или в любом другом справочном руководстве.
9.2. Стеки и очереди
Стеки и очереди – это первые из встретившихся нам структур, которые, строго говоря, не встроены в Ruby. Иными словами, в Ruby нет классов Stack и Queue, в отличие от Array и Hash (впрочем, класс Queue есть в библиотеке thread.rb, которую мы еще будем рассматривать).
И все же в некотором смысле они встроены в Ruby. Ведь класс Array реализует всё, что нужно для того, чтобы рассматривать его как стек или очередь. Стек организован по принципу «последним пришел, первым обслужен» (LIFO – last-in first-out). Традиционный пример – стопка подносов на подпружиненной подставке в кафетерии: подносы кладутся сверху и сверху же снимаются.
Над стеком можно выполнять ограниченный набор операций. Как минимум операции заталкивания (push) и выталкивания (pop), то есть помещения в стек и извлечения из него. Обычно также предоставляется способ проверить, пуст ли стек, и исследовать верхний элемент, не извлекая его из стека. Но никогда реализация не позволяет получить доступ к элементу в середине стека.
Как же реализовать стек на базе массива, если к элементам массива можно обращаться в произвольном порядке, а стек таким свойством не обладает? Ответ прост. Стек – более абстрактная структура, чем массив. Он является стеком лишь до тех пор, пока мы обращаемся с ним как с таковым. В тот момент, когда вы пытаетесь обратиться к элементу недопустимым образом, стек перестает быть стеком.
Но можно без труда определить класс Stack так, что к элементам можно будет обращаться только законно. И мы покажем, как это сделать.
Стоит отметить, что во многих алгоритмах стек применяется как основа элегантного рекурсивного решения. Причина станет ясна, если чуточку подумать. При вызове функции или метода параметры заталкиваются в системный стек и выталкиваются из него при возврате. Таким образом, рекурсивный алгоритм просто подменяет явно определенный пользователем стек системным. Что лучше? Зависит от того, какое значение вы придаете понятности программы, ее эффективности и другим аспектам.
Очередь организована по принципу «первым пришел, первым обслужен» (FIFO – first-in first-out). Аналогом может служить очередь за билетами в театр: вновь подходящие становятся в конец очереди, а те, кто пришел раньше, обслуживаются первыми. В программировании очереди используются реже, чем стеки.
Очереди полезны в системах реального времени, когда события нужно обрабатывать в порядке возникновения. Находят они применение и в ситуации «производитель-потребитель» (особенно в многопоточных программах и многозадачных средах). Неплохой пример – очередь к принтеру: задания на печать помещаются в один конец и ожидают, пока не будут извлечены с другого конца.
Две основные операции над очередью называются «поместить» (enqueue) и «извлечь» (dequeue). Им соответствуют методы unpush и shift в классе Array.
Отметим, что метод unshift может использоваться в сочетании с shift при реализации массива, но никак не очереди, поскольку unshift добавляет элемент в тот же конец массива, из которого shift его удаляет. С помощью различных комбинаций этих методов можно реализовать и стек, и очередь, но рассматривать все возможные сочетания мы не будем.
На этом мы закончим введение в стеки и очереди. Самое время рассмотреть некоторые примеры.
