Using Ruby, what is the most efficient way to check if any key in a hash matches any values within an Array.

Question

I want to compare the keys in a hash of parameters against an array of elements for a match.

For example:

params          = {"key1", "key2", "key3"}
params_to_match = ["key2","key3"]

I could do this, but I'm sure there is a much more elegant way to acheive the same result

params.each_key{|key|
  if params_to_match.include?(key.to_s)
    return
  end
}

Answer 1

Not necessarily more efficient but perhaps more elegant in some sense:

return unless (params.keys & params_to_match).empty?

A more efficient way than your example would (in the general case, not necessarily with such a small toy example) be to check whether the hash contains the keys, since the time to look those up is practically constant while looking them up from the array is O(n). So, your example would become something like this:

params_to_match.each { |p| return if params.has_key?(p) }

Answer 2

Here's a fast algorithm in psedudocode.

assert keys, input are sorted
pos = beginning of keys
for i in input
  pos = keys.find(pos, i)  # find() starts search at position pos
  if not_found(pos) then return false
  ++pos
return true

This algorithm, assuming the keys and the input are sorted to begin with, performs in O(n+m), n and m being the count of keys and input. I'll leave it for you to translate that to Ruby, but pay close attention to the find() function; it must start its search at the position found in the previous iteration, not at the start of keys. Otherwise you're down to O(n^2+m), n the count of keys.

Answer 3

I think the best combination of elegant and efficient would be

return if params_to_match.any? { |p| params.has_key?(p) }

If you have ActiveSupport, you could do

return if params.slice(*params_to_match).any?

Answer 4

Use &

Set Intersection—Returns a new array containing elements common to the two arrays, with no duplicates.

[ 1, 1, 3, 5 ] & [ 1, 2, 3 ]   #=> [ 1, 3 ]

params.keys & params_to_match  #=> ["key2", "key3"]