Ruby의 양방향 해시 테이블

Question

Ruby에서 양방향 해시 테이블이 필요합니다. 예를 들어 :

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 

방법 반전 rfetch 의미 는을 가져오고 단지 내 제안이다.

주 세 가지가 :

1. 여러 개의 키가 같은 값에 rfetch 반환 그들 모두를 매핑 할 경우, 배열에 포장.
2. 값이 배열 인 경우 rfetch은 배열의 요소 중에서 해당 매개 변수를 찾습니다.
3. 양방향 해시는 fetch과 rfetch이 일정한 시간 내에 실행되어야 함을 의미합니다.

이러한 구조는 Ruby (외부 라이브러리 포함)에 있습니까?

두 개의 단방향 해시 중 하나를 수정하여 (동기화 문제를 피하기 위해 클래스로 패킹 할 때) 동기화 할 생각을했지만 어쩌면 기존 솔루션을 사용할 수 있을까요?

Answer 1

무언가를 매우 쉽게 만들 수 있습니다. 두 개의 해시를 감싸는 단순한 객체 만 사용하면됩니다 (하나는 앞으로, 다른 하나는 뒤집기). 예를 들어 : (그들은 이 정상 해시 조회이기 때문에)

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 

봐 올린다는 정상 해시 조회처럼 작동합니다. 일부 연산자와 어쩌면 괜찮은 to_s 및 inspect 구현을 추가하면 좋을 것입니다.

이러한 점은 다음과 같이 작동

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 

당신이 그들을 필요로 할 때 당신의 도구를 구축 아무 문제가 없습니다.

Answer 2

이 시도 :

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

내장 된 루비에서 그런 구조가 없다.

Hash#rassoc 비슷한 무언가를하지만 첫 번째 경기를 반환하고 선형 시간하는 것으로

:

또한

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

, 완벽하게 안전한 방식으로 루비의 요구 사항을 fullfill에 할 수 없습니다, 배열 인 값의 변경을 감지 할 수 없기 때문입니다. 예 : 변경 사항을 감지하기 위해 해시를 계산하면 선형 시간이 달라집니다. 배열 값을 복제하고 동결시킬 수 있습니다 (Ruby는 해시 키가 문자열 인 것처럼!)

Hash과 다른 API를 가질 수있는 Graph 클래스가 필요합니까? rgl 또는 그와 비슷한 것을 확인할 수 있지만 구현 방법을 모르겠습니다.

행운을 빈다.

Answer 4

이 해시를 많이 업데이트하지 않는 경우 inverthash을 사용할 수 있습니다.

Answer 5

이 작업을 수행하려면 메서드 (http://www.ruby-doc.org/core-2.1.0/Hash.html#method-i-invert)가 있습니다. 배열에 여러 값을 매핑하지는 않습니다.