java - PriorityQueue と PriorityBlockingQueue

Question

これらのプログラムの中からどれを選択する必要がありますか? また、その理由は何ですか? 一般に、なぜ PriorityQueue よりも PriorityBlockingQueue を使用する必要があるのかという問題があります。

PriorityBlockingQueue

import java.util.concurrent.PriorityBlockingQueue;

public class PriorityBlockingQueueExample {

    static PriorityBlockingQueue<String> priorityQueue = new PriorityBlockingQueue<String>();
    public static void main(String[] args) {

        new Thread(){
            public void run(){
                try {
                System.out.println(priorityQueue.take() +" is removed from priorityQueue object");
                } catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }    
            }
        }.start();
        new Thread(){
            public void run(){
                priorityQueue.add("string variable");
                System.out.println("Added an element to the queue");
            }
        }.start();
    }
}

これらのプログラムの中からどれを選択する必要がありますか? また、その理由は何ですか? 一般に、なぜ PriorityQueue よりも PriorityBlockingQueue を使用する必要があるのかという問題があります。PriorityQueue

import java.util.PriorityQueue;

public class PriorityQueueTest {

    static PriorityQueue<String> priorityQueue = new PriorityQueue<String>();
    private static Object lock = new Object();
    public static void main(String[] args) {

        new Thread(){
            public void run(){
                synchronized(lock){     
                    try {
                        while(priorityQueue.isEmpty()){lock.wait();}
                            System.out.println(priorityQueue.remove() +" is removed from priorityQueue object");
                            lock.notify();
                    } catch (InterruptedException e) {
                            //  TODO Auto-generated catch block
                            e.printStackTrace();
                    }
                }
            }
        }.start();
        new Thread(){
            public void run(){
                synchronized(lock){
                    priorityQueue.add("string variable");
                    System.out.println("Added an element to the queue");
                    lock.notify();
                }
            }
        }.start();
    }
}

score 19 · Accepted Answer

通常は空の場合にアクセスするQueueと戻りますが、キューが空の場合は、値が使用可能になるまでブロックされます。nullBlockingQueue

使用しているキューの優先度の部分は、アイテムが特定の順序でキューから読み込まれることを意味します (実装されている場合は自然Comparableに、またはに従っていますComparator)。

PriorityQueue通常、またはのいずれかの抽象型に依存する必要がありますBlockingQueue。コードにこれら両方の概念の知識が必要な場合は、再考が必要になる場合があります。

PriorityQueueメッセージの順序付けに要約すると、が必要になる理由は多数あります。たとえば、ジョブのキューで、それらのジョブに優先順位を付けたい場合があります。つまり、通常、ジョブを処理するコードは順序にとらわれない必要があります。

通常、BlockingQueueワーカースレッドがキューに入れられた作業を取得し、実行する作業がない場合は、作業が利用可能になるまでそれらのスレッドをブロックできます。a の例のようPriorityQueueに、呼び出しコードはこれにとらわれない可能性がありますが、常にそうであるとは限らないある種の待機タイムアウトを使用したい場合があります。

score 2 · Accepted Answer

これが古いトピックであることは知っていますが、優先キューの同時実装を考慮していないことがわかりました。

Java のコレクションフレームワークにはそれがありませんが、それを作成するのに十分なビルディングブロックがあります。

public class ConcurrentSkipListPriorityQueue<T> implements Queue<T> {

    private ConcurrentSkipListMap<T, Boolean> values;

    public ConcurrentSkipListPriorityQueue(Comparator<? super T> comparator) {
        values = new ConcurrentSkipListMap<>(comparator);
    }

    public ConcurrentSkipListPriorityQueue() {
        values = new ConcurrentSkipListMap<>();
    }

    @Override
    public boolean add(T e) {
        values.put(e, Boolean.TRUE);
        return true;
    }

    @Override
    public boolean offer(T e) {
        return add(e);
    }

    @Override
    public T remove() {
        while (true) {
            final T v = values.firstKey();
            if (values.remove(v)) {
                return v;
            }
        }
    }

    @Override
    public T poll() {

        try {
            while (true) {
                if (values.isEmpty()) {
                    return null;
                }
                final T v = values.firstKey();
                if (values.remove(v)) {
                    return v;
                }
            }
        } catch (NoSuchElementException ex) {
            return null; // poll should not throw an exception.. 
        }
    }

    @Override
    public T element() {
        return values.firstKey();
    }

    @Override
    public T peek() {
        if (values.isEmpty()) {
            return null;
        }

        try {
            return element();
        } catch (NoSuchElementException ex) {
            return null;
        }
    }

    @Override
    public int size() {
        return values.size();
    }

    @Override
    public boolean isEmpty() {
        return values.isEmpty();
    }

    @Override
    public boolean contains(Object o) {
        return values.containsKey(o);
    }

    @Override
    public Iterator<T> iterator() {
        return values.keySet().iterator();
    }

    @Override
    public Object[] toArray() {
        return values.keySet().toArray();
    }

    @Override
    public <T> T[] toArray(T[] a) {
        return values.keySet().toArray(a);
    }

    @Override
    public boolean remove(Object o) {
        return values.remove(o);
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return values.keySet().containsAll(c);
    }

    @Override
    public boolean addAll(Collection<? extends T> c) {

        boolean changed = false;

        for (T i : c) {
            changed |= add(i);
        }

        return changed;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return values.keySet().removeAll(c);
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return values.keySet().retainAll(c);
    }

    @Override
    public void clear() {
        values.clear();
    }

}

このキューは、すべての操作を ConcurrentSkipListMap クラスに委譲することにより、スキップリストに基づいています。これにより、複数のスレッドからのノンブロッキング同時アクセスが可能になります。

java - PriorityQueue と PriorityBlockingQueue

3 に答える 3

Related

Reference