В Ruby массивы индексируются целыми числами; индексация начинается с нуля, как в языке С. На этом, впрочем, сходство и заканчивается.

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

Массивы в Ruby неоднородны, то есть в них могут храниться данные разных типов. На самом деле в массиве хранятся только ссылки на объекты, а не объекты как таковые. Исключение составляют только непосредственные значения, например объекта класса Fixnum.

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

Наконец, класс Array в Ruby предоставляет немало полезных функций для работы с массивами: доступ, поиск, конкатенирование и т.п. В этом разделе мы изучим встроенную функциональность и расширим ее.

 

8.1.1. Создание и инициализация массива

Для создания массива применяется специальный метод класса []; перечисленные внутри скобок данные помещаются во вновь созданный массив. Ниже показаны три способа вызвать этот метод. (Массивы а, b и с инициализируются одинаково.)

a = Array.[] (1,2,3,4)

b = Array[1,2,3,4]

с = [1,2,3,4]

Имеется также метод класса new, который принимает 0,1 или 2 параметра. Первый параметр задает начальный размер массива (число элементов в нем). Второй определяет начальное значение каждого элемента:

d = Array.new            # Создать пустой массив.

е = Array.new(3)         # [nil, nil, nil]

f = Array.new(3, "blah") # ["blah", "blah", "blah"]

Обратите особое внимание на последний пример. Типичная «ошибка начинающего» — думать, что все объекты в этом массиве различны. На самом деле это три ссылки на один и тот же объект. Поэтому, если вы его измените (а не замените другим), то изменятся все элементы массива. Чтобы не попасть в эту ловушку, воспользуйтесь блоком. Блок будет вычисляться по одному разу для каждого элемента, поэтому все элементы окажутся различными объектами:

f[0].capitalize!            # f равно: ["Blah", "Blah", "Blah"]

g = Array.new(3) { "blah" } # ["blah", "blah", "blah"]

g[0].capitalize!            # g равно: ["Blah", "blah", "blah"]

 

8.1.2. Доступ к элементам массива и присваивание им значений

Получить ссылку на элемент и присвоить ему значение можно с помощью методов класса [] и []= соответственно. Каждый из них принимает один целочисленный параметр — либо пару целых чисел (начало и конец), либо диапазон. Отрицательные индексы отсчитываются от конца массива, начиная с -1.

Специальный метод экземпляра at реализует простейший случай получения ссылки на элемент. Поскольку он может принимать только один целочисленный параметр, то работает чуть быстрее.

a = [1, 2, 3, 4, 5, 6]

b = а[0]               # 1

с = a.at(0)            # 1

d = а[-2]              # 5

е = a.at(-2)           # 5

f = а[9]               # nil

g = a.at(9)            # nil

h = a[3,3]             # [4, 5, 6]

i = a[2..4]            # [3, 4, 5]

j = a[2...4]           # [3, 4]

a[1] = 8               # [1, 8, 3, 4, 5, 6]

a[1,3] = [10, 20, 30]  # [1, 10, 20, 30, 5, 6]

a[0..3] = [2, 4, 6, 8] # [2, 4, 6, 8, 5, 6]

a[-1] = 12             # [2, 4, 6, 8, 5, 12]

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

k = [2, 4, 6, 8, 10]

k[1..2] = [3, 3, 3] # [2, 3, 3, 3, 8, 10]

k[7] = 99           # [2, 3, 3, 3, 8, 10, nil, 99]

Наконец, если одному элементу присвоить в качестве значения массив, то на место этого элемента будет вставлен вложенный массив (в отличие от присваивания диапазону):

m = [1, 3, 5, 7, 9]

m[2] = [20, 30]    # [1,3, [20, 30], 7, 9]

# С другой стороны... m = [1, 3, 5, 7, 9]

m[2..2] = [20, 30] # [1, 3, 20, 30, 7, 9]

Метод slice — синоним метода []:

x = [0, 2, 4, 6, 8, 10, 12]

а = x.slice(2)    # 4

b = x.slice(2,4)  # [4, 6, 8, 10]

с = x.slice(2..4) # [4, 6, 8]

Специальные методы first и last возвращают первый и последний элемент массива соответственно. Если массив пуст, они возвращают nil:

x = %w[alpha beta gamma delta epsilon]

a = x.first # "alpha"

b = x.last  # "epsilon"

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

Метод values_at принимает список индексов и возвращает массив, содержащий только указанные элементы. Его можно использовать в тех случаях, когда диапазон не годится (так как нужные элементы находятся не в соседних позициях).

В более ранних версиях Ruby метод values_at назывался indices (синоним indexes). Теперь эти названия не используются.

x = [10, 20, 30, 40, 50, 60]

y = x.values_at(0, 1, 4) # [10, 20, 50]

z = x.values_at(0..2,5)  # [10, 20, 30, 60]

 

8.1.3. Определение размера массива

Метод length и его синоним size возвращают число элементов в массиве. (Как всегда, эта величина на единицу больше индекса последнего элемента.)

x = ["а", "b", "с", "d"]

а = x.length # 4

b = x.size   # 4

Метод nitems отличается от предыдущих тем, что не учитывает элементы равные nil:

у = [1, 2, nil, nil, 3, 4]

с = у.size   # 6

d = у.length # 6

е = y.nitems # 4

 

8.1.4. Сравнение массивов

При сравнении массивов возможны неожиданности — будьте осторожны!

Для сравнения массивов служит метод экземпляра <=>. Он работает так же, как в других контекстах, то есть возвращает -1 (меньше), 0 (равно) или 1 (больше). Методы == и != опираются на реализацию метода <=>.

Массивы сравниваются поэлементно; первая же пара несовпадающих элементов определяет результат всего сравнения. (Предпочтение отдается левее расположенным элементам, как при сравнении двух длинных целых чисел «на глазок», когда мы сравниваем по одной цифре за раз.)

а = [1, 2, 3, 9, 9]

b = [1, 2, 4, 1, 1]

с = а <=> b # -1 (то есть а < b)

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

d = [1, 2, 3]

е = [1, 2, 3, 4]

f = [1, 2, 3]

if d < е          # false

 puts "d меньше e"

end

if d == f

 puts "d равно f" # Печатается "d равно f"

end

Поскольку класс Array не подмешивает модуль Comparable, то обычные операторы сравнения <, >, <= и >= для массивов не определены. Но при желании их легко определить самостоятельно:

