Picking a random hash element

1-post.md

Over the weekend, I was working on optimising some code on a game that I'm working on. The game contains a hash with a million elements which represent each point in a 1000 x 1000 grid, with the key representing a coordinate.

{Coordinate(1,1) => Cell.new, Coordinate(1,2) => Cell.new .. }

I wanted to grab a random grid point, so I figured that I'd just need a random key and find the value for that key:

@map[@map.keys.sample]

Turns out this technique is super slow.

             user     system      total        real
keys.sample  6.530000   1.460000   7.990000 (  7.994976)
rand         0.000000   0.000000   0.000000 (  0.002176)

In my contrived example below, I was able to simply use rand(hash.size) to get a random cell, knowing that the keys followed a number convention. In my case, I needed a random coordinate, which wasn't much harder to obtain.

The lesson here is that you can use hash[hash.keys.sample] as a fairly elegant solution, but only when performance isn't a great issue. If the hash is big, or you're performing that call many times, consider coming up with a smarter way to do it :)

2-benchmark.rb

require 'benchmark'
hash = {}
1000000.times{|i| hash[i] = i}

Benchmark.bm do |bm|
  bm.report("keys.sample") do
    1000.times{ hash[hash.keys.sample] }
  end
  bm.report("rand") do
    1000.times{ hash[rand(hash.size)] }
  end
end