ホームページ  >  記事  >  Java  >  Java 並行プログラミングでの PriorityBlockingQueue の使用方法の詳細な説明

Java 並行プログラミングでの PriorityBlockingQueue の使用方法の詳細な説明

王林
王林転載
2023-05-08 08:43:071361ブラウズ

    PriorityBlockingQueue は、Java でヒープ データ構造を実装する、スレッドセーフな境界付きブロッキング キューです。マルチスレッドのシナリオで要素を安全に追加、削除、取得でき、優先度に従って要素を並べ替えることができます。

    1. PriorityBlockingQueue の概要

    PriorityBlockingQueue クラスは BlockingQueue インターフェイスを実装しており、AbstractQueue クラスを継承するスレッドセーフ キューであり、AbstractQueue クラスが Queue インターフェイスを実装します。 PriorityBlockingQueue は、コンストラクターで容量を指定できる有界キューです。指定しない場合、デフォルトのサイズは Integer.MAX_VALUE です。同時に、PriorityBlockingQueue は内部的にヒープ データ構造を実装しているため、要素の優先順位に応じたソートもサポートしています。

    2. PriorityBlockingQueue のソースコード分析

    1. コンテナ

    PriorityBlockingQueue は内部的にオブジェクト型の配列キューを使用して要素を格納し、また int 型の変数サイズを使用して要素を格納します. 要素の数を記録します。以下は、PriorityBlockingQueue クラスの定義です:

    private transient Object[] queue;
    private transient int size;

    2. Comparator

    PriorityBlockingQueue は、要素の優先順位に従って並べ替えることができます。これは、PriorityBlockingQueue が小さなルート ヒープまたは大きなルートを維持するためです。内部的にヒープします。コンストラクターでは、要素の並べ替えに要素独自の比較メソッドまたはカスタム コンパレーターの使用を選択できます。コンパレータが指定されていない場合、PriorityBlockingQueue は並べ替えに要素独自の比較方法を使用します。

    private final Comparator<? super E> comparator;

    3. コンストラクター

    PriorityBlockingQueue は複数のコンストラクターを提供します。パラメーターなしのコンストラクターを使用して、デフォルトの容量 Integer.MAX_VALUE を持つ PriorityBlockingQueue を作成するか、初期容量のコンストラクターと一緒に使用するかを選択できます。またはカスタムコンパレータ。以下は、PriorityBlockingQueue クラスの 2 つのコンストラクターです:

    public PriorityBlockingQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }
    public PriorityBlockingQueue(int initialCapacity, Comparator<? super E> comparator) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }

    4. 要素の追加

    PriorityBlockingQueue に要素を追加するメソッドは、offer() メソッドです。最初に、容量が十分であるかどうかを確認します。容量が足りない場合は、元の配列の長さを半分にする拡張操作が実行されます。次に、新しい要素をキューの最後に追加し、siftUp() メソッドを通じて要素を適切な位置にフィルタリングして、ヒープのプロパティを維持します。

    public boolean offer(E e) {
        if (e == null)
            throw new NullPointerException();
        final ReentrantLock lock = this.lock;
        lock.lock();
        int n, cap;
        Object[] array;
        while ((n = size) >= (cap = (array = queue).length))
            tryGrow(array, cap);
        try {
            Comparator<? super E> cmp = comparator; 
            if (n == 0) { array[0] = e; } 
            else { siftUp(n, e, array, cmp); } 
            size = n + 1; notEmpty.signal(); 
        } finally { 
            lock.unlock(); 
        } 
        return true; 
    }

    5. 要素の取得

    PriorityBlockingQueue の要素を取得するメソッドは take() メソッドです。最初にキューが空かどうかがチェックされます。キューが空の場合は、現在のスレッドが要素がキューに追加されるまでブロックされます。次に、キューの先頭要素を取得し、 siftDown() メソッドを通じてキューの最後の要素を先頭に移動して、ヒープのプロパティを維持します。

    public E take() throws InterruptedException { 
        final ReentrantLock lock = this.lock; 
        lock.lockInterruptibly(); 
        E result; 
        try { 
            while (size == 0) notEmpty.await(); 
            result = extract(); 
        } finally {
            lock.unlock(); 
        } 
        return result; 
    }
    private E extract() { 
        final Object[] array = queue; 
        final E result = (E) array[0]; 
        final int n = --size; 
        final E x = (E) array[n]; 
        array[n] = null; 
        if (n != 0) 
        siftDown(0, x, array, comparator); 
        return result; 
    }

    6. ヒープ プロパティの維持

    PriorityBlockingQueue は、要素の優先順位を維持するために小さなルート ヒープまたは大きなルート ヒープを使用します。ここでは例として小さなルート ヒープを取り上げます。小さなルート ヒープの特徴は、親ノードの値が左右の子ノードの値以下であることです。PriorityBlockingQueue のヒープは配列を通じて実装されます。要素が追加されると、新しい要素はキューの最後に追加され、ヒープのプロパティを維持するために siftUp() メソッドを通じて適切な位置までフィルタリングされます。要素を取得するとキューの先頭要素が取得され、ヒープの性質を維持するために siftDown() メソッドによってキューの末尾要素が先頭に移動されます。以下は、siftUp() メソッドと siftDown() メソッドのコード実装です。

    private static <T> 
    void siftUp(int k, T x, Object[] array, Comparator<? super T> cmp) { 
        if (cmp != null) 
        siftUpUsingComparator(k, x, array, cmp); 
        else siftUpComparable(k, x, array); 
    }
    @SuppressWarnings("unchecked") 
    private static <T> 
    void siftUpUsingComparator(int k, T x, Object[] array, Comparator<? super T> cmp) { 
        while (k > 0) { 
            int parent = (k - 1) >>> 1; 
            Object e = array[parent]; 
            if (cmp.compare(x, (T) e) >= 0) 
            break; 
            array[k] = e; 
            k = parent; 
        } 
        array[k] = x; 
    }
    @SuppressWarnings("unchecked") 
    private static <T> 
    void siftUpComparable(int k, T x, Object[] array) { 
        Comparable<? super T> key = (Comparable<? super T>) x; 
        while (k > 0) { 
            int parent = (k - 1) >>> 1; 
            Object e = array[parent]; 
            if (key.compareTo((T) e) >= 0) 
            break; 
            array[k] = e; 
            k = parent; 
        } 
        array[k] = key; 
    }
    private static <T> 
    void siftDown(int k, T x, Object[] array, Comparator<? super T> cmp) { 
        if (cmp != null) 
        siftDownUsingComparator(k, x, array, cmp); 
        else siftDownComparable(k, x, array); 
    }
    @SuppressWarnings("unchecked") 
    private static <T> 
    void siftDownUsingComparator(int k, T x, Object[] array, Comparator<? super T> cmp) { 
        int half = size >>> 1; 
        while (k < half) { 
            int child = (k << 1) + 1; 
            Object c = array[child]; 
            int right = child + 1; 
            if (right < size && cmp.compare((T) c, (T) array[right]) > 0) 
            c = array[child = right]; 
            if (cmp.compare(x, (T) c) <= 0) 
            break; 
            array[k] = c; 
            k = child; 
        } 
        array[k] = x; 
    }
    @SuppressWarnings("unchecked") 
    private static <T> 
    void siftDownComparable(int k, T x, Object[] array) { 
        Comparable<? super T> key = (Comparable<? super T>) x; 
        int half = size >>> 1; 
        while (k < half) { 
            int child = (k << 1) + 1; 
            Object c = array[child]; 
            int right = child + 1; 
            if (right < size && ((Comparable<? super T>) c).compareTo((T) array[right]) > 0) 
            c = array[child = right]; 
            if (key.compareTo((T) c) <= 0) 
            break; 
            array[k] = c; 
            k = child; 
        } 
        array[k] = key; 
    }

    siftUp() メソッドと siftDown() メソッドはどちらも siftUpUsingComparator() メソッドと siftDownUsingComparator() メソッドを使用します。ヒープの上部フィルターと下部フィルターを実装します。 PriorityBlockingQueue が Comparator を指定しない場合、要素自体の Comparable を使用してヒープの上位および下位のフィルタリングが実装されます。

    以上がJava 並行プログラミングでの PriorityBlockingQueue の使用方法の詳細な説明の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

    声明:
    この記事はyisu.comで複製されています。侵害がある場合は、admin@php.cn までご連絡ください。