class Array

 def <(other)

  (self <=> other) == -1

 end

 def <=(other)

  (self < other) or (self == other)

 end

 def >(other)

  (self <=> other) == 1

 end

 def >=(other)

  (self > other) or (self == other)

 end

end

Впрочем, было бы проще включить модуль Comparable:

class Array

 include Comparable

end

Определив эти операторы, можно пользоваться ими как обычно:

if а < b

 print "а < b" # Печатается "а < b"

else

 print "а >= b"

end

if d < e

 puts "d < e"  # Печатается "d < e"

end

Может статься, что при сравнении массивов мы столкнемся с необходимостью сравнивать два элемента, для которых оператор <=> не определен или не имеет смысла. Следующий код приводит к возбуждению исключения (TypeError) во время выполнения, так как сравнение 3 <=> "x" лишено смысла:

g = [1, 2, 3]

h = [1, 2, "x"]

if g < h      # Ошибка!

 puts "g < h" # Ничего не выводится.

end

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

if g != h      # Здесь ошибка не возникает.

 puts "g != h" # Печатается "g != h"

end

Наконец, не исключено, что два массива, содержащих несравнимые типы данных, все равно можно сравнить с помощью операторов < и >. В примере ниже мы получаем определенный результат еще до того, как натолкнемся на несравнимые элементы:

i = [1, 2, 3]

j = [1, 2, 3, "x"]

if i < j      # Здесь ошибка не возникает.

 puts "i < j" # Печатается "i < j"

end

 

8.1.5. Сортировка массива

Самый простой способ отсортировать массив — воспользоваться встроенным методом sort:

words = %w(the quick brown fox)

list = words.sort # ["brown", "fox", "quick", "the"]

# Или отсортировать на месте:

words.sort!       # ["brown", "fox", "quick", "the"]

Здесь предполагается, что все элементы массива сравнимы между собой. При сортировке неоднородного массива, например [1, 2, "tHRee", 4], обычно возникает ошибка.

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

а = [1, 2, "three", "four", 5, 6]

b = a.sort {|x,y| x.to_s <=> y.to_s}

# b равно [1, 2, 5, 6, "four", "three"]

Конечно, подобное упорядочение (в данном случае основанное на кодировке ASCII) может оказаться бессмысленным. При работе с неоднородным массивом нужно прежде всего задать себе вопрос, зачем вообще его сортировать. И почему приходится хранить в массиве объекты разных типов?

Описанная методика работает, потому что блок возвращает целое число (-1.0 или 1) при каждом вызове. Если возвращена -1, то есть x меньше у, то два элемента меняются местами. Чтобы отсортировать массив по убыванию, достаточно все го лишь изменить порядок сравнения:

x = [1, 4, 3, 5, 2]

y = x.sort {|a,b| b <=> а} # [5, 4, 3, 2, 1]

Блоки можно применять и для более сложных сортировок. Предположим, что нужно отсортировать названия книг и фильмов следующим способом: регистр игнорируется, полностью игнорируются пробелы, а также ряд знаков препинания и артикли. Ниже приведен простой пример (и преподаватели английского языка, и программисты будут удивлены таким способом упорядочения по алфавиту).

titles = ["Starship Troopers",

          "A Star is Born",

          "Star Wars",

          "Star 69",

          "The Starr Report"]

