12

プライオリティ キューを使用して、多数のカスタム オブジェクトを並べ替えて使用しています。オブジェクトには、自然な順序である「重み」があります。ただし、優先度キューに挿入されるさまざまなオブジェクトが同じ「重み」を持つ場合があります。そのような場合、キューに入れられたのと同じ順序でプライオリティ キューに並べてもらいたいと思います。

たとえば、CustomObjects A、B、C、D をその順序で追加すると、すべて同じ「重み」で、優先度キューもその順序でそれらを返す必要があります - 1 つ以上のオブジェクトをポーリングしたとしても他のものを追加する前に。

カスタム オブジェクトの CompareTo は次のとおりです。

public int compareTo(CustomObject o) {
    int thisWeight = this.weight;
    int thatWeight = o.weight;
    if(thisWeight < thatWeight){
        return -1;
    }
    else{
        return 1;
    }
}

これで最初の順序が維持されると思いましたが、そうではありません。これは、重み 1 で A、B、C を入力したときに発生します。世論調査 A; D,E も重み 1 で追加します。どういうわけか、D と E は B の後、C の前にソートされます。

PriorityQueues の Iterator が正しい順序を返さないことを認識しているため、順序を確認する能力が限られていますが、要素がキューを離れる順序を確認でき、明らかにパスをたどっていません。私がしたいこと。

提案？

4

2 に答える 2

16

挿入順序に従って順序付けする必要がある場合は、タイムスタンプに追加の要素を使用する必要があります。つまり、挿入と等しい重みを使用timestampして、どの要素が最初に挿入されたかを確認します。したがってCustomObject、次のようになります。 

class CustomObject {  
   int weight;  
   long timestamp;  
}

そして、比較は次のようになります。 

public int compareTo (CustomObject o) {  
    int thisWeight = this.weight;  
    int thatWeight = o.weight;  
    if (thisWeight != thatWeight) {  
        return thisWeight - thatWeight;  
    }  
    else {  
        return this.timestamp - o.timestamp;  
    }  
}

小さいほど、以前timestampに挿入されたことを意味するため、挿入順序を維持できます。

addまたはごとに更新するカウンターを維持することで、「論理的な」時間を使用することもできますremove。

于 2013-03-31T16:58:28.910 に答える
14

自動的にインクリメントされるシーケンス番号をセカンダリ キーとして使用し、それを使用して関係を断ち切ることができます。

Javadoc forPriorityBlockingQueueには、この手法の例が含まれています。

このクラスの操作は、同じ優先度の要素の順序について保証しません。順序付けを強制する必要がある場合は、セカンダリ キーを使用してプライマリ プライオリティ値の同点を解消するカスタム クラスまたはコンパレータを定義できます。たとえば、比較可能な要素に先入れ先出しのタイブレークを適用するクラスを次に示します。FIFOEntry(anEntry)これを使用するには、単純なエントリ オブジェクトの代わりに新しいオブジェクトを挿入します。

class FIFOEntry<E extends Comparable<? super E>>
     implements Comparable<FIFOEntry<E>> {
   final static AtomicLong seq = new AtomicLong();
   final long seqNum;
   final E entry;
   public FIFOEntry(E entry) {
     seqNum = seq.getAndIncrement();
     this.entry = entry;
   }
   public E getEntry() { return entry; }
   public int compareTo(FIFOEntry<E> other) {
     int res = entry.compareTo(other.entry);
     if (res == 0 && other.entry != this.entry)
       res = (seqNum < other.seqNum ? -1 : 1);
     return res;
   }
 }
于 2013-03-31T16:58:00.977 に答える