Recipe 5.12. Building a Histogram

Problem

You have an array that contains a lot of references to relatively few objects. You want to create a histogram, or frequency map: something you can use to see how often a given object shows up in the array.

Solution

Build the histogram in a hash, mapping each object found to the number of times it appears.

module Enumerable
	  def to_histogram
	    inject(Hash.new(0)) { h, x h[x] += 1; h}
	  end
	end

	[1, 2, 2, 2, 3, 3].to_histogram
	# => {1=>1, 2=>3, 3=>2}

	["a", "b", nil, "c", "b", nil, "a"].to_histogram
	# => {"a"=>2, "b"=>2, "c"=>1, nil=>2}

	"Aye\nNay\nNay\nAbstaining\nAye\nNay\nNot Present\n".to_histogram
	# => {"Abstaining\n"=>1, "Nay\n"=>3, "Not Present\n"=>1, "Aye\n"=>2}

	survey_results = { "Alice" => :red, "Bob" => :green, "Carol" => :green,
	                   "Mallory" => :blue }
	survey_results.values.to_histogram
	# => {:red=>1, :green=>2, :blue=>1}

Discussion

Making a histogram is an easy and fast (linear-time) way to summarize a dataset. Histograms expose the relative popularity of the items in a dataset, so they're useful for visualizing optimization problems and dividing the "head" from the "long tail."

Once you have a histogram, you can find the most or least common elements in the list, sort the list by frequency of appearance, or see whether the distribution of items matches your expectations. Many of the other recipes in this book build a histogram as a first step towards a more complex algorithm.

Here's a quick way of visualizing a histogram as an ASCII chart. First, we convert the histogram keys to their string representations so they can be sorted and printed. We also store the histogram value for the key, since we can't do a histogram lookup later based on the string value we'll be using.

def draw_graph(histogram, char="#")
	  pairs = histogram.keys.collect { x [x.to_s, histogram[x]] }.sort

Then we find the key with the longest string representation. We'll pad the rest of the histogram rows to this length, so that the graph bars will line up correctly.

largest_key_size = pairs.max { x,y x[0].size <=> y[0].size }[0].size

Then we print each key-value pair, padding with spaces as necessary.

pairs.inject("") do s,kv
	    s << "#{kv[0].ljust(largest_key_size)} #{char*kv[1]}\n"
	  end
	end

Here's a histogram of the color survey results from the Solution:

puts draw_graph(survey_results.values.to_histogram)
	# blue  #
	# green ##
	# red   #

This code generates a bunch of random numbers , then graphs the random distribution:

random = []
	100.times { random << rand(10) }
	puts draw_graph(random.to_histogram)
	# 0 ############
	# 1 ########
	# 2 #######
	# 3 #########
	# 4 ##########
	# 5 #############
	# 6 ###############
	# 7 ########
	# 8 #######
	# 9 ###########

Recipe 5.13. Remapping the Keys and Values of a Hash

Problem

You have two hashes with common keys but differing values. You want to create a new hash that maps the values of one hash to the values of another.

Solution

class Hash
	  def tied_with(hash)
	    remap do h,key,value
	      h[hash[key]] = value
	    end.delete_if { key,value key.nil?  value.nil? }
	  end

Here is the Hash#remap method:

def remap(hash={})
	    each { k,v yield hash, k, v }
	    hash
	  end
	end

Here's how to use Hash#tied_with to merge two hashes:

a = {1 => 2, 3 => 4}
	b = {1 => 'foo', 3 => 'bar'}
	a.tied_with(b)                          # => {"foo"=>2, "bar"=>4}
	b.tied_with(a)                          # => {2=>"foo", 4=>"bar"}

Discussion

This remap method can be handy when you want to make a similar change to every item in a hash. It is also a good example of using the yield method.

Hash#remap is conceptually similar to Hash#collect , but Hash#collect builds up a nested array of key-value pairs, not a new hash.