2009-03-22 6 views
7

私のプログラムの別の部分で使用するために、javaのPriorityQueueクラスをclojureでラップしたいと思います。私が理解しようとしているのは、これを淡々として行い、優先順位キューを不変にする方法があるかどうかです。これを行うには良い方法はありますか、あるいは私はただ変更可能なデータ構造としてPriorityQueueを使う方が良いでしょうか?ClojureでJavaクラスを不変にするにはどうすればよいですか?

答えて

8

変更可能なデータ構造を不変のものとして包む簡単な方法はないと思います。不変なデータ構造は、新しいバージョンが旧バージョンと賢明にデータを共有できるときに効率的になります。PriorityQueueの内部へのアクセスなしにこれがどのように行われるかは実際にはわかりません。

永続的優先度キューthis threadが本当に必要な場合は面白いかもしれません。それらは線形時間の挿入を持っているようですが、それが問題であれば別の実装を探す必要があるかもしれません。

編集:第2の考えでは、永続的優先度キューの簡単な実装は、(prio、value)のペアをソートされたセットに格納することです。

(defn make-pqueue [] 
    (sorted-set)) 

(defn pqueue-add [pq x prio] 
    (conj pq [prio x])) 

(defn pqueue-peek [pq] 
    (first pq)) 

(defn pqueue-pop [pq] 
    (let [top (first pq)] 
    (disj pq top))) 

もちろん、上記のコードはかなり制限されています(例:複数のエントリはありません)が、そのアイデアを示しています。

+0

ソートセットは、(prio、value)のペアでどのようにprioでソートすることがわかりますか? –

+0

Clojureは辞書編集法でベクトルを比較するため、最初に優先度でソートし、次に値でソートします。 – CAdaker

+0

実際には、ソースを見ると、同じ長さのベクトルだけが辞書順に比較されます。しかし、これは問題ではない。 – CAdaker

7

自動的に変更可能なクラスを不変にすることはできません。 Javaクラスを直接呼び出して変更することができます。

不変性を強制するには、それをclojureで実装するか、javaクラスを拡張して、すべての変更可能なメソッド実装で例外をスローすることができます。

関連する問題