Using Ruby, what is the most efficient way to check if any key in a hash matches any values within an Array
I want to compare the keys in a hash of parameters against an array of elements for a match.
For exa开发者_如何学JAVAmple:
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
}
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) }
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"]
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?
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.
精彩评论