8

プログラムの別の部分で使用するために、Java の PriorityQueue クラスを clojure でラップしたいと考えています。私が理解しようとしているのは、これを巧妙な方法で実行し、優先キューを不変にする方法があるかどうかです。これを行う良い方法はありますか、それとも PriorityQueue を変更可能なデータ構造として使用したほうがよいでしょうか?

4

2 に答える 2

9

可変データ構造を不変データ構造としてラップする簡単な方法はないと思います。新しいバージョンが巧妙な方法で古いバージョンとデータを共有できる場合、不変のデータ構造は効率的になりますPriorityQueue。

永続的な優先キューが本当に必要な場合は、このスレッドが興味深いかもしれません。ただし、これらには線形時間の挿入があるようです。そのため、それが問題である場合は、別の実装を探す必要があります。

編集: よく考えてみると、永続的な優先度キューの単純な実装は、(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)))

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

于 2009-03-22T23:15:32.710 に答える
8

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

不変性を強制するには、clojure で実装するか、Java クラスを拡張してすべての可変メソッド実装で例外をスローします。

于 2009-03-23T12:32:08.770 に答える