Программирование на языке Ruby - Хэл Фултон
Шрифт:
Интервал:
Закладка:
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 # Ошибка.
