Текст книги "Программирование на языке Ruby"
Автор книги: Хэл Фултон
Жанр:
Программирование
сообщить о нарушении
Текущая страница: 22 (всего у книги 56 страниц) [доступный отрывок для чтения: 23 страниц]
Предположим, что есть два массива и надо построить из них третий, который содержит массивы из двух элементов, взятых из соответственных позиций исходных массивов. В последних версиях 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"]
Для массивов нет метода 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}
Предположим, что необходимо отсортировать массив, которому соответствуют «параллельные» массивы, то есть в соответственных позициях находятся логически связанные данные. Не хотелось бы, чтобы в результате сортировки это соответствие нарушилось.
В представленном ниже решении мы сортируем массив и сохраняем получившийся набор индексов. Затем список индексов (который сам является массивом) можно применить к любому другому массиву, чтобы расставить его элементы в том же порядке.
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]
Когда массив растет и в нем создаются новые элементы, по умолчанию им присваивается значение 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 # {}
Значением по умолчанию для хэша является объект, возвращаемый вместо 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"
В классе 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
Удалить пары ключ-значение из хэша можно с помощью методов 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, если не было произведено никаких изменений.
В классе 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
Инвертирование хэша осуществляется в 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
Чтобы преобразовать весь хэш в массив, пользуйтесь методом 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"]
К классу 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"]]
Хэши по природе своей не упорядочены ни по ключам, ни по значениям. Чтобы отсортировать хэш, Ruby преобразует его в массив, который затем сортирует. Понятно, что и результатом является массив.
names = {"Jack"=>"Ruby","Monty"=>"Python",
"Blaise"=>"Pascal", "Minnie"=>"Perl"} list = names.sort
# list равно:
# [["Blaise","Pascal"], ["Jack","Ruby"],
# ["Minnie","Perl"], ["Monty","Python"]]
Иногда бывает нужно объединить хэши. Метод 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!, которые изменяют вызывающий объект «на месте».
Простейший способ сделать это – прибегнуть к способу создания хэшей с помощью квадратных скобок. Следующий способ годится, если массив состоит из четного числа элементов.
Array =[2,3,4,5,6,7]
hash = Hash[*array]
# hash равно: {2=>3, 4=>5, 6=>7}
Ключи хэша можно скопировать в отдельный массив, а к получившимся из разных хэшей массивам применить методы & и - класса 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}
Часто в массиве или матрице заполнена лишь небольшая часть элементов. Можно хранить их как обычно, но такое расходование памяти неэкономно. Хэш позволяет хранить только реально существующие значения.
В следующем примере предполагается, что несуществующие значения по умолчанию равны нулю:
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, пришлось бы принимать небанальные решения по поводу желательного поведения. Интересующийся читатель может восполнить пробелы.
