Программирование на языке Ruby

Фултон Хэл

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]