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".

8.3.2. Кванторы.

Кванторы 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).

8.3.3. Метод partition.

Как говорится, «в мире есть два сорта людей: те, что делят людей по сортам, и те, что не делят». Метод 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"]}.

8.3.4. Обход с группировкой.

До сих пор мы обходили список по одному элементу за раз. Но иногда желательно на каждой итерации анализировать по два, три или более элементов.

Итератор 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.

8.3.5. Преобразование в массив или множество.

Каждая перечисляемая структура теоретически может быть тривиально преобразована в массив (методом 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 # #<Set: {[1, 2], [3, 4], [5, 6]}>

8.3.6. Энумераторы.

Объект класса 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.

8.3.7. Объекты-генераторы.

Идея генератора довольно интересна. Обычный итератор в 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 это требует большого объема вычислений, поэтому, если итераций много, работа заметно замедляется.