3

2つのスレッドの優先度が同じ場合は、優先度と先入れ先出し（FCFS）でスレッドをスケジュールする方法を探しています。キューのヒープなどを使用することを考えていました。問題は、自分で優先度付きキューを実装したとしても、優先度を変更できると、このキューへの挿入順序が台無しになることです。

この問題を解決するために、各スレッドの挿入時間を節約し、優先度キューを挿入時間（プライマリ優先度パラメーターのセカンダリパラメーターとして）で並べ替えることができますが、解決できるデータ構造の組み合わせがあると思います挿入時間を使用せずに問題。

複雑さはあるべきです（通常のキューを持ち、スレッドをポップする必要があるときはいつでもキューを繰り返すなど、複雑さをO(logN)伴う単純なソリューションがいくつかあります）。O(N)

4

1 に答える 1

2

問題を正しく把握できていない可能性がありますが、優先度ごとに個別のリストを作成できます。
したがって、各スレッドは、その優先度に基づいて対応するリストに追加されます。また、常にリストの最後に追加してヘッドから削除するため、FCFS の動作になります。

優先度キューを作成して、優先度が最も低い次のスレッドを取得することもできます (次のスレッドを取得するには O(1)、挿入するには O(logN)。比較のために、各ノードの優先度と挿入時間の組み合わせを使用できます。

于 2012-04-09T11:27:37.107 に答える