Текст книги "Программирование на языке Ruby"
Автор книги: Хэл Фултон
Жанр:
Программирование
сообщить о нарушении
Текущая страница: 21 (всего у книги 56 страниц) [доступный отрывок для чтения: 23 страниц]
Для отображения индексов на элементы массива интерпретатор языка пользуется функцией индексирования. Поскольку методы доступа к элементам массива можно переопределять, мы можем реализовать любой способ индексирования.
Например, ниже реализован массив, в котором индексы начинаются с 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]]
Иногда нужно переставить элементы массива в случайном порядке. Первое, что приходит на ум, – тасование карточной колоды, но есть и другие применения – например, случайная сортировка списка вопросов.
Для решения этой задачи пригодится метод 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).
Если для численного анализа вам нужны многомерные массивы, то в архиве приложений 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.
В Ruby эта задача решается проще, чем во многих других языках. Нужно просто вычислить «разность множеств»:
text = %w[the magic words are squeamish ossifrage]
dictionary = %w[an are magic the them these words]
# Найти неправильно написанные слова
unknown = text – dictionary # ["squeamish", "ossifrage"]
Метод 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]
Метод 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]
В 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 равно []
Часто нужно добавить в конец существующего массива отдельный элемент или целый массив. В 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]
Базовые операции со стеком называются 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 вашей машине порядок может быть другим.)
Часто требуется вставить разделители между элементами массива, но не перед первым и не после последнего. Для этого предназначены метод 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"
Чтобы переставить элементы массива в обратном порядке, воспользуйтесь методами reverse или reverse!:
inputs = ["red", "green", "blue"]
outputs = inputs.reverse # ["green","blue","red"]
priorities = %w(eat sleep code)
priorities.reverse! # ["code","sleep","eat"]
Чтобы удалить из массива повторяющиеся экземпляры, воспользуйтесь методом uniq (или его вариантом для модификации на месте uniq!):
breakfast = %w[spam spam eggs ham eggs spam]
lunch = breakfast.uniq # ["spam","eggs","ham"]
breakfast.uniq! # Массив breakfast изменился.