sorted = titles.sort do |x,y|

 # Удалить артикли

 a = x.sub(/"(a |an |the )/i, "")

 b = y.sub(/"(a |an |the )/i, "")

 # Удалить пробелы и знаки препинания

 a.delete!(" .,-?!")

 b.delete!(" .,-?!")

 # Преобразовать в верхний регистр

 a.upcase!

 b.upcase!

 # Сравнить а и b

 а <=> b

end

# Теперь sorted равно:

# [ "Star 69", "A Star is Born", "The Starr Report"

#   "Starship Troopers", "Star Wars"]

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

В последних версиях Ruby в модуль Enumerable добавлен метод sort_by (который, конечно, подмешивается к классу Array). Важно понимать, что он делает.

В методе sort_by применяется то, что программисты на Perl называют преобразованием Шварца — в честь Рэндала Шварца (Randal Schwartz), внесшего немалый вклад в развитие этого языка. Вместо того чтобы сортировать сами элементы массива, мы применяем к ним некоторую функцию и сортируем возвращаемые ей результаты.

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

files = files.sort {|x,y| File.size(x) <=> File.size(y) }

Однако тут есть две проблемы. Во-первых, слишком многословно. Надо бы сделать покомпактнее.

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

Метод sort_by решает обе проблемы. Вот «правильный» способ:

files = files.sort_by {|x| File.size(x) }

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

Не существует метода sort_by!. Но при желании вы можете написать его самостоятельно.

А как обстоит дело с сортировкой по нескольким ключам? Предположим, что имеется массив объектов, который нужно отсортировать по трем атрибутам: имени, возрасту и росту. Из того, что массивы можно сравнивать, следует, что такое решение будет работать:

list = list.sort_by {|x| [x.name, x.age, x.height] }

Конечно, элементы массива могут быть и не такими простыми. Допустимы произвольно сложные выражения.

 

8.1.6. Выборка из массива по заданному критерию

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

Метод detect находит не больше одного элемента. Он принимает блок (которому элементы передаются последовательно) и возвращает первый элемент, для которого значение блока оказывается равным true.

x = [5, 8, 12, 9, 4, 30]

# Найти первый элемент, кратный 6.

x.detect {|e| e % 6 == 0 } #12

# Найти первый элемент, кратный 7.

c.detect {|e| e % 7 == 0 } # nil

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

Метод find — синоним detect. Метод find_all возвращает несколько элементов, а не один-единственный; select — синоним find_all.

# Продолжение предыдущего примера...

x.find {|e| e % 2 == 0}     # 8

x.find_all {|e| e % 2 == 0} # [8, 12, 4, 30]

x.select {|e| e % 2 == 0}   # [8, 12, 4, 30]

Метод grep вызывает оператор сравнения (то есть оператор ветвящегося равенства) для сопоставления каждого элемента с заданным образцом. В простейшей форме он возвращает массив, состоящий из элементов, соответствующих образцу. Так как используется оператор ===, то образец не обязан быть регулярным выражением. (Имя grep пришло из UNIX и связано с командой старого редактора g/re/p.)

а = %w[January February March April May]

a.grep(/ary/}  # ["January, "February"]

b = [1, 20, 5, 7, 13, 33, 15, 28]

b.grep(12..24) # [20, 13, 15]

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

# продолжение предыдущего примера...

# Будем сохранять длины строк.

a.grep(/ary/) {|m| m.length} # [7, 8]

# Будем сохранять квадраты исходных элементов.

b.grep(12..24) { |n| n*n}    # {400, 169, 225}

Метод reject — полная противоположность select. Он исключает из массива элементы, для которых блок возвращает значение true. Имеется также вариант reject! для модификации массива «на месте»:

с = [5, 8, 12, 9, 4, 30]

d = с.reject {|e| е % 2 == 0} # [5, 9]

b.reject! {|e| е % 3 == 0}

# с равно [5, 8, 4]

Методы min и max ищут минимальное и максимальное значение в массиве. У каждого метода есть две формы. В первой используется сравнение «по умолчанию», что бы это ни означало в конкретной ситуации (на базе оператора <=>). Во второй форме применяется блок для выполнения нестандартного сравнения.

а = %w[Elrond Galadriel Aragorn Saruman Legolas]

b = a.min # "Aragorn"

с = a.max # "Saruman"

d = a.min {|x,y| x.reverse <=> y.reverse} # "Elrond"

e = a.max {|x,y| x.reverse <=> y.reverse} # "Legolas"

Чтобы найти индекс минимального или максимального элемента (в предположении, что такой элемент один), применяется метод index:

# Продолжение предыдущего примера...

i = a.index a.min # 2

j = a.index a.max # 3

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

 

8.1.7. Специализированные функции индексирования

Для отображения индексов на элементы массива интерпретатор языка пользуется функцией индексирования. Поскольку методы доступа к элементам массива можно переопределять, мы можем реализовать любой способ индексирования.

Например, ниже реализован массив, в котором индексы начинаются с 1, а не с нуля:

class Array2 < Array

 def [] (index)

  if index>0

   super(index-1)

  else

   raise IndexError

  end

 end

 def []=(index,obj)

  if index>0

   super(index-1,obj)

  else

   raise IndexError

  end

 end

end

x = Array2.new

x[1]=5

x[2]=3

x[0]=1  # Ошибка.

x[-1]=1 # Ошибка.

Отметим, что отрицательные индексы (от конца массива) здесь запрещены. Имейте в виду, что в реальной задаче придется внести и другие изменения, например переопределить метод slice и пр. Но общую идею вы поняли.

Аналогичный подход можно применить для реализации многомерных массивов (мы еще вернемся к ним в разделе 8.1.11).

Можно также реализовать нечто вроде треугольной матрицы, как показано ниже. Это частный случай двумерного массива, в котором элемент в позиции x,y совпадает с элементом в позиции y,x (поэтому хранить можно только один). Иногда это бывает полезно, например для хранения неориентированного графа (как мы покажем ближе к концу главы).

class TriMatrix

 def initialize

  @store = []

 end

 def [](x,y)

  if x > у

   index = (x*x+x)/2 + y

   @store[index]

  else

   raise IndexError

  end

 end

 def []=(x,y,v)

  if x > y

   index = (x*x+x)/2 + y

   @store[index] = v

  else

   raise IndexError

  end

 end

end

t = TriMatrix.new

t[3,2] = 1

puts t[3,2] # 1

puts t[2,3] # IndexError

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

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

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

 

8.1.8. Реализация разреженной матрицы

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

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

С другой стороны, присваивание значения элементу массива, лежащему за текущей правой границей, приводит к созданию всех промежуточных элементов, причем они получают значение nil. Например, если определены элементы от 0 до 9 и затем производится присваивание элементу 1000, то создаются также элементы с индексами от 10 до 999, равные nil. Если это неприемлемо, надо поискать альтернативу.

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

 

8.1.9. Массивы как математические множества

В большинстве языков множества напрямую не реализованы (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

x = [1, 2, 3, 4, 5]

y = [3, 4, 5, 6, 7]

z = x ^ y # [1, 2, 6, 7]

Чтобы проверить, входит ли некий элемент в множество, пользуйтесь методом include? или member? (синоним, подмешанный из модуля Comparable):

x = [1, 2, 3]

if x.include? 2

 puts "yes" # Печатается "yes"

else

 puts "no"

end

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

Многим это безразлично. Но привыкшие к языку Pascal или Python (или впитавшие математический формализм с молоком матери) хотели бы, чтобы было по-другому. Такую возможность мы реализуем в следующем фрагменте:

class Object

 def in(other)

  other.include? self

 end

end

x = [1, 2, 3]

if 2.in x

 puts "yes" # Печатается "yes"

else

 puts "no"

end

Лично я отправил запрос на изменение Ruby (RCR 241) с предложением ввести в язык оператор in. Он должен походить на одноименный оператор в языках Pascal, Python и даже SQL.

У этой идеи есть свои достоинства (к тому же in — уже зарезервированное слово), но единодушного одобрения она не получила. Может быть, оператор in появится в Ruby, а может, и нет.

Теперь обратимся к подмножествам и надмножествам. Как определить, является ли данное множество подмножеством или надмножеством другого? Встроенных методов для этого нет, но мы можем поступить следующим образом:

class Array

 def subset?(other)

  self.each do |x|

   if !(other.include? x)

    return false

   end

  end

  true

 end

 def superset?(other)

  other.subset?(self)

 end

end

a = [1, 2, 3, 4]

b = [2, 3]

с = [2, 3, 4, 5]

flag1 = c.subset? a   # false

flag2 = b.subset? a   # true

flag3 = c.superset? b # true

Обратите внимание: мы выбрали «естественный» порядок, то есть задаем вопрос x.subset?у — «является ли x подмножеством у?», а не наоборот.

Для распознавания пустого множества достаточно проверить, пуст ли массив. Это делает метод empty?.

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

universe = [1, 2, 3, 4, 5, 6]

а = [2, 3]

b = universe - а # Дополнение а = [1, 4, 5, 6]

Если считаете необходимым, можете определить и унарный оператор (например, - или ~ для выполнения этой операции.

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

Наконец, иногда возникает необходимость вычислить степень множества. Это не что иное, как множество всех подмножеств данного множества (включая его само и пустое множество). Читатели, знакомые с дискретной математикой, в особенности с комбинаторикой, понимают, что число таких подмножеств равно 2n. Сгенерировать степень множества можно следующим образом:

class Array

 def powerset

  num = 2**size

  ps = Array.new(num, [])

  self.each_index do |i|

   a = 2**i

   b = 2**(i+1) — 1

   j = 0

   while j < num-1

    for j in j+a..j+b

     ps[j] += [self[i]]

    end

    j += 1

   end

  end

  ps

 end

end

x = [1, 2, 3]

y = x.powerset

# y равно:

#  [[], [1], [2], [1,2] , [3], [1,3], [2,3], [1,2,3]]

 

8.1.10. Рандомизация массива

Иногда нужно переставить элементы массива в случайном порядке. Первое, что приходит на ум, — тасование карточной колоды, но есть и другие применения — например, случайная сортировка списка вопросов.

Для решения этой задачи пригодится метод rand из модуля Kernel. Ниже показан один из возможных способов:

class Array

 def randomize

  self.sort_by { rand } # Сортировать по ключу, являющемуся

 end                    # случайным числом.

 def randomize!

  self.replace(self.randomize)

 end

end

x = [1, 2, 3, 4, 5]

y = x.randomize # [3, 2, 4, 1, 5]

x.randomize!    # x равно [3, 5, 4, 2]

Из-за самой природы сортировки, вероятно, вносится некоторое статистическое смещение. Но обычно это не играет роли.

Выбрать случайный элемент массива (не запрещая дубликатов) можно так:

class Array

 def pick_random

  self[rand(self.length)]

 end

end

Наконец, не стоит забывать, что метод rand позволяет сгенерировать предсказуемую последовательность (например, для тестирования), если затравить алгоритм известным значением с помощью метода srand (см. раздел 5.28).

 

8.1.11. Многомерные массивы

Если для численного анализа вам нужны многомерные массивы, то в архиве приложений Ruby есть прекрасная библиотека NArray, которую написал Масахиро Танака (Masahiro Tanaka). Если необходим аппарат для работы с матрицами, обратитесь к стандартной библиотеке matrix.rb, которая была упомянута в разделе 5.10.

В следующем примере показан способ работы с многомерными массивами за счет перегрузки методов [] и []= для отображения элементов на вложенный массив. Представленный класс Array3 обеспечивает рудиментарные операции с трехмерными массивами, но он далеко не полон:

class Array3

 def initialize

  @store = [[[]]]

 end

 def [](a,b,c)

  if @store[a]==nil ||

   @store[a][b]==nil ||

   @store[a][b][c]==nil

   return nil

  else

   return @store[a][b][c]

  end

 end

 def []=(a,b,c,x)

  @store[a] = [[]] if @store[a]==nil

  @store[a][b] = [] if @store[a][b]==nil

  @store[a][b][с] = x

 end

end

x = Array3.new

x[0,0,0] = 5

x[0,0,1] = 6

x[1,2,31 = 99

puts x[1,2,3]

Единственное, чего мы реально добились, — так это удобного использования запятой в обозначении [x,y,z] вместо употребляемой в языке С нотации [x][у][z]. Если C-подобная нотация вас устраивает, можете просто воспользоваться вложенными массивами Ruby. Еще одно мелкое достоинство — предотвращение ситуации, когда объектом, от имени которого вызывается оператор [], оказывается nil.

 

8.1.12. Нахождение элементов, принадлежащих одному массиву и не принадлежащих другому

В Ruby эта задача решается проще, чем во многих других языках. Нужно просто вычислить «разность множеств»:

text = %w[the magic words are squeamish ossifrage]

dictionary = %w[an are magic the them these words]

# Найти неправильно написанные слова

unknown = text - dictionary # ["squeamish", "ossifrage"]

 

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

Метод collect из модуля Enumerable часто позволяет сэкономить время и силы. Тем, кто привык к языку Smalltalk, он покажется интуитивно очевидным в большей степени, чем программистам на С.

Этот метод просто воздействует неким произвольным образом на каждый элемент массива, порождая в результате новый массив. Иными словами, он «отображает» один массив на другой (отсюда и синоним map).

x = %w[alpha bravo charlie delta echo foxtrot]

# Получить начальные буквы.

a = x.collect (|w| w[0..0]}  # %w[a b с d e f]

# Получить длины строк.

b = x.collect {|w| w.length} # [5, 5, 7, 5, 4, 7]

# map - просто синоним.

с = x.map {|w| w.length}     # [5, 5, 7, 5, 4, 7]

Имеется также вариант collect! (или map!) для модификации на месте.

x.collect! {|w| w.upcase}

# x равно %w[ALPHA BRAVO CHARLIE DELTA ECHO FOXTROT]

x.map! {|w| w.reverse}

# x равно %w[AHPLA OVARB EILRAHC ATLED OHCE TORTXOF]

 

8.1.14. Удаление из массива элементов равных nil

Метод compact (и его вариант compact! для модификации на месте) удаляет из массива элементы равные nil, оставляя все остальные без изменения:

a = [1, 2, nil, 3, nil, 4, 5]

b = a.compact # [1, 2, 3, 4, 5]

a.compact!    # а равно [1, 2, 3, 4, 5]

 

8.1.15. Удаление заданных элементов из массива

В Ruby легко удалить элементы из массива - для этого даже существует много способов. Чтобы удалить элемент с известным индексом, достаточно вызвать метод delete_at:

a = [10, 12, 14, 16, 18]

a.delete_at(3) # Возвращает 16.

# а равно [10, 12, 14, 18]

a.delete_at(9) # Возвращает nil {вне диапазона).

Все элементы с заданным значением поможет удалить метод delete. Он возвращает значения удаленных элементов или nil, если искомый элемент не найден:

b = %w(spam spam bacon spam eggs ham spam)

b.delete("spam") # Возвращает "spam"

# b равно ["bacon", "eggs", "ham"]

b.delete("caviar") # Возвращает nil

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

с = ["alpha", "beta", "gamma", "delta"]

c.delete("delta") { "Nonexistent" }

# Возвращается "delta" (блок не вычисляется).

с.delete("omega") { "Nonexistent" }

# Возвращается "Nonexistent".

Метод delete_if передает каждый элемент массива в блок и удаляет те элементы, для которых вычисление блока дает true. Примерно так же ведет себя метод reject! с тем отличием, что последний может возвращать nil, когда массив не изменяется.

email = ["job offers", "greetings", "spam", "news items"]

# Удалить слова из четырех букв

email.delete_if {|x| x.length==4 }

# email равно ["job offers", "greetings", "news items"]

Метод slice! получает доступ к тем же элементам, что и slice, но, помимо возврата их значений, еще и удаляет из массива:

x = [0, 2, 4, 6, 8, 10, 12, 14, 16]

а = x.slice!(2)    # 4

# x is now [0, 2, 6, 8, 10, 12, 14, 16]

b = x.slice!(2,3)  # [6, 8, 10]

# x is now [0, 2, 12, 14, 16]

с = x.slice!(2..3) # [12, 14]

# x is now [0, 2, 16]

Для удаления элементов из массива можно также пользоваться методами shift и pop (дополнительную информацию об их исходном предназначении вы найдете в разделе 9.2).

x = [1, 2, 3, 4, 5]

x.рор   # Удалить последний элемент.

# x is now [1, 2, 3, 4]

x.shift # Удалить первый элемент.

# x is now [2, 3, 4]

Метод reject принимает блок и формирует новый массив без тех элементов, для которых блок возвращает true:

arr = [1,2,3,4,5,6,7,8]

odd = arr.reject {|x| x % 2 == 0 } # [1,3,5,7]

Наконец, метод clear удаляет из массива все элементы. Это эквивалентно присваиванию переменной пустого массива, но чуть-чуть эффективнее:

x = [1, 2, 3]

x.clear

# x равно []

 

8.1.16. Конкатенирование массивов и добавление в конец массива

Часто нужно добавить в конец существующего массива отдельный элемент или целый массив. В Ruby это можно сделать разными способами.

Оператор << добавляет объект в конец массива; в качестве значения он возвращает сам массив, поэтому можно объединять несколько таких операций в цепочку.

x = [1, 5, 9]

x << 13       # x равно [1, 5, 9, 13]

x << 17 << 21 # x равно [1, 5, 9, 13, 17, 21].

Аналогичную операцию выполняют методы unshift и push, которые добавляют элемент в начало и в конец массива соответственно (см. также следующий раздел данной главы).

Массивы можно конкатенировать методом concat или с помощью операторов + и +=:

x = [1,2]

y = [3,4]

z = [5,6]

b = y + z  # [3,4,5,6]

b += x     # [3,4,5,6,1,2]

z.concat у # z равно [5,6,3,4]

Имейте в виду, что оператор += всегда создает новый объект. Также не забывайте, что оператор << добавляет в конец новый элемент, который сам может быть массивом.

a = [1,2]

b = [3,4]

a += b          # [1,2,3,4]

a = [1,2]

b = [3,4]

а << b          # [1,2, [3,4]]

a = [1,2]

b = [3,4]

а = a.concat(b) # [1,2,3,4]

 

8.1.17. Использование массива в качестве стека или очереди

Базовые операции со стеком называются push и pop, они добавляют и удаляют элементы в конец массива. Базовые операции с очередью — это shift (удаляет элемент из начала массива) и unshift (добавляет элемент в начало массива). Для добавления в конец массива можно также пользоваться оператором << (по существу синоним push).

Постарайтесь не запутаться. Методы shift и unshift модифицируют массив в начале, a push, pop и << — в конце.

Эта тема будет продолжена в разделе 9.2.

 

8.1.18. Обход массива

Как и следовало ожидать, в классе Array есть стандартный итератор each. Но имеются и другие полезные итераторы.

Метод reverse_each обходит массив в обратном порядке. Результат такой же, как если бы мы вызвали сначала метод reverse, а потом each, но работает быстрее.

words = %w(Son I am able she said)

str = ""

words.reverse_each { |W| str += "#{w} "}

# str равно "said she able am I Son "

Если нужно только перебрать все индексы, можно воспользоваться итератором each_index. Конструкция x.each_index эквивалентна (0..(x.size-1)).each (то есть обходу всего диапазона индексов).

Итератор each_with_index (подмешанный из модуля Comparable) передает в блок как сам элемент, так и его индекс.

x = ["alpha", "beta", "gamma"]

x.each_with_index do |x,i|

 puts "Элемент #{i} равен #{x}"

end

# Выводятся три строки.

Предположим, что нужно обойти массив в случайном порядке. Ниже представлен итератор random_each (который просто вызывает метод randomize, описанный в разделе 8.1.10).

class Array

 # Предполагается, что метод randomize определен.

 def random_each

  temp = self.randomize

  temp.each {|x| yield x}

 end

end

dwarves = %w(Sleepy Dopey Happy Sneezy Grumpy Bashful Doc)

list = ""

dwarves.random_each (|x| list += "#{x} "}

# list равен:

# "Bashful Dopey Sleepy Happy Grumpy Doc Sneezy "

# (Ha вашей машине порядок может быть другим.)

 

8.1.19. Преобразование массива в строку с разделителями

Часто требуется вставить разделители между элементами массива, но не перед первым и не после последнего. Для этого предназначены метод join и оператор *.

been_there = ["Veni", "vidi", "vici."]

journal = been_there.join(", ") # "Veni, vidi, vici."

letters = ["Phi","Mu","Alpha"]

musicians = letters.join(" ")   # "Phi Mu Alpha"

people = ["Bob","Carol","Ted","Alice"] movie = people * " and "

# movie равно "Bob and Carol and Ted and Alice"

Если необходимо обрабатывать последний элемент особым образом, например вставить перед ним слово «and», это можно сделать вручную:

list = %w[A В С D Е F]

with_commas = list[0..-2]*", " + ", and " + list[-1]

# with_commas равно "А, В, C, D, E, and F"

 

8.1.20. Обращение массива

Чтобы переставить элементы массива в обратном порядке, воспользуйтесь методами reverse или reverse!:

inputs = ["red", "green", "blue"]

outputs = inputs.reverse # ["green","blue","red"]

priorities = %w(eat sleep code)

priorities.reverse! # ["code","sleep","eat"]

 

8.1.21. Удаление дубликатов из массива

Чтобы удалить из массива повторяющиеся экземпляры, воспользуйтесь методом uniq (или его вариантом для модификации на месте uniq!):

breakfast = %w[spam spam eggs ham eggs spam]

lunch = breakfast.uniq # ["spam","eggs","ham"]

breakfast.uniq! # Массив breakfast изменился.

 

8.1.22. Чередование массивов

Предположим, что есть два массива и надо построить из них третий, который содержит массивы из двух элементов, взятых из соответственных позиций исходных массивов. В последних версиях Ruby модуль Enumerable содержит метод zip:

a = [1, 2, 3, 4]

b = ["a", "b", "c", "d"]

с = a.zip(b)

# с равно [[1,"а" ] , [2,"b"], [3,"с"], [4,"d"]]

# Чтобы устранить вложенность, воспользуйтесь методом flatten

d = с.flatten

# d равно [1, "а", 2, "b", 3, "с", 4, "d"]

 

8.1.23. Вычисление частоты различных значений в массиве

Для массивов нет метода count, как для строк (чтобы подсчитать число вхождений каждого элемента). Поэтому создадим свой собственный:

class Array

 def count

  k=Hash.new(0)

  self.each{|x| k[x]+=1 }

  k

 end

end

meal = %w[spam spam eggs ham eggs spam]

items = meal.count

# items равно {"ham" => 1, "spam" => 3, "eggs" => 2}

spams = items["spam"] # 3

Обратите внимание, что метод возвращает хэш.

 

8.1.24. Инвертирование массива для получения хэша

Массив нужен для того, чтобы ассоциировать целое число (индекс) с данными. А если нужно инвертировать это отношение, то есть ассоциировать данные с индексом? Иными словами, породить хэш? Это можно сделать так:

class Array

 def invert

  h={}

  self.each_with_index{|x,i| h[x]=i}

  h

 end

end

a = ["red","yellow","orange"]

h = a.invert # {"orange"=>2, "yellow"=>1, "red"=>0}

 

8.1.25. Синхронная сортировка нескольких массивов

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

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

class Array

 def sort_index

  d=[]

  self.each_with_index{|x, i| d[i]=[x,i]}

  if block_given?

   d.sort {|x,у| yield x[0],y[0]}.collect{|x| x[1]}

  else

   d.sort.collect{|x| x[1]}

  end

 end

 def sort_with(ord=[])

  return nil if self.length!=ord.length

  self.values_at(*ord)

 end

end

a = [21, 33, 11, 34, 36, 24, 14]

b = a.sort_index

a2 = a.sort_with(b)

c = a.sort_index {|x,y| x%2 <=> y%2 }

a3 = a.sort_with(c)

p a  # [21, 33, 11, 34, 36, 24, 14]

p b  # [2,6,0,5,1,3,4]

p a2 # [11, 14, 21, 24, 33, 34, 36]

p c  # [6, 5, 4, 3, 2, 1, 0]

p a3 # [14, 24, 36, 34, 11, 33, 21]

 

8.1.26. Указание значения по умолчанию для новых элементов массива

Когда массив растет и в нем создаются новые элементы, по умолчанию им присваивается значение nil:

a = Array.new

a[0]="x"

a[3]="y"

# а равно ["x", nil, nil, "y"]

Но, допустим, нам требуется, чтобы новые элементы получали другое значение. Тогда в качестве конкретного применения общего принципа предлагаем класс ZArray, описывающий массив, в котором вновь созданные элементы будут равны 0:

class ZArray < Array

 def [](x)

  if x > size

   for i in size+1..x

    self[i]=0

   end

  end

  v = super(x)

 end

 def []=(x,v)

  max = size

  super(x,v)

  if size - max > 1

   (max..size-2).each do |i|

    self[i] = 0

   end

  end

 end

end

num = Zarray.new

num[1] = 1

num[2] = 4

num[5] = 25

# num равно [0, 1, 4, 0, 0, 25]

 

Хэши еще называют ассоциативными массивами, словарями и т.д. Особенно хорошо эта структура данных знакома программистам на языках Perl и Java.

Массив можно представить как структуру, которая создает ассоциацию между индексом x и элементом данных y. Хэш тоже создает подобную ассоциацию, но с двумя отличиями. Во-первых, в случае с массивом x — целое число, а для хэша это не обязательно. Во-вторых, массив — упорядоченная структура, тогда как элементы хэша обычно располагаются в непредсказуемом порядке.

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

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

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

 

8.2.1. Создание нового хэша

Как и в случае с классом Array, для создания хэша служит специальный метод класса []. Данные, перечисленные в квадратных скобках, образуют ассоциированные пары. Ниже показаны шесть способов вызвать этот метод (все хэши с a1 до c2 содержат одни и те же данные).

a1 = Hash.[]("flat",3,"curved",2)

a2 = Hash.[]("flat"=>3,"curved"=>2)

b1 = Hash["flat",3,"curved",2]

b2 = Hash["flat"=>3,"curved"=>2]

c1 = {"flat",3,"curved",2}

c2 = {"flat"=>3,"curved"=>2}

# Для a1, b1 и c1 число элементов должно быть четным.

Есть также метод new, который может принимать параметр, задающий значение по умолчанию. Отметим, что это значение не является частью хэша — оно просто используется вместо nil.

d = Hash.new         # Создать пустой хэш.

е = Hash.new(99)     # Создать пустой хэш.

f = Hash.new("а"=>3) # Создать пустой хэш.

е["angled"]          # 99

e.inspect            # {}

f["b"]               # {"а"=>3} (значением по умолчанию

                     # является тоже хэш).

f.inspect            # {}

 

8.2.2. Указание значения по умолчанию для хэша

Значением по умолчанию для хэша является объект, возвращаемый вместо nil в случае, когда указанный ключ не найден. Это полезно, если вы планируете вызывать для возвращенного значения методы, которые для nil не определены. Задать значение по умолчанию можно в момент создания хэша или позже с помощью метода default=.

Все отсутствующие ключи указывают на один и тот же объект по умолчанию, поэтому изменение данного объекта имеет побочный эффект.

а = Hash.new("missing") # Объект по умолчанию - строка "missing".

a["hello"]              # "missing"

а.default="nothing"

a["hello"]              # "nothing"

a["good"] << "bye"      # "nothingbye"

a.default               # "nothingbye"

Имеется также специальный метод экземпляра fetch, который возбуждает исключение IndexError, если в объекте типа Hash нет указанного ключа. Он принимает также второй параметр, играющий роль значения по умолчанию. Кроме того, методу fetch можно передать необязательный блок, который выработает значение по умолчанию, если ключ не будет найден. Таким образом, каждому отсутствующему ключу можно сопоставить свое «значение по умолчанию».

а = {"flat",3,"curved",2,"angled",5}

a.fetch("pointed")                # IndexError

a.fetch("curved","na")            # 2

a.fetch("x","na")                 # "na"

a.fetch("flat") {|x| x.upcase}    # 3

a.fetch("pointed") {|x| x.upcase) # "POINTED"

 

8.2.3. Доступ к парам ключ-значение и добавление новых пар

В классе Hash есть методы класса [] и []=. Используются они почти так же, как одноименные методы в классе Array, но принимают лишь один параметр. В качестве параметра может выступать любой объект, а не только строка (хотя строки используются чаще всего).

а = {}

а["flat"] = 3       # {"flat"=>3}

а.[]=("curved",2)   # {"flat"=>3,"curved"=>2}

a.store("angled",5) # {"flat"=>3,"curved"=>2,"angled"=>5}

Метод store — просто синоним []=, оба могут принимать два аргумента, как показано в примере выше.

Метод fetch аналогичен методу [], но возбуждает исключение IndexError, когда ключ отсутствует. Есть у него и необязательный второй аргумент (или блок) для указания значения по умолчанию (см. раздел 8.2.2).

a["flat"]       # 3

а.[]("flat")    # 3

a.fetch("flat") # 3

a["bent"]       # nil

Предположим, что мы не уверены, существует ли объект Hash, но хотели бы избежать очистки имеющегося хэша. Очевидное решение — проверить, определен ли интересующий нас объект:

unless defined? а

 а={}

end

a["flat"] = 3

Но есть и другой способ:

а ||= {}

a["flat"] = 3

# Или даже так:

(а ||= {})["flat"] = 3

Тот же вопрос можно поставить для отдельных ключей, когда новое значение следует присваивать, лишь если такого ключа еще нет:

a=Hash.new(99)

а[2]       # 99

а          # {}

а[2] ||= 5 # 99

а          # {}

b=Hash.new

b          # {}

b[2]       # nil

b[2] ||= 5 # 5

b          # {2=>5}

Отметим, что nil может выступать и в качестве ключа, и в качестве значения:

b={}

b[2]      # nil b[3]=nil

b         # {3=>nil}

b[2].nil? # true

b[3].nil? # true b[nil]=5

b         # {3=>nil,nil=>5}

b[nil]    # 5

b[b[3]]   # 5

 

8.2.4. Удаление пар ключ-значение

Удалить пары ключ-значение из хэша можно с помощью методов clear, delete, delete_if, reject, reject! и shift.

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

Метод shift удаляет незаданную пару ключ-значение и возвращает ее в виде массива из двух элементов или nil, если никаких ключей не осталось.

a = {1=>2, 3=>4}

b = a.shift # [1,2]

# а равно {3=>4}

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

a = (1=>1, 2=>4, 3=>9, 4=>16)

a.delete(3) # 9

# a is now {1=>1, 2 =>4, 4=>16)

a.delete(5)                # в этом случае nil.

delete(6) { "не найдено" } # "не найдено".

Пользуйтесь методами delete_if, reject или reject! в сочетании с обязательны блоком, чтобы удалить все ключи, для которых блок возвращает значение true. Метод reject работает с копией хэша, а метод reject! возвращает nil, если не было произведено никаких изменений.

 

8.2.5. Обход хэша

В классе Hash имеется стандартный итератор each, а кроме него итераторы each_key, each_pair и each_value (each_pair — синоним each).

{"а"=>3, "b"=>2}.each do |key, val|

 print val, " из ", key, "; " # 3 из a; 2 из b;

end

Остальные два итератора передают в блок только ключ или только значение:

{"а"=>3,"b"=>2}.each_key do |key|

 print "ключ = #{key};" # Печатается: ключ = a; key = b;

end

{"a"=>3,"b"=>2).each_value do |value|

 print "значение = #{value};" # Печатается: значение = 3; val = 2;

end

 

8.2.6. Инвертирование хэша

Инвертирование хэша осуществляется в Ruby тривиально с помощью метода invert:

а = {"fred"=>"555-1122","jane"=>"555-7779"}

b = a.invert

b["555-7779"] # "jane"

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

 

8.2.7. Поиск ключей и значений в хэше

Определить, было ли присвоено значение некоторому ключу, позволяет метод has_key? или любой из его синонимов include?, key?, member?:

а = {"а"=>1,"b"=>2}

a.has_key? "с" # false

a.include? "а" # true

a.key? 2       # false

a.member? "b"  # true

Можно также воспользоваться методом empty?, чтобы узнать, остался ли в хэше хотя бы один ключ. А метод length и его синоним size позволяют узнать, сколько ключей имеется в хэше:

a.empty? # false

a.length # 2

Можно проверить также, существует ли указанное значение. Для этого предназначены методы has_value? или value?:

a.has_value? 2 # true

a.value? 99    # false

 

8.2.8. Копирование хэша в массив

Чтобы преобразовать весь хэш в массив, пользуйтесь методом to_a. В получившемся массиве ключи станут элементами с четными индексами (начиная с 0), а значения — с нечетными:

h = {"а"=>1,"b"=>2}

h.to_a # ["а",1,"b",2]

Можно также получить массив, содержащий только ключи или только значения:

h.keys   # ["а","b"]

h.values # [1,2]

Наконец, можно поместить в массив только значения, соответствующие заданному списку ключей. Этот метод работает для хэшей примерно так же, как одноименный метод для массивов. (Кроме того, как и в случае массивов, метод values_at заменяет устаревшие методы indices и indexes.)

h = {1=>"one", 2=>"two", 3=>"three", 4=>"four", "cinco"=>"five"}

h.values_at(3,"cinco",4) # ["three","five","four"]

h.values_at(1,3)         # ["one","three"]

 

8.2.9. Выборка пар ключ-значение по заданному критерию

К классу Hash подмешан модуль Enumerable, поэтому можно обращаться к методам detect (find), select (find_all), grep, min, max и reject (как и для массивов).

Метод detect (синоним find) находит одну пару ключ-значение. Он принимает блок (которому передается по одной паре за раз) и возвращает первую пару, для которой вычисление блока дает true.

names = {"fred"=>"jones","jane"=>"tucker", "joe"=>"tucker","mary"=>"SMITH"}

# Найти tucker.

names.detect {|k,v| v=="tucker" } # ["joe","tucker"]

# Найти имена, записанные прописными буквами.

names.find {|k,v| v==v.upcase }   # ["mary", "SMITH"]

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

Метод select (синоним find_all) возвращает все пары, удовлетворяющие условию, а не только первую:

names.select {|k,v| v=="tucker" }

# [["joe", "tucker"], ["jane", "tucker"]]

names.find_all (|k,v| k.count("r")>0}

# [["mary", "SMITH"], ["fred", "jones"]]

 

8.2.10. Сортировка хэша

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

names = {"Jack"=>"Ruby","Monty"=>"Python",

         "Blaise"=>"Pascal", "Minnie"=>"Perl"} list = names.sort

# list равно:

# [["Blaise","Pascal"], ["Jack","Ruby"],

# ["Minnie","Perl"], ["Monty","Python"]]

 

8.2.11. Объединение двух хэшей

Иногда бывает нужно объединить хэши. Метод merge получает два хэша и формирует из них третий, перезаписывая обнаружившиеся дубликаты:

dict = {"base"=>"foundation", "pedestal"=>"base"}

added = {"base"=>"non-acid", "salt"=>"NaCl"}

new_dict = diet.merge(added)

# {"base" =>"non-acid", "pedestal" =>"base", "salt"=>"NaCl"}

У метода merge есть синоним update.

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

dict = {"base"=>"foundation", "pedestal"=>"base"}

added = {"base"=>"non-acid", "salt" =>"NaCl"}

new_dict = diet.merge(added) {|key,old,new| old < new ? old : new }

# {"salt"=>"NaCl", "pedestal"=>"base", "base"=>"foundation"}

Таким образом, при использовании блока результат может получиться не такой, как в случае, когда блок не задан. Имеются также методы merge! и update!, которые изменяют вызывающий объект «на месте».

 

8.2.12. Создание хэша из массива

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

Array =[2,3,4,5,6,7]

hash = Hash[*array]

# hash равно: {2=>3, 4=>5, 6=>7}

 

8.2.13. Вычисление разности и пересечения хэшей

Ключи хэша можно скопировать в отдельный массив, а к получившимся из разных хэшей массивам применить методы & и - класса Array. Результатом являются пересечение и разность множеств ключей. Соответствующие им значения можно получить с помощью метода each, примененного к хэшу, содержащему все образованные таким способом ключи.

а = {"а"=>1,"b"=>2,"z"=>3}

b = {"x"=>99,"у"=>88,"z"=>77}

intersection = a.keys & b.keys

difference = a.keys - b.keys

с = a.dup.update(b)

inter = {}

intersection.each {|k| inter[k]=c[k] }

# inter равно {"z"=>77}

diff={}

difference.each {|k| diff[k]=c[k] }

# diff равно {"а"=>1, "b"=>2}

 

8.2.14. Хэш как разреженная матрица

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

В следующем примере предполагается, что несуществующие значения по умолчанию равны нулю:

values = Hash.new(0)

values[1001] = 5

values[2010] = 7

values[9237] = 9

x = values[9237] # 9

y = values[5005] # 0

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

А если нужно реализовать разреженную матрицу размерности два или более? В этом случае можно было бы использовать массивы в качестве ключей:

cube = Hash.new(0)

cube[[2000,2000,2000]] = 2

z = cube[[36,24,36]] # 0

Здесь обычная матрица содержала бы миллиарды элементов.

 

8.2.15. Реализация хэша с повторяющимися ключами

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

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

Листинг 8.1. Хэш с повторяющимися ключами

class HashDup

 def initialize(*all)

  raise IndexError if all.size % 2 != 0

  @store = {}

  if all[0] # не nil

   keyval = all.dup

   while !keyval.empty?

    key = keyval.shift

    if @store.has_key?(key)

     @store[key] += [keyval.shift]

    else

     @store[key] = [keyval.shift]

    end

   end

  end

 end

 def store(k,v)

  if @store.has_key?(k)

   @store[k] += [v]

  else

   @store[k] = [v]

  end

 end

 def [](key)

  @store[key]

 end

 def []=(key,value)

  self.store(key,value)

 end

 def to_s

  @store.to_s

 end

 def to_a

  @store.to_a

 end

 def inspect

  @store.inspect

 end

 def keys

  result=[]

  @store.each do |k,v|

   result += ([k]*v.size)

  end

  result

 end

 def values

  @store.values.flatten

 end

 def each

  @store.each {|k,v| v.each {|y| yield k,y}}

 end

 alias each_pair each

 def each_key

  self.keys.each {|k| yield k}

 end

 def each_value

  self.values.each {|v| yield v}

 end

 def has_key? k

  self.keys.include? k

 end

 def has_value? v

  self.values.include? v

 end

 def length

  self.values.size

 end

 alias size length

 def delete k

  val = @store[k]

  @store.delete k

  val

 end

 def delete k,v

  @store[k] -= [v] if @store[k]

  v

 end

 # Остальные методы опущены...

end

# He будет работать... для повторяющихся ключей

# актуально только последнее значение.

h = {1=>1, 2=>4, 3=>9, 4=>16, 2=>0}

# А так будет...

h = HashDup.new(1,1, 2,4, 3,9, 4,16, 2,0)

k = h.keys   # [4, 1, 2, 2, 3]

v = h.values # [16, 1, 4, 0, 9]

n = h.size   # 5

h.each {|k,v| puts "#{k} => #{v}"}

# Печатается:

# 4 => 16

# 1 => 1

# 2 => 4

# 2 => 0

# 3 => 9

Но если не пользоваться литеральными хэшами, то задача решаема. В листинге 8.1 реализован класс, содержащий атрибут @store, который является обычным хэшем; каждое значение этого хэша представляет собой массив. Доступ к хэшу организован так, что при необходимости добавить ключ, который уже существует, мы на самом деле добавляем новое значение в массив, ассоциированный с этим ключом.

Что должен возвращать метод size? Очевидно, «истинное» число пар ключ-значение, включая и дубликаты. Аналогично метод keys возвращает массив, который может содержать дубликаты. Итераторы ведут себя естественно; как и в случае обычного хэша, порядок обхода непредсказуем.

Помимо стандартного метода delete мы реализовали метод delete_pair. Первый удаляет все значения, ассоциированные с данным ключом, второй — только конкретную пару ключ-значение. (Отметим, что было бы затруднительно реализовать единственный метод вида delete(k, v=nil), так как nil — допустимое значение в любом хэше.)

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

 

Что делает набор перечисляемым? Вообще-то сам тот факт, что это набор. Модуль 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 # #

 

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