public
Created

Hash.new

  • Download Gist
hash.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126
# Oftentimes, we want to create lists of things that have something in
# common. For example we may have a list of objects, each with a
# name. We want to count how many times each name occurs. We could do
# so with a hash, like this:
 
h = {}
a.each{|o|
# make sure there's a value here
h[o.name] ||= 0
h[o.name] += 1
}
 
# But it turns out there's an easier way, using the less common
# Hash.new method:
 
h = Hash.new(0)
a.each{|o| h[o.name] += 1}
 
# (or using a reduce to get it down to one line)
 
h = a.reduce(Hash.new(0)){|h, o| h[o.name] += 1; h}
 
# What's going on here? When we supply an argument to Hash.new, we
# provide a default value that's used for any key that's not already
# in the hash. When we omit the argument (or use the short-hand form
# {}) the default value is set to nil.
 
g = Hash.new(5)
h = {}
g["nancy"] = 10
 
g["nancy"] # => 10
g["sean"] # => 5
h["sean"] # => nil
 
# However, care should be taken with using normal objects as default
# values, as the following example shows:
 
h = Hash.new([])
h["mary"] << 5
h["abigail"] << 10
 
h["mary"] # => [5, 10]
h["abigail"] # => [5, 10]
 
# What's going on here? We're setting a particular object--an instance
# of the Array class--to the default value. However, this means that
# the exact same array is used for every index of the Hash. Needless
# to say, this probably isn't what you want. But there is another,
# more powerful form of Hash.new that can solve this exact problem:
# Hash.new {|hash, key| ... }. Using the block form, we can fix our
# above example:
 
h = Hash.new{|hash, key| hash[key] = []}
 
h["mary"] << 5
h["abigail"] << 10
 
h["mary"] # => [5]
h["abigail"] # => [10]
 
# Now we're producing a new array element for every key. This sort of
# thing can be useful if we have a list of objects each with names and
# values, and we want a list of the values corresponding to each
# name. We can now write:
 
h = Hash.new{|h, k| h[k] = []}
a.each{|o| h[o.name] << h.value}
 
# The possibilities are endless. Effectively the block form makes
# hashes into lightweight methods much like proc and lambda, with the
# added benefit that we get memoization for free. For example, lets
# say we want a function to calculate the fibonacci numbers. We all
# know the formula: f(n) = f(n-1) + f(n-2). We can compute it
# naievely like this:
 
def f(n)
case n
when 0 then 1
when 1 then 1
else
f(n-1) + f(n-2)
end
end
 
# This works fine for small values of n. f(20) takes less than three
# hundreths of a second on my MacBook Pro. But it quickly becomes
# useless: f(30) takes 0.34 seconds, but I got bored waiting for f(40)
# to finish. Is calculating the Fibbonaci sequence fundamently a hard
# problem, where we can't expect to find a good solution? Or do we
# just need to be smarter about it? Consider the following expansion,
# of the n = 5 case:
 
f(5) = f(4) + f(3)
= f(3) + f(2) + f(2) + f(1)
= f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)
= f(1) + f(0) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)
= 8
 
# While we got the right answer, notice how we kept repeating the same
# calculations. Even in the trivial case of n = 5, we calculated f(3)
# twice, and f(2) three times. Since we know that larger values of the
# problem depend on the values of smaller values, we can save
# ourselves an enormous amount of time my memoizing the function,
# which simply means saving the results of our earlier runs for
# later. The Ruby hash is a natural at this. Here's a much more
# effecient and yet concise implementation of the above:
 
f = Hash.new do |h, k|
case k
when 0 then h[0] = 1
when 1 then h[1] = 1
else
h[k] = h[k-2] + h[k-1]
end
end
 
# With our new and improved Fib, we can easily compute f(5000):
def time; t = Time.now; yield ; Time.now - t; end
time{f[5000]} # => 0.033939
 
# I should take this time to note that there is a very simple
# iterative algorithm for fibbonaci, and you should never actually use
# a recursive algorithm to compute it. However, this technique can be
# very useful for the many recursive algorithms which can not be
# trivially made iterative.

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.