Рубин эффективный способ получить несколько ключей хеш-функции для заданного значения

Question

Какой самый эффективный способ получить все ключи хеш-функции из заданного значения.

my_hash = {"a"=>"aa", "b"=>"bb", "c"=>"bb"}

Я хочу дать хэш "bb" в качестве входного значения и вернуть все их ключи (b, c) обратно в виде массива

Возвращает только один ключ:

my_hash.index("bb")
# returns only b

Это работает, но кажется неэффективным:

my_hash.select{|k,v| v == 'bb' }.map{|i| i[0] }
# returns b and c

Я прочитал все документы. Я чувствую, что есть что-то очевидное, что я упускаю.

Спасибо!

Обновление:

Я закончил тем, что переключил ключи и значения для создания хэша и пошел с массивом для значений. Это более эффективное решение. Ниже вы найдете информацию о лучших способах поиска значений, если это необходимо.

Новая структура:

my_hash = {"aa"=>["a"],"bb"=>["b","c"]}

Answer 1

Немного быстрее:

my_hash.map{ |k,v| v=='bb' ? k : nil }.compact

Медленнее для небольшого хэша и только для одного запроса.Быстрее, если вам нужно запросить обратное отображение для нескольких значений.Я бы порекомендовал сохранить обратную карту, если это важно для вашего приложения.

rev = Hash.new{ |h,k| h[k]=[] }
my_hash.each{ |k,v| rev[v] << k }
rev['bb']

Бенчмарк:

require 'benchmark'
N = 1_000_000
my_hash = {"a"=>"aa", "b"=>"bb", "c"=>"bb"}

Benchmark.bmbm do |x|
  x.report('select/map'){ N.times{
    my_hash.select{|k,v|v=='bb'}.map{|i| i[0]}
  }}
  x.report('select/map/destructure'){ N.times{
    my_hash.select{|k,v|v=='bb'}.map{|k,v| k}
  }}
  x.report('map/compact'){ N.times{
    my_hash.map{|k,v|v=='bb' ? k : nil}.compact        
  }}
  x.report('reverse map'){ N.times{
    rev = Hash.new{|h,k|h[k]=[]}
    my_hash.each{ |k,v| rev[v]<<k }
    rev['bb']
  }}
  x.report('reject'){ N.times{
    my_hash.reject{|k,v|v != "bb"}.keys
  }}
end
#=> Rehearsal ----------------------------------------------------------
#=> select/map               1.950000   0.000000   1.950000 (  1.950137)
#=> select/map/destructure   1.960000   0.010000   1.970000 (  1.963740)
#=> map/compact              1.200000   0.000000   1.200000 (  1.197340)
#=> reverse map              3.660000   0.000000   3.660000 (  3.658245)
#=> reject                   2.110000   0.000000   2.110000 (  2.115805)
#=> ------------------------------------------------ total: 10.890000sec
#=> 
#=>                              user     system      total        real
#=> select/map               1.950000   0.000000   1.950000 (  1.948784)
#=> select/map/destructure   1.970000   0.010000   1.980000 (  1.966636)
#=> map/compact              1.190000   0.000000   1.190000 (  1.192052)
#=> reverse map              3.670000   0.000000   3.670000 (  3.664798)
#=> reject                   2.140000   0.000000   2.140000 (  2.135069)

Answer 2

Поскольку хэши даже не упорядочены по значению (что МОЖЕТ немного ускорить процесс, возможно, позволив использовать бинарный поиск), вы не найдете способа сделать это, не пройдя весь хеш, так что ваше решение на самом деле выглядит наиболее эффективным.

Альтернативой может быть:

my_hash.reject{|k,v|v != "bb"}.keys

Это немного короче по кодам, но ИМХО также немного сложнее для понимания, чем ваша версия. Также метод reject создает копию хэша, поэтому он требует больше памяти. Если вас не интересует исходный хеш, используйте delete_if, который работает на месте:

my_hash.delete_if{|k,v|v != "bb"}.keys

Answer 3

Ассоциативные структуры данных, благодаря своей конструкции, позволяют быстро искать значение по ключу.Они не предназначены для эффективного поиска ключей по значению.

В C ++ std :: map не делает это эффективно, но делает boost :: bimap.Я не знаю, как это работает, но логически это может сработать, создав две карты (ключ к значению и значение к ключу) и сделав интерфейс, чтобы он выглядел так, как будто они едины.Вы могли бы сделать то же самое.Поскольку ваша карта кажется однозначной в одном направлении и многозначной в другом направлении (т. Е. Нет однозначного соответствия), я сомневаюсь, что есть много готовых библиотек, которые делают именно то, что вы хотите.: Я не знаю Ruby.

Answer 4

Другая альтернатива: my_hash.find_all{|k,v|v == "bb"}.map(&:first)

Не самый быстрый, но приятный для глаз человека:)

Использование теста Фрогза:

Rehearsal ----------------------------------------------------------
select/map               3.604000   0.000000   3.604000 (  3.638208)
select/map/destructure   3.682000   0.000000   3.682000 (  3.678210)
map/compact              2.620000   0.000000   2.620000 (  2.620150)
reverse map              5.991000   0.000000   5.991000 (  5.985342)
reject                   3.572000   0.000000   3.572000 (  3.612207)
find_all/map             2.964000   0.000000   2.964000 (  2.965169)
------------------------------------------------ total: 22.433000sec

                             user     system      total        real
select/map               3.619000   0.000000   3.619000 (  3.634207)
select/map/destructure   3.698000   0.000000   3.698000 (  3.702212)
map/compact              2.589000   0.000000   2.589000 (  2.620150)
reverse map              5.913000   0.000000   5.913000 (  6.013344)
reject                   3.557000   0.000000   3.557000 (  3.569204)
find_all/map             2.948000   0.000000   2.948000 (  2.959169)