4

重複の可能性：
Java：優先キューから作成されたキューの順序がおかしい

次のコンパレータを実装して、優先キューをキューに変えるのに疲れました。

  • ハック：QueueComparatorは、常に1を返すことにより、PriorityQueueをキュー（FIFO）のように動作させます。
  • 優先キューの「自然順序付け」は先頭に最小の要素があり、従来のコンパレータは最初が2番目よりも小さい場合に-1を返すため、ハッキングされたコンパレータは常に1を返し、現在の（最後の）正方形が配置されます。末尾で（再帰的に）

コードは次のとおりです。

import java.util.Comparator;
public class QueueComparator implements Comparator<Square>{
    public int compare(Square square1, Square square2)
    {
        return 1;
    }
}

しかし、結果として生じる「キュー」は、物事を整理しません（FIFO）。なんで？

4

4 に答える 4

9

問題は、なぜそれが必要なのかということです。

まず、コンパレータは完全に壊れています。これは、コンパレータが次のような基本的な制約に違反しているためです。

sign(compare(a,b)) = - sign(compare(b,a))

と

compare(a,a) == 0

したがって、それを使用するものはすべて、エントリの喪失、無限ループでの実行、スタックオーバーフローのスローなど、あらゆる種類の結果をもたらす可能性があります...

を実装したい場合は、IDontGiveAShitComparator常に0を返す必要があります。コンパレータに依存するすべてのものがそれを処理できるはずです。

どのような順序の結果が得られるかは、まだ実装次第です。要素をリストに格納する場合、FIFOまたはLIFOはある種の可能性があります。バランスの取れたツリーに格納する場合、おそらく常に片側に要素を追加し、ツリーのバランスを取り直し、ほとんどすべてを混乱させます。

多分それはハッシュに基づく何かを使用します、その場合同じ優先順位を持つすべての要素はそれらのハッシュ値によって順序付けられて出てくるかもしれません。

于 2012-10-04T07:44:42.077 に答える
4

まあ、それはハックです。だから、それが機能していなくても、私はそれほど驚かないでしょう。

PriorityQueueのJavadocは次のように述べています。

このキューの先頭は、指定された順序に関して最小の要素です。複数の要素が最小値で結び付けられている場合、ヘッドはそれらの要素の1つです-結びつきは任意に解除されます。

さて、あなたはそれを持っています。コンパレータが要素のすべてのペアに対して同じ値を返す場合は、同点しかありません。したがって、キューの順序は実際には任意です。

于 2012-10-04T07:39:51.907 に答える
4

compareTo(a,b)一般に、を返し-compare(b,a)、compareTo(a,a)ゼロを返す必要があります。コンパレータはこれら両方のルールに違反しています。

Javadocを確認してください。

于 2012-10-04T07:44:44.633 に答える
0

優先度付きキューの一般的な実装は、バイナリヒープを使用して行われます（デフォルトのJava実装も同様です）。コンパレータは、ヒーププロパティ（ノードは常にそのすべての子に対してより大きい/等しい（または小さい/等しい））を真に保つためにのみ使用されます。コンパレータが常に1を返す場合、PriotityQueueの動作により、挿入後にヒーププロパティを復元しようとしたときに予期しない動作が発生する可能性がありますが、FIFOキューで終了することはありません。

BinaryHeapはツリーとして編成されているため、実際の「テール」はないことに注意してください。最後に来る必要がある要素はリーフノードですが、「最後」ではありません。

于 2012-10-04T07:45:15.500 に答える