19

PriorityBlockingQueueは無制限ですが、何らかの方法でバインドする必要があります。それを達成するための最良の方法は何ですか？

参考までに、境界PriorityBlockingQueueは で使用されますThreadPoolExecutor。

NB: 例外が発生した場合に例外をスローしたくない場合は、オブジェクトをキューに入れてから、優先度の値に基づいてカットしたいと考えています。このカットを行う良い方法はありますか？

4

9 に答える 9

13

私は実際にそれをサブクラス化しません。現時点ではサンプル コードをまとめることはできませんが、デコレータ パターンのバージョンを提案したいと思います。

新しいクラスを作成し、対象のクラスによって実装されるインターフェイスを実装します: PriorityBlockingQueue。このクラスで使用される次のインターフェイスが見つかりました。

Serializable, Iterable<E>, Collection<E>, BlockingQueue<E>, Queue<E>

クラスのコンストラクターでは、PriorityBlockingQueuea をコンストラクター パラメーターとして受け入れます。

次に、 のインスタンスを介して、インターフェイスに必要なすべてのメソッドを実装しますPriorityblockingQueue。Bounded にするために必要なコードを追加します。これは、Decorator パターンのかなり標準的な実装です。

于 2010-03-04T21:12:45.037 に答える
6

Google Collections/Guavaライブラリにこれの実装があります: MinMaxPriorityQueue。

min-max プライオリティ キューは、最大サイズで設定できます。その場合、キューのサイズがその値を超えるたびに、キューはコンパレータに従って最大の要素 (追加されたばかりの要素である可能性があります) を自動的に削除します。これは、いっぱいになると新しい要素をブロックまたは拒否する従来の制限付きキューとは異なります。

于 2011-09-28T21:36:42.170 に答える
2

頭のてっぺんから、それをサブクラス化し、put メソッドを上書きしてこれを強制します。超過した場合は、例外をスローするか、適切と思われることを行います。

何かのようなもの：

public class LimitedPBQ extends PriorityBlockingQueue {

    private int maxItems;
    public LimitedPBQ(int maxItems){
        this.maxItems = maxItems;
    }

    @Override
    public boolean offer(Object e) {
        boolean success = super.offer(e);
        if(!success){
            return false;
        } else if (this.size()>maxItems){
            // Need to drop last item in queue
            // The array is not guaranteed to be in order, 
            // so you should sort it to be sure, even though Sun's Java 6 
            // version will return it in order
            this.remove(this.toArray()[this.size()-1]);
        }
        return true;
    }
}

編集: add と put の両方で呼び出しオファーがあるため、それをオーバーライドするだけで十分です

編集 2: maxItems を超える場合は、最後の要素を削除する必要があります。ただし、もっとエレガントな方法があるかもしれません。

于 2010-02-26T12:49:28.677 に答える
2

Frank V の提案に従って BoundedPriorityBlockingQueue を実装した後、私はそれが私が望んでいたことをまったくしていないことに気付きました。主な問題は、キューに挿入する必要がある項目が、既にキューにあるすべてのものよりも優先度が高い可能性があることです。したがって、私が本当に欲しいのは「ピボット」メソッドです。オブジェクトをキューに入れると、キューがいっぱいになったときに、ブロックするのではなく、優先度の最も低いオブジェクトを取得したいと考えています。

Frank V の提案を具体化するために、次の断片を使用しました...

