Bảng băm hai chiều trong Ruby

Question

Tôi cần một bảng Hash hai chiều trong Ruby. Ví dụ:

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 

Phương pháp rfetch nghĩa đảo ngược lấy và duy nhất là đề nghị của tôi.

Lưu ý ba điều:

1. Nếu bản đồ nhiều phím ở cùng giá trị sau đó rfetch trả về tất cả trong số họ, đóng gói trong mảng.
2. Nếu giá trị là một mảng thì rfetch tìm kiếm thông số của nó trong số các phần tử của mảng.
3. Hash hai chiều có nghĩa là cả hai fetch và rfetch sẽ được thực thi trong thời gian không đổi.

Cấu trúc này có tồn tại trong Ruby (bao gồm thư viện bên ngoài) không?

Tôi đã nghĩ đến việc triển khai nó bằng cách sử dụng hai Hashes một chiều được đồng bộ hóa khi một trong số chúng được sửa đổi (và đóng gói nó vào lớp để tránh các vấn đề đồng bộ hóa).

Answer 1

Bạn có thể tự xây dựng một thứ gì đó dễ dàng, chỉ cần sử dụng một đối tượng đơn giản bao bọc hai băm (một cho hướng chuyển tiếp, một cho hướng ngược lại). Ví dụ:

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 sẽ cư xử giống như tra cứu băm bình thường (vì họ là tra cứu băm bình thường). Thêm một số toán tử và có thể triển khai to_s và inspect phong nha và bạn tốt.

một điều như vậy làm việc như thế này:

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 

Không có gì sai với việc xây dựng các công cụ của bạn khi bạn cần đến chúng là.

Answer 2

Hãy thử điều này:

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

Không có cấu trúc như vậy tích hợp sẵn trong Ruby.

Lưu ý rằng Hash#rassoc làm điều gì đó tương tự, nhưng nó sẽ trả về chỉ là trận đấu đầu tiên và là tuyến tính theo thời gian:

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

Ngoài ra, nó không thể fullfill yêu cầu của bạn trong Ruby một cách tuyệt đối an toàn, vì bạn sẽ không thể phát hiện các thay đổi trong các giá trị là mảng. Ví dụ:

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?? 

Tính toán băm mỗi lần để phát hiện thay đổi sẽ làm cho thời gian tìm kiếm tuyến tính của bạn. Bạn có thể sao chép mảng-giá trị và đóng băng chúng, mặc dù (như Ruby làm cho các khóa Hash là các chuỗi!)

Những gì bạn cần là một lớp Graph, có thể có một API khác với Hash, không? Bạn có thể xem rgl hoặc tương tự, nhưng tôi không biết cách chúng được triển khai.

Chúc may mắn.

Answer 4

Nếu bạn không thực hiện nhiều cập nhật cho hàm băm này, bạn có thể sử dụng inverthash.

Answer 5

Có phương pháp Hash#invert (http://www.ruby-doc.org/core-2.1.0/Hash.html#method-i-invert) để đạt được điều này. Nó sẽ không bản đồ nhiều giá trị cho một mảng mặc dù.