Javaコンテナ:Stack,Queue,PriorityQueueおよびBlockingQueue
5738 ワード
JavaではStackクラスがVectorクラスを継承し,その上でスタックの機能を実現している.インタフェースによる非表示ではなく直接継承であるため(QueueはLinkedListで実現されているが、非キューインタフェースに対して非表示である)、JavaのStackはVectorのすべての方法を有し、スレッドセキュリティ特性を継承している(したがって、Vectorと同様にパフォーマンスに損失がある).
リストに基づいて、Stackは以下の方法を追加した.
Stackは古く,スタックの動作をシミュレートするために同じ関数を繰り返し実現する方法であることが分かった.効率を重視する場合、LinkedListまたはArrayListに基づいてスタックを再実現すると、より良い効果が得られることは明らかである.
2. Queue
継承階層から見ると,QueueはList,Map,Setと同様にCollectionsクラスを直接継承したコンテナクラスであるが,その実現からQueueは特殊なリストと見なすこともできる.なぜならQueueの直接実装方法はLinkedListであり,その機能を制限し,Queueがサポートする機能:add(),remove(),element(),offer(),poll(),peek(),put(),take()のみを暴露しているからである.もちろんLinkedListのこれらの機能はListインタフェースに対しても,すべて露出しているわけではない.
Queueオブジェクトは、次の方法で操作できます.
キュー内のpollとpeek操作はNullをフラグとするため、キューにNull要素を追加するのは合法ではありません.
3. PriorityQueue
StackとQueueを紹介した後、自然ともう一つの最も基本的なデータ構造であるHeap、つまりここのPriorityQueue優先キューといえます.優先キューについては、かなり前にC++の優先キューを紹介しましたが、Javaも同様で、ポイント部分はComparatorの操作です.PriorityQueueがHeapベースであることを知っているため、新しい要素が格納されるとsiftUpUsingComparatorメソッドが呼び出され、以下のように定義されます.
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
コードから分かるように、Comparatorの戻り値が負の場合、siftUp操作が行われます.たとえば、数値の大きい数字(以下の例ではa)を先に列挙したい場合は、compare(a,b)を列挙したい場合は、-1を返します.C++と同様に,方法は「より小さくない」という概念を得ていることがわかる.我々が定義した方法は、「より小さい」方法と見なすことができる.
また、Comparatorというインタフェースには多くの方法があるにもかかわらず、
@FunctionalInterfaceのフラグがあり、これが関数インタフェースであることを示しています.言い換えれば、Java 8ではlambda式を使用してこの方法を書くことができます.匿名クラスメソッドで書かれたComparator:
PriorityQueue priorityQueue=new PriorityQueue(new Comparator() {
@Override
public int compare(Student student1, Student student2) {
return student1.mark.compareTo(student2.mark);
}
});
Lambda式でComparatorを書く
PriorityQueue priorityQueue=new PriorityQueue((Comparator)(student1, student2)->student1.mark.compareTo(student2.mark));
ここで注意しなければならないのは,タイプ変換を加えなければJavaはlambda式のタイプを正確に推定できないことである.
4. BlockingQueue
JavaにおけるQueueの最も重要な応用はおそらくそのサブクラスBlockingQueueである.
生産者消費者モデルを考慮すると、私たちは複数の生産者と複数の消費者を持っており、生産者は絶えず消費者に資源を提供しているが、それらの生産/消費速度が一致しないか、不安定であれば、大量の生産者のアイドル/消費者のアイドルをもたらす.この場合、生産者がリソースをバッファに配置し、消費者がバッファからリソースを絶えず取り出し、アイドルとブロックを減らすバッファを使用する必要があります.
BlockingQueue,ブロックキュー,すなわち1つのバッファがマルチスレッドプログラミングに適用されると見なす.キューが空の場合、すべての消費者スレッドがブロックされ、キューがいっぱいの場合、すべての生産者スレッドがブロックされます.
queueに加えて、BlockingQueueには次の方法が追加されています.
BlockingQueueインタフェースには、以下のいくつかの実装があります.
4.1. ArrayBlockingQueue
1つの定長配列と2つの識別ヘッダの整数index識別からなり、生産者がデータを入れ、消費者がデータを取り出すのはArrayBlockingQueueにとって同じロック(プライベートなReentrantLock)を使用するため、真の並列は実現できない.初期化時に長さパラメータ以外にbooleanタイプの変数を追加して、プライベートなReentrantLockを初期化できます(初期化はフェアロックかどうか、デフォルトはfalse).
4.2. LinkedBlockingQueue
LinkedBlockingQueueの最大の特徴は、最大容量を指定しないと、無境界キューと見なすことができることです(デフォルトの最大容量制限があり、システムリソースが消費されても達成できないことが多い).すなわち,生産者の行為を制限せず,キューが空の場合のみ消費者の行為を制限する.LinkedBlockingQueueは、putとtakeを制御するために読み書き分離された2つのReentrantLockを採用しているため、より良いパフォーマンス(読み書きロックのように読み書きシーンでより良いパフォーマンスを提供する)が得られ、以下のようになります.
/** Lock held by take, poll, etc */
private final ReentrantLock takeLock = new ReentrantLock();
/** Wait queue for waiting takes */
private final Condition notEmpty = takeLock.newCondition();
/** Lock held by put, offer, etc */
private final ReentrantLock putLock = new ReentrantLock();
/** Wait queue for waiting puts */
private final Condition notFull = putLock.newCondition();
ArrayBlockingQueueとLinkedBlockingQueueは最も一般的な2つのブロックキューです.
4.3. PriorityBlockingQueue
PriorityBlockingQueueはPriorityQueueのパッケージであるため、優先キューでもある.優先度のデフォルトは、直接比較であり、大きい方が先にデキューされ、コンストラクタからカスタムComparatorに転送されます.PriorityQueueは実装上無境界キューであるため、PriorityBlockingQueueは同様に無境界キューであり、生産者には制限されない.
4.4. DelayQueue
DelayQueueはPriorityBlockingQueueに基づいてパッケージ化されたもので、Delayedオブジェクトを格納するために使用されます.このキューのヘッダは、遅延期間が満了した後に最も長く保存されたDelayed要素(すなわち、時間を優先してPriorityBlockingQueueを利用する)であり、要素遅延期間が満了しない場合、poll操作を行うとNullに戻ります.take操作がブロックされます.
4.5. SynchronousQueue
SynchronousQueueは非常に特殊で、容量がありません.言い換えれば、長さが0のBlockingQueueであり、生産者と消費者は仲介のない直接取引を行い、生産者/消費者が適切な目標を見つけていない場合、ブロックが発生します.しかし、一環が減少したため、その全体的な性能はいくつかのシステムでより適している可能性があります.この方法は、構築時に公平/デフォルトとして決定される非公平モードもサポートし、非公平モードである場合、一部の生産者/消費者の飢餓を引き起こす可能性がある.
5.参考文書
Javaマルチスレッド-ツール編-BlockingQueue