STL priority_queueで効率的な優先度更新を行う方法

StackOverflow https://stackoverflow.com/questions/649640

  •  19-08-2019
  •  | 
  •  

質問

いくつかのオブジェクトのpriority_queueがあります：

typedef priority_queue<Object> Queue;
Queue queue;

オブジェクトの優先度は時々変更される可能性があります-キュー内のオブジェクトの優先度を効率的な方法で更新できる必要があります。現在、このメソッドを使用していますが、動作しますが効率が悪いようです：

Queue newQueue;
while (!queue.empty())
{
  Object obj=queue.top();
  queue.pop();

  if (priorityHasChanged(obj))
    newQueue.push_back(Object(new_priority));
  else
    newQueue.push_back(obj);
}

newQueue.swap(queue); // this only works because I actually subclassed the priority_queue
                 // class and exposed a swap method that swaps in the container

私はこの方法で実装しました。当時急いでいたので、これが私ができる最も迅速なことでした。しかし、これよりも良い方法が必要です。本当に欲しいのは、次のいずれかの方法です：

  • 優先度が変更されたインスタンスを抽出し、新しい優先度の値を持つ新しいインスタンスを挿入します
  • 変更された優先度でインスタンスを更新し、キューを更新して、正しくソートされるようにします

これを行う最良の方法は何ですか？

役に立ちましたか？

解決

標準の優先度キューでは運が悪かったと思います。なぜなら、基礎となるdeque / vector / listなどには到達できないからです。独自に実装する必要があります-それほど難しくありません。

他のヒント

問題を解決するための2つの選択肢を提案できますが、どちらも実際の更新は行いません。

  1. priority_queueを使用し、更新するたびに要素をプッシュします。無駄なエントリがキューにあるという事実を受け入れます。最上位の値をポップするときに、最新の値が含まれているかどうかを確認します。そうでない場合は、無視して次をポップします。

    この方法では、更新された要素の削除を先頭に達するまで遅らせます。ダイクストラアルゴリズムを実現するトッププログラマーがこのアプローチを使用していることに気付きました。

  2. setを使用します。また、対数時間で最大の要素を抽出できるようにソートされます。また、古い要素を削除してから、再度挿入することもできます。そのため、まだ更新操作はできませんが、削除と再挿入は可能です。

両方のアプローチの複雑さは同じようです。

（私が知っている）STLでこれを行う最も簡単な方法は、エントリを削除し、優先度を更新してから再挿入することです。これを行うにはstd :: priority_queueを使用すると非常に遅くなりますが、std :: setでも同じことができます。残念ながら、セット内にあるオブジェクトの優先度を変更しないように注意する必要があります。

私はmutable_priority_queueクラスに基づいて、std :: multimap（値のマッピングへの優先度用）とstd :: map（値から優先度へのマッピング用）を一緒に実装しました。対数時間の値。コードとその使用方法の例をこちら

適切なデータ構造は、<！> quot; Fibonacci Heap <！> quot;と呼ばれます。 ただし、自分で実装する必要があります。 挿入/更新はO（1）です ExtractMinはO（logn）

です

高性能の更新可能な優先度キューを実装し、 github で利用できるようにしました。

これは、通常の使用方法です。

better_priority_queue::updatable_priority_queue<int,int> pQ;
pQ.push(0, 30);   // or pQ.set(0, 30)
pQ.push(1, 20);
pQ.push(2, 10);

pQ.update(2, 25); // or pQ.set(2, 25)

while(!pQ.empty())
    std::cout << pQ.pop_value().key << ' ';

// Outputs: 0 2 1

Jarekczekの答えを補完するために、実際にsetと<！> quot;不要なエントリを含む純粋なヒープ<！> quot;アプローチは同じ複雑さを持ち、stl::setバージョンは通常、深さが2 * log_2（n_elements）よりも低いことを保証する赤黒ツリーで実装されているという事実により、stl::priority_queueバージョンよりもはるかに遅く実行されます。定期的な更新が必要ですが、<=>はできるだけ純粋で高速なバイナリヒープです。これが、ダイクストラを実装するときに通常使用される理由です。

ただし、いくつかのベースノードで多くの更新を行う場合、セットアプローチはより高速になる場合があります。これは、私のライブラリを使用することで最も改善される場所でもあります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top