12

clojure で双方向マップを実装する最良の方法は何でしょうか? (双方向マップとは、A->B と B->A の両方のアクセスを提供できる連想マップを意味します。したがって、実際には、値自体が反対方向に進むためのキーになります。)

各方向に 1 つずつ、2 つのマップを設定できると思いますが、これを行うより慣用的な方法はありますか?

2 つのキーが同じ値にマップできないことを意味する全単射が必要な場合と、その条件が課されていない場合の両方に興味があります。

4

3 に答える 3

13

これには、 Apache commonsのコレクションの 1 つなど、いつでも Java ライブラリを使用できます。TreeBidiMap が実装されjava.util.Mapているため、何の努力もせずに seq も可能です。

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")

ただし、永続的なコレクションが必要で TreeBidiMap が変更可能であるため、assocやのように機能しないものもあります。dissoc

本当にこれをネイティブ Clojure で行いたい場合は、メタデータを使用して逆方向ハッシュを保持できます。これでもメモリ要件が 2 倍になり、追加と削除のたびに時間が 2 倍になりますが、ルックアップは十分に高速で、少なくともすべてがバンドルされています。

(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))

もちろん、完全な機能を得るには、おそらく他の多くの機能を実装する必要があります。このアプローチがどれほど実現可能かはわかりません。

user> (def x (assoc-bidi (make-bidi) :foo :bar))
#'user/x
user> (:foo x)
:bar
user> (getkey x :bar)
:foo
于 2009-07-26T00:14:39.190 に答える
5

ほとんどの場合、次の方法で問題なく動作することがわかりました。

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

これにより、元のマップと反転したマップが新しいマップに単純にマージされ、その結果に対して通常のマップ操作を使用できます。

これは簡単で汚いですが、いずれかのキーがいずれかの値と同じである可能性がある場合、または の値a-mapが一意でない場合は、明らかにこの実装を避ける必要があります。

于 2013-05-13T21:45:35.857 に答える
1

この問題を次のように再構成できます。
タプルのリストが与えられた場合、と の([a1 b1] [a2 b2] ...)両方でタプルをすばやく検索できるようにする必要がaありbます。したがって、マッピングa -> [a b]とが必要ですb -> [a b]。これは、少なくともタプル[a b]を共有できることを意味します。そして、それを実装することを考えると、これが列 A と列 B の両方の列によってインデックス付けされたインメモリ データベース テーブルであることがすぐに明らかになります。

したがって、軽量のインメモリ データベースを使用できます。

申し訳ありませんが、特定の何かを推奨するほど Java プラットフォームに精通していません。当然、Datomicが思い浮かびますが、この特定のユース ケースではやり過ぎになる可能性があります。一方、ブライアンの回答に対するコメントに基づいて、あなたにとって望ましいと思われる不変性が組み込まれています。

于 2013-05-14T06:19:39.450 に答える