2

ジョブのリストと、これらのジョブを待っているワーカーのキューがあります。すべての仕事は同じですが、労働者は異なり、仕事を遂行する能力によって分類されます。つまり、最初の人はこの仕事を最もうまく行うことができ、2番目の人は少し悪いことをします。仕事は常にその時点で空いている人から最もスキルの高い人に割り当てられます。ある人に仕事が割り当てられると、しばらくの間、列から外れます。しかし、彼が終わると、彼は元の位置に戻ります。したがって、たとえば、ある瞬間のワーカー キューは次のようになります。

[x, x, .83, x, .7, .63, .55, .54, .48, ...]

はx行方不明の労働者を表し、数字は残された労働者のスキルレベルを示します。新しいジョブが発生すると、使用可能なワーカーの中で最もスキルの高い 3 番目のワーカーに割り当てられます。したがって、次の瞬間のキューは次のようになります。

[x, x, x, x, .7, .63, .55, .54, .48, ...]

この時点でワーカー #2 が仕事を終えてリストに戻ったとします。

[x, .91, x, x, .7, .63, .55, .54, .48, ...]

プロセスが完全に明確になったことを願っています。私の質問は、ワーカーの迅速な検索と削除、およびその位置への挿入を実装するために使用するアルゴリズムとデータ構造です。

今のところ、私が見ることができる最善のアプローチは、最小限の要素を削除する (ジョブを割り当ててワーカーをキューから削除する) ために償却されたフィボナッチ ヒープを使用することです。これはかなり良い方法です。しかし、要素がすでにソートされており、時々キューをドロップするだけであるという事実を考慮に入れる、さらに優れたアルゴリズム/データ構造はありますか?O(log n)O(1)

4

2 に答える 2

2

Fibonacci ヒープよりも実装が簡単で、挿入と削除もサポートする通常のheapO(lg n)を使用します (挿入と同じ数の削除があるため、安価な挿入を取得してもそれほど価値はありません)。priority_queueフィボナッチ ヒープとは対照的に、通常のヒープはC++ の STLなどの標準ライブラリに実装されることがよくあります。

より高速なデータ構造が存在する場合、それを使用して よりも高速に並べ替えを実行できますがOmega(n lg n)、これは一般的なケースでは不可能です。スキルレベルの数値が特殊な性質を持っている場合（例えば、制限された範囲の整数）、 よりも高速に並べ替えを実行することは可能ですOmega(n lg n)が、その場合により高速な優先キューが存在するかどうかはわかりません。

(ちなみに、「rambo coder」のコメントは完全に正しいです。ヒープの実際のパフォーマンスと、ソートされていないリストのパフォーマンスを比較する必要があります)。

于 2012-11-23T17:30:34.337 に答える
2

理論的な演習として、データを前処理してすべてを小さな整数に減らし、完全なキュー内の位置を与えることを検討してください。最初に頭に浮かぶのはhttp://en.wikipedia.org/wiki/Van_Emde_Boas_treeで、理論的にはログ n をログ n に減らすことができます。この記事の最後に、非現実的ではない解決策のアイデアがいくつかあることに注意してください。http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.137.8757 (一定時間でキーを減少させる整数優先度キュー...)の記事では、フィボナッチ ツリーよりも理論的に優れていると特に主張しています。小さな整数キーの場合、ソートの問題とのリンクに注意してください-また、ソートへのリンクを含む別の論文を参照します-これも非常に理論的です。

于 2012-11-23T20:25:53.640 に答える