Tabela mieszania dwukierunkowego w języku Ruby

Question

Potrzebuję dwukierunkowej tabeli skrótu w języku Ruby. Na przykład:

h = {:abc => 123, :xyz => 789, :qaz => 789, :wsx => [888, 999]} 
h.fetch(:xyz) # => 789 
h.rfetch(123) # => abc 
h.rfetch(789) # => [:xyz, :qaz] 
h.rfetch(888) # => :wsx 

Method rfetch oznacza odwrócony pobrać i jest tylko moja propozycja.

Uwaga trzy rzeczy:

1. Jeśli kilka klawiszy map przy tej samej wartości następnie rfetch zwraca wszystkie z nich, zapakowane w tablicy.
2. Jeśli wartością jest tablica, wówczas rfetch szuka jej parametru wśród elementów tablicy.
3. Hash dwukierunkowy oznacza, że ​​zarówno fetch, jak i rfetch powinny być wykonywane w stałym czasie.

Czy taka struktura istnieje w Ruby (w tym w bibliotekach zewnętrznych)?

Zastanowiłem się nad jego implementacją za pomocą dwóch jednokierunkowych skrótów synchronizowanych, gdy jedna z nich jest modyfikowana (i pakowana w klasę, aby uniknąć problemów z synchronizacją), ale może mógłbym użyć już istniejącego rozwiązania?

Answer 1

Można zbudować coś całkiem łatwo, wystarczy użyć prostego obiektu, który otacza dwa hashe (jeden dla kierunku do przodu, drugi dla rewersu). Na przykład:

class BiHash 
    def initialize 
     @forward = Hash.new { |h, k| h[k] = [ ] } 
     @reverse = Hash.new { |h, k| h[k] = [ ] } 
    end 

    def insert(k, v) 
     @forward[k].push(v) 
     @reverse[v].push(k) 
     v 
    end 

    def fetch(k) 
     fetch_from(@forward, k) 
    end 

    def rfetch(v) 
     fetch_from(@reverse, v) 
    end 

    protected 

    def fetch_from(h, k) 
     return nil if(!h.has_key?(k)) 
     v = h[k] 
     v.length == 1 ? v.first : v.dup 
    end 
end 

Look up będzie zachowywać się tak jak normalnych wyszukiwań hash (bo są normalne wyszukiwań hash). Dodaj niektórych operatorów i może przyzwoite implementacje to_s i inspect i jesteś dobry.

Takie rzeczy działa tak:

b = BiHash.new 
b.insert(:a, 'a') 
b.insert(:a, 'b') 
b.insert(:a, 'c') 
b.insert(:b, 'a') 
b.insert(:c, 'x') 

puts b.fetch(:a).inspect   # ["a", "b", "c"] 
puts b.fetch(:b).inspect   # "a" 
puts b.rfetch('a').inspect   # [:a, :b] 
puts b.rfetch('x').inspect   # :c 
puts b.fetch(:not_there).inspect # nil 
puts b.rfetch('not there').inspect # nil 

Nie ma nic złego w budowaniu narzędzi, gdy są potrzebne.

Answer 2

Spróbuj tego:

class Hash 
    def rfetch val 
    select { |k,v| v.is_a?(Array) ? v.include?(val) : v == val }.map { |x| x[0] } 
    end 
end 

Answer 3

Nie ma takiej struktury wbudowane w Ruby.

Zauważ, że Hash#rassoc robi coś podobnego, ale zwraca tylko pierwszy mecz i jest liniowa w czasie:

h = {:abc => 123, :xyz => 789, :qaz => 789, :wsx => [888, 999]} 
h.rassoc(123) # => [:abc, 123] 

Ponadto, nie jest możliwe, aby napełnić swoje wymagania w Ruby w zupełnie bezpieczny sposób, ponieważ nie będziesz w stanie wykryć zmian wartości, które są tablicami. Np .:

h = MyBidirectionalArray.new(:foo => 42, :bar => [:hello, :world]) 
h.rfetch(:world) # => :bar 
h[:bar].shift 
h[:bar] # => [:world] 
h.rfetch(:world) # => should be nil, but how to detect this?? 

Obliczanie skrótu za każdym razem w celu wykrycia zmiany spowoduje, że wyszukiwanie będzie przebiegać liniowo. Można jednak zduplikować wartości tablic i je zamrozić (tak jak Ruby robi dla kluczy skrótu będących ciągami!).

Potrzebna jest klasa Graph, która może mieć inne API niż Hash, nie? Możesz sprawdzić rgl lub podobną, ale nie wiem, w jaki sposób są one realizowane.

Powodzenia.

Answer 4

Jeśli nie robisz wielu aktualizacji tego skrótu, możesz użyć inverthash.

Answer 5

Istnieje metoda Hash#invert (http://www.ruby-doc.org/core-2.1.0/Hash.html#method-i-invert), aby to osiągnąć. Nie będzie jednak mapował wielu wartości do tablicy.