1

以下のコードでは、PrioriyQueue を作成する際に 10 の意味を知りたいと考えています。初期容量はわかっていますが、パフォーマンスに影響しますか??

import java.util.*;

class Test {
    static class PQsort implements Comparator<Integer> { // inverse sort
        public int compare(Integer one, Integer two) {
            return two - one; // unboxing
        }
    }

    public static void main(String[] args) {
        int[] ia = { 1, 5, 3, 7, 6, 9, 8 }; // unordered data
        PriorityQueue<Integer> pq1 = new PriorityQueue<Integer>(); // use
                                                                    // natural
                                                                    // order
        for (int x : ia)
            pq1.offer(x);
        for (int x : ia)
            // review queue
            System.out.print(pq1.poll() + " ");
        System.out.println("");
        PQsort pqs = new PQsort(); // get a Comparator
        PriorityQueue<Integer> pq2 = new PriorityQueue<Integer>(10, pqs); // use
                                                                            // Comparator
        for (int x : ia)
            // load queue
            pq2.offer(x);
        System.out.println("size " + pq2.size());
        System.out.println("peek " + pq2.peek());
        System.out.println("size " + pq2.size());
        System.out.println("poll " + pq2.poll());
        System.out.println("size " + pq2.size());
        for (int x : ia)
            // review queue
            System.out.print(pq2.poll() + " ");
    }
}
4

2 に答える 2

1

Javadocは次のように説明しています。

プライオリティ キューは無制限ですが、キューに要素を格納するために使用される配列のサイズを制御する内部容量があります。これは常に、少なくともキュー サイズと同じ大きさです。要素が優先キューに追加されると、その容量は自動的に増加します。成長方針の詳細は明記されていません。

言い換えれば、初期容量を指定できることは、キューが内部配列の拡張に多くの時間を費やしていることがわかった場合にパフォーマンスを最適化する方法です。

于 2012-05-23T07:37:27.757 に答える
0

API ドキュメントでは、容量について説明しています。内部配列のサイズです。

http://download.java.net/jdk7/archive/b123/docs/api/java/util/PriorityQueue.html

Allowing you to specify an initial capacity is a small optimization. 
If you know how many entries you will need, you can save the (tiny) time 
spent growing the queue to the required size, by sizing it correctly 
from the start.
于 2012-05-23T07:40:53.293 に答える