Bản đồ hai hướng trong clojure?

Question

Cách tốt nhất để triển khai bản đồ hai hướng trong clojure là gì? (Theo bản đồ hai hướng, tôi có nghĩa là một bản đồ liên kết có thể cung cấp cả A-> B và B-> Một truy cập. Vì vậy, trong thực tế, các giá trị bản thân sẽ là chìa khóa để đi theo hướng ngược lại.)

I giả sử tôi có thể thiết lập hai bản đồ, một bản theo từng hướng, nhưng có cách nào khác để làm điều này không?

Tôi quan tâm cả trong trường hợp chúng tôi muốn có một sự đánh giá, ngụ ý rằng không có hai khóa nào có thể ánh xạ tới cùng một giá trị và các trường hợp không áp dụng điều kiện đó.

Answer 1

Bạn luôn có thể sử dụng thư viện Java cho điều này, như một trong các bộ sưu tập trong Apache commons. TreeBidiMap thực hiện java.util.Map vì vậy nó thậm chí còn có thể thực hiện mà không cần bất kỳ nỗ lực nào.

user> (def x (org.apache.commons.collections.bidimap.TreeBidiMap.)) 
#'user/x 
user> (.put x :foo :bar) 
nil 
user> (keys x) 
(:foo) 
user> (.getKey x :bar) 
:foo 
user> (:foo x) 
:bar 
user> (map (fn [[k v]] (str k ", " v)) x) 
(":foo, :bar") 

Một số điều sẽ không làm việc mặc dù, như assoc và dissoc, vì họ mong đợi bộ sưu tập dai dẳng và TreeBidiMap là có thể thay đổi.

Nếu bạn thực sự muốn thực hiện điều này trong Clojure bản địa, bạn có thể sử dụng siêu dữ liệu để giữ hàm băm đảo ngược. Điều này vẫn sẽ tăng gấp đôi yêu cầu bộ nhớ của bạn và tăng gấp đôi thời gian cho mỗi lần thêm và xóa, nhưng tra cứu sẽ đủ nhanh và ít nhất mọi thứ được đóng gói.

(defn make-bidi [] 
    (with-meta {} {})) 

(defn assoc-bidi [h k v] 
    (vary-meta (assoc h k v) 
      assoc v k)) 

(defn dissoc-bidi [h k] 
    (let [v (h k)] 
    (vary-meta (dissoc h k) 
       dissoc v))) 

(defn getkey [h v] 
    ((meta h) v)) 

Có thể bạn sẽ phải triển khai một loạt các chức năng khác để có đầy đủ chức năng của khóa học. Không chắc chắn cách tiếp cận khả thi này là như thế nào.

user> (def x (assoc-bidi (make-bidi) :foo :bar)) 
#'user/x 
user> (:foo x) 
:bar 
user> (getkey x :bar) 
:foo 

Answer 2

Đối với hầu hết các trường hợp, tôi đã tìm thấy các công việc sau tốt:

(defn- bimap 
    [a-map] 
    (merge a-map (clojure.set/map-invert a-map))) 

này chỉ đơn giản là sẽ hợp nhất các bản đồ gốc với bản đồ đảo ngược thành một bản đồ mới, sau đó bạn có thể sử dụng các hoạt động thường xuyên bản đồ Với kết quả.

Nhanh chóng và dơ bẩn, nhưng rõ ràng bạn nên tránh việc triển khai này nếu bất kỳ khóa nào có thể giống như bất kỳ giá trị nào hoặc nếu các giá trị trong a-map không phải là duy nhất.

Answer 3

Chúng ta có thể điều chỉnh lại vấn đề này như sau:
Cho một danh sách các hàng ([a1 b1] [a2 b2] ...) chúng tôi muốn để có thể nhanh chóng tra cứu tuples bởi cả a và b. Vì vậy, chúng tôi muốn ánh xạ a -> [a b] và b -> [a b]. Điều này có nghĩa là có thể chia sẻ ít nhất tuples . Và nếu chúng ta suy nghĩ về việc thực hiện nó thì nó nhanh chóng trở nên rõ ràng rằng đây là một bảng cơ sở dữ liệu trong bộ nhớ với các cột A và B được lập chỉ mục bởi cả hai cột.

Vì vậy, bạn chỉ có thể sử dụng cơ sở dữ liệu trong bộ nhớ nhẹ.

Rất tiếc, tôi không quen với Nền tảng Java đủ để đề xuất một điều gì đó cụ thể. Trong số nguyên nhân gây ra Datomic, nhưng nó có thể là quá mức cần thiết cho trường hợp sử dụng cụ thể này. Mặt khác, nó có tính bất biến, trong đó có vẻ mong muốn đối với bạn dựa trên nhận xét của bạn cho câu trả lời của Brian.