5

「高優先度」と「低優先度」のキューが次のように実装されたC＃4.0アプリがあります。

BlockingCollection highPriority = new BlockingCollection（1000）; BlockingCollection lowPriority = new BlockingCollection（1000）;

highPriorityで生成されたデータは、lowPriorityで生成されたデータよりも先に消費する必要があります。ここでのひねりは、データがいつでも2つのキューのいずれかに生成される可能性があることです。したがって、highPriorityですべてのデータを消費した後、lowPriorityである可能性のあるすべてのデータを消費します。lowPriorityでデータを消費しているときに、highPriorityで新しいデータが生成された場合、lowPriorityで現在のアイテムの消費を終了してから、切り替えてhighPriorityでデータを処理したいと思います。

誰かがこれを助けるためのアルゴリズムを提案できますか？擬似コードは問題ありません。どうもありがとう。

4

3 に答える 3

3

これはどう：

while(true)
{
    workitem = highQueue.dequeue();

    if(workitem == null)
        workitem = lowQueueu.dequeue()

    process(workitem)
}
于 2011-04-01T17:14:06.130 に答える
1

これは、単一の優先キューで行います。これにより、コードをほとんど変更せずに、後で3番目の優先度を追加できます。

lockFree-SkipListを使用する前に作成しましたが、通常のスキップリスト（http://www.codeproject.com/KB/recipes/PriorityQueueSkipList.aspx）を使用するプロジェクトを次に示します。スキップリストを使用したのは、それらが並行性の下で十分に実行され、実装が非常に簡単であるためです（ロックフリーバージョンを除く）。

赤黒木を使用するCodePlexの優先キューも確認しましたが、現在は見つかりません。更新：私が考えていた優先キューの実装は、NGenericsプロジェクトの一部でした：http ：//code.google.com/p/ngenerics/

于 2011-04-02T19:59:00.440 に答える
1

@Kevin Brock が提案したように、可能であればこれを単一のオブジェクトにラップし、そのオブジェクトに実装することをお勧めしますIProducerConsumerCollection。それ以外の場合、呼び出すコードTryDequeueはビジー待機ループを実行する必要があります。つまり、キューが 2 つある場合は、次のように記述する必要があります。

WorkItem item = null;
do
{
    if (!hpQueue.TryDequeue(out item))
    {
        lpQueue.TryDequeue(out item);
    }
while (item != null);

独自のクラスを使用する場合は、イベント (EventWaitHandleなど) を使用してビジー状態の待機を防ぐことができます。

実際には、プライオリティ キューを使用した方がよいでしょう。プライオリティ キューをスレッド セーフにして を実装するのは非常に簡単IProducerConsumerCollectionで、それを で使用できますBlockingCollection。開始するには、Julian Bucknall のPriority Queue in C#が適しています。

于 2011-04-01T18:18:07.797 に答える