Загрузка...


  • 8.1. Массивы
  • 8.1.1. Создание и инициализация массива
  • 8.1.2. Доступ к элементам массива и присваивание им значений
  • 8.1.3. Определение размера массива
  • 8.1.4. Сравнение массивов
  • 8.1.5. Сортировка массива
  • 8.1.6. Выборка из массива по заданному критерию
  • 8.1.7. Специализированные функции индексирования
  • 8.1.8. Реализация разреженной матрицы
  • 8.1.9. Массивы как математические множества
  • 8.1.10. Рандомизация массива
  • 8.1.11. Многомерные массивы
  • 8.1.12. Нахождение элементов, принадлежащих одному массиву и не принадлежащих другому
  • 8.1.13. Преобразование или отображение массивов
  • 8.1.14. Удаление из массива элементов равных nil
  • 8.1.15. Удаление заданных элементов из массива
  • 8.1.16. Конкатенирование массивов и добавление в конец массива
  • 8.1.17. Использование массива в качестве стека или очереди
  • 8.1.18. Обход массива
  • 8.1.19. Преобразование массива в строку с разделителями
  • 8.1.20. Обращение массива
  • 8.1.21. Удаление дубликатов из массива
  • 8.1.22. Чередование массивов
  • 8.1.23. Вычисление частоты различных значений в массиве
  • 8.1.24. Инвертирование массива для получения хэша
  • 8.1.25. Синхронная сортировка нескольких массивов
  • 8.1.26. Указание значения по умолчанию для новых элементов массива
  • 8.2. Хэши
  • 8.2.1. Создание нового хэша
  • 8.2.2. Указание значения по умолчанию для хэша
  • 8.2.3. Доступ к парам ключ-значение и добавление новых пар
  • 8.2.4. Удаление пар ключ-значение
  • 8.2.5. Обход хэша
  • 8.2.6. Инвертирование хэша
  • 8.2.7. Поиск ключей и значений в хэше
  • 8.2.8. Копирование хэша в массив
  • 8.2.9. Выборка пар ключ-значение по заданному критерию
  • 8.2.10. Сортировка хэша
  • 8.2.11. Объединение двух хэшей
  • 8.2.12. Создание хэша из массива
  • 8.2.13. Вычисление разности и пересечения хэшей
  • 8.2.14. Хэш как разреженная матрица
  • 8.2.15. Реализация хэша с повторяющимися ключами
  • 8.3. Перечисляемые структуры в общем
  • 8.3.1. Метод inject
  • 8.3.2. Кванторы
  • 8.3.3. Метод partition
  • 8.3.4. Обход с группировкой
  • 8.3.5. Преобразование в массив или множество
  • 8.3.6. Энумераторы
  • 8.3.7. Объекты-генераторы
  • 8.4. Заключение
  • Глава 8. Массивы, хэши и другие перечисляемые структуры

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

    Если не удается соединить детали, на то должна быть причина.

    Ни в коем случае не пользуйтесь молотком.

    (Руководство по техническому обслуживанию компании IBM (1925))

    Простых переменных для практического программирования недостаточно. В любом современном языке поддерживаются более сложные виды структурированных данных и предоставляются механизмы для создания новых абстрактных типов данных.

    Исторически самой первой и широко распространившейся составной структурой данных был массив. Давным-давно, еще в языке ФОРТРАН, массивы назывались индексированными переменными; сегодня они несколько видоизменились, но основная идея во всех языках одна и та же.

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

    Наконец, мы рассмотрим сам модуль

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

    8.1. Массивы

    В 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]

    8.2. Хэши

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

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

    8.4. Заключение

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

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

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

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

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









    Главная | В избранное | Наш E-MAIL | Добавить материал | Нашёл ошибку | Наверх