java - PriorityQueue \ java

Question

コレクション全体を別のコレクションにコピーして poll メソッドを使用するよりも、自然な順序で PQ を使用して toString を出力するより良い方法について考えることはできません。

他の提案はありますか？

Answer 1

完全にソートされた場合の PriorityQueue の順序が必要な場合は、それを TreeSet のような Sorted コレクションにコピーする必要があります

例えば

System.out.println(new TreeSet(pq)); // prints elements naturally sorted.

注: これは重複を破棄しますが、PriorityQueue はそうしません。

---

並べ替えは O(n * log n) で、印刷は O(n) ですが、これだけではありません。メモリ内での並べ替えは、IO を使用するよりもはるかに高速です。つまり、並べ替えをより重要にするには、非常に大きなキューが必要になります。

public static void main(String... args) {
    PriorityQueue<Double> pq = new PriorityQueue<Double>();
    for (int i = 0; i < 10*1000 * 1000; i++)
        pq.add(Math.random());
    long start1 = System.nanoTime();
    Set<Double> set = new TreeSet<Double>(pq);
    long time1 = System.nanoTime() - start1;

    long start2 = System.nanoTime();
    for (Double d : set) {
        System.out.println(d);
    }
    long time2 = System.nanoTime() - start2;
    System.out.printf("It took %.3f seconds to sort, and %.3f seconds to print %,d doubles%n", time1 / 1e9, time2 / 1e9, pq.size());
}

最後にプリント

It took 28.359 seconds to sort, and 94.844 seconds to print 10,000,000 doubles

配列を使用してソートすると、

Double[] doubles = pq.toArray(new Double[pq.size()]);
Arrays.sort(doubles);

It took 8.377 seconds to sort ....

つまり、並べ替えが最も重要になるのに十分な長さのキューを用意する前に、メモリが不足するか、文字列の最大長を超える可能性があります。

Answer 2

toString()Anyコレクションに追加しているオブジェクトのメソッドをオーバーライドする必要があり、toStringメソッドは正常に動作します

    PriorityQueue<String> priorityQueue = new PriorityQueue<String>();
    priorityQueue.add("one");
    priorityQueue.add("two");
    priorityQueue.add("three");
    System.out.println(priorityQueue);//Prints [one, two, three]