public class BoundedPriorityBlockingQueue<E> 
   implements 
     Serializable, 
     Iterable<E>, 
     Collection<E>, 
     BlockingQueue<E>, 
     Queue<E>, 
     InstrumentedQueue 
{

... プライベートな最終的な ReentrantLock ロック; // = 新しい ReentrantLock(); プライベート最終条件 notFull;

final private int capacity;
final private PriorityBlockingQueue<E> queue;

public BoundedPriorityBlockingQueue(int capacity) 
  throws IllegalArgumentException, 
         NoSuchFieldException, 
         IllegalAccessException 
{
   if (capacity < 1) throw 
       new IllegalArgumentException("capacity must be greater than zero");      
   this.capacity = capacity;
   this.queue = new PriorityBlockingQueue<E>();

   // gaining access to private field
   Field reqField;
   try {
    reqField = PriorityBlockingQueue.class.getDeclaredField("lock");
    reqField.setAccessible(true);
    this.lock = (ReentrantLock)reqField.get(ReentrantLock.class);
    this.notFull = this.lock.newCondition();

   } catch (SecurityException ex) {
    ex.printStackTrace();
    throw ex;
   } catch (NoSuchFieldException ex) {
    ex.printStackTrace();
    throw ex;
   } catch (IllegalAccessException ex) {
    ex.printStackTrace();
    throw ex;
   }

...

@Override
public boolean offer(E e) {
    this.lock.lock();
    try {
        while (this.size() == this.capacity)
            notFull.await();
        boolean success = this.queue.offer(e);
        return success;
    } catch (InterruptedException ie) {
        notFull.signal(); // propagate to a non-interrupted thread
        return false;

    } finally {
        this.lock.unlock();
    }
}
...

これにはいくつかのインストルメンテーションも含まれているため、キューの有効性を確認できます。私はまだ「PivotPriorityBlockingQueue」に取り組んでいます。興味がある人は投稿できます。

于 2011-06-30T14:37:10.927 に答える
1

ConcurrencyUtils リポジトリに実装があります。

于 2015-10-27T00:51:42.583 に答える
0

これまでのところ、次のすべての特性を備えた単一の回答はありません。

  • インターフェイスを実装しBlockingQueueます。
  • 絶対最大値の除去をサポートします。
  • 競合状態はありません。

残念ながら、BlockingQueue標準の Java ライブラリには実装がありません。実装を見つけるか、自分で何かを実装する必要があります。を実装するBlockingQueueには、適切なロックに関する知識が必要です。

ここに私が提案するものがあります: https://gist.github.com/JensRantil/30f812dd237039257a3dを見て、それをテンプレートとして使用して、 a の周りに独自のラッパーを実装しますSortedSet。基本的に、すべてのロックがそこにあり、複数の単体テストがあります (微調整が必​​要です)。

于 2015-07-17T18:48:23.530 に答える
0

実行したい Runnables の順序が厳密でない場合 (そのまま: 優先度の高いタスクが存在するにもかかわらず、優先度の低いタスクが実行される場合があります)、次のことをお勧めします。サイズダウン:

if (queue.size() > MIN_RETAIN * 2){
    ArrayList<T> toRetain = new ArrayList<T>(MIN_RETAIN);
    queue.drainTo(toRetain, MIN_RETAIN);
    queue.clear();
    for (T t : toRetain){
      queue.offer(t);
    }
}

優先度の低いタスクが同時アクセスを使用してキューから取得されると、ドレインが瞬間につながるため、順序を厳密にする必要がある場合、これは明らかに失敗します。

利点は、これがスレッド セーフであり、プライオリティ キューの設計と同じくらい高速になる可能性が高いことです。

于 2010-03-04T21:55:40.800 に答える
-1

Google Collections APIのForwardingQueueを見てください。セマティクスをブロックするには、 Semaphoreを使用できます。

于 2010-03-06T02:05:28.910 に答える
-1

ここに別の実装があります

あなたが求めていることをしているようです：

BoundedPriorityQueue は、要素数に上限がある優先キューを実装します。キューがいっぱいでない場合、追加された要素は常に追加されます。キューがいっぱいで、追加された要素がキュー内の最小の要素よりも大きい場合、最小の要素が削除され、新しい要素が追加されます。キューがいっぱいで、追加された要素がキュー内の最小要素より大きくない場合、新しい要素は追加されません。

于 2012-09-03T08:18:45.383 に